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(); }}