企业面试笔试题

0. 概述

总结一些面试机试中的题目，他们可能是力扣中的原题，都是加工过的，但是其内核还是力扣上的原题，很多题需要两种以上方法的叠加，很有挑战性！

1. 动态规划

倒买装备

出自小红书
在游戏中，击败魔物后，薯队长获得了N件宝物，接下来得把这些宝物卖给宝物回收员来赚点小钱。这个回收员有个坏毛病，每次卖给他一件宝物后，之后他就看不上比这件宝物差的宝物了。

在这个世界中，衡量宝物的好坏有两个维度，稀有度X和实用度H，回收员在回收一个宝物A后，下一个宝物的稀有度和实用度都不能低于宝物A。那么薯队长如何制定售卖顺序，才能卖给回收员宝物总个数最多。

输出描述:
一个整数，表示最多可以卖出的宝物数

示例1
输入
4
3 2
1 1
1 3
1 2
输出
3

解题思路:
对输入的数组按照，排序规则是先按照一个纬度排序，如果这个纬度相等，由第二个纬度决定次序。把排序好的数组，在第二个纬度上求最长升序子序列的长度，就可以得到能卖出最多装备的数量了。
这道题的亮点就是，输入数据的处理和用lambda表达式写比较器，太精妙了！

// 解题思路: 对输入的数组进行排序，就是第一列排序后，如果第一列有相等元素，第二列决定排序次序
public static int getMaxNumOfItems(int[][] input){
    int rows = input.length;
    // 对数组排序, 如果一个参数相等那就比较第二个参数
    Arrays.sort(input, ((o1, o2) -> o1[0]!=o2[0] ? o1[0]-o2[0] : o1[1]-o2[1]));
    // 求排序之后的，在参数二上求最长升序子序列的长度
    int[] arr = new int[rows];
    for (int i = 0; i < rows; i++){
        arr[i] = input[i][1];
    }
    return getLengthOfLIS(arr);
}

// 求给定数组的最长升序子序列长度
public static int getLengthOfLIS(int[] nums){
    // 贪心和二分查找求
    // tails[i] 表示 长度为i+1的LIS的结尾
    // end表示tails数组的有效边界，初始为0
    int[] tails = new int[nums.length];
    int end = 0;
    tails[0] = nums[0];
    for(int cur : nums){
        // 比左边界的数要大，说明升序长度加一
        if (cur > tails[end]){
            end++;
            tails[end] = cur;
        }else {
            int l = 0;
            int r = end;
            int m = 0;
            while(l <= r){
                m = l + ((r-l)>>1);
                if (tails[m] >= cur){
                    r = m-1;
                }else {
                    l = m+1;
                }
            }
            tails[l] = cur;
        }
    }
    end++;
    return end;
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int len = sc.nextInt();
    int[][] input = new int[len][2];
    for (int i=0; i<len; i++){
        input[i][0] = sc.nextInt();
        input[i][1] = sc.nextInt();
    }
    sc.close();
    System.out.println(getMaxNumOfItems(input));
}