关于面试:上岸算法-I-LeetCode-Weekly-Contest-222解题报告

No.1 卡车上的最大单元数

解题思路

优先应用容量大的箱子即可。

代码展现

class Solution {public int maximumUnits(int[][] boxTypes, int truckSize) {Arrays.sort(boxTypes, (a, b) -> (b[1] - a[1]));
        int res = 0;
        for (var box : boxTypes) {int cnt = Math.min(truckSize, box[0]);
            res += cnt * box[1];
            truckSize -= cnt;
        }
        return res;
    }
}

No.2 大餐计数

解题思路

枚举即可。应用一个 Map 记录每种美味度对应的菜品数量。

代码展现

class Solution {public int countPairs(int[] deliciousness) {int res = 0, mod = 1000000007, max = 2 * (1 << 20);
        Map<Integer, Integer> map = new HashMap<>();
        for (int d : deliciousness) {for (int sum = 1; sum <= max; sum *= 2) {res = (res + map.getOrDefault(sum - d, 0)) % mod;
            }
            map.put(d, map.getOrDefault(d, 0) + 1);
        }
        return res;
    }
}

No.3 将数组分成三个子数组的计划数

解题思路

二分查找。分成三段 left mid 和 right，有两个分界点，当咱们确定左侧的分界点之后，能够二分查找右侧的分界点的最大值和最小值，在此范畴内都是成立的。

代码展现

class Solution {public int waysToSplit(int[] nums) {int sum = Arrays.stream(nums).sum();
        int mod = 1000000007;
        int cur = nums[0];
        int ans = 0;
        int preSum[] = new int[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length - 1; i++) {cur += nums[i];
            preSum[i] = nums[i] + preSum[i - 1];
            // 最大值
            int lr = findRight(preSum, cur, i);
            // 最小值
            int ll = findLeft(preSum, cur, sum - cur, lr);
            if (ll == -1 || lr == -1 || ll > lr) {continue;}
            ans += (lr - ll + 1);
            ans %= mod;
        }
        return ans;
    }

    int findRight(int[] preSum, int sum, int r) {
        // 右边局部的和小于等于左边
        int l = 1;
        int ret = -1;
        while (l <= r) {int m = (l + r) / 2;
            // 0 ~ m-1
            int lsum = preSum[m - 1];
            // m ~ 右界
            int rsum = sum - preSum[m - 1];
            if (lsum <= rsum) {
                ret = m;
                l = m + 1;
            } else {r = m - 1;}
        }
        return ret;
    }

    int findLeft(int[] preSum, int sum, int rSum, int r) {
        int l = 1;
        int ret = -1;
        while (l <= r) {int m = (l + r) / 2;
            int midSum = sum - preSum[m - 1];
            if (midSum <= rSum) {
                ret = m;
                r = m - 1;
            } else {l = m + 1;}
        }
        return ret;
    }
}

No.4 失去子序列的起码操作次数

解题思路

LCS，须要应用 o(NlogN) 的算法。

代码展现

class Solution {public int minOperations(int[] target, int[] arr) {Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < target.length; i++) {map.put(target[i], i);
        }
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {if (map.containsKey(num)) {list.add(map.get(num));
            }
        }

        List<Integer> list2 = new ArrayList<>();
        for (int num : list) {if (list2.size() == 0 || list2.get(list2.size() - 1) < num) {list2.add(num);
                continue;
            }
            int l = 0, r = list2.size() - 1;
            while (l + 1 < r) {int mid = (l + r) / 2;
                if (list2.get(mid) < num) {l = mid;} else {r = mid;}
            }
            int idx = list2.get(l) >= num ? l : r;
            list2.set(idx, num);
        }
        return target.length - list2.size();}
}