No.1 统计匹配检索规定的物品数量
解题思路
枚举、统计。
代码展现
class Solution { public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) { int index = 0; if (ruleKey.equals("color")) { index = 1; } else if (ruleKey.equals("name")) { index = 2; } int count = 0; for (var item : items) { if (item.get(index).equals(ruleValue)) { count++; } } return count; }}No.2 最靠近指标价格的甜点老本
解题思路
递归搜寻即可，把所有的配比计划都枚举一遍。
代码展现
class Solution { int answer; public int closestCost(int[] baseCosts, int[] toppingCosts, int target) { answer = 0x3f3f3f3f; // INF for (int base : baseCosts) { dfs(base, 0, toppingCosts, target); } return answer; } private void dfs(int sum, int idx, int[] toppingCosts, int target) { if (sum - target > Math.abs(answer - target)) { return; } if (idx == toppingCosts.length) { int cur = Math.abs(sum - target); int min = Math.abs(answer - target); if (cur < min || (cur == min && sum < answer)) { answer = sum; } return; } for (int i = 0; i < 3; i++) { dfs(sum + toppingCosts[idx] * i, idx + 1, toppingCosts, target); } }}No.3 通过起码操作次数使数组的和相等
解题思路
贪婪，每次挑跨度最大的数字操作。
代码展现
class Solution { public int minOperations(int[] nums1, int[] nums2) { // 无解状况判断 if (nums1.length > nums2.length * 6 || nums2.length > nums1.length * 6) { return -1; } // 保障 nums1.sum > nums2.sum if (Arrays.stream(nums1).sum() < Arrays.stream(nums2).sum()) { int[] tmp = nums1; nums1 = nums2; nums2 = tmp; } int sum1 = Arrays.stream(nums1).sum(); int sum2 = Arrays.stream(nums2).sum(); int[] count1 = count(nums1); int[] count2 = count(nums2); int operationCount = 0; // 将 nums1 中的数字变小，nums2 中的数字变大 while (sum1 > sum2) { int i1 = lastNonZero(count1) + 1; int i2 = firstNonZero(count2) + 1; // 挑跨度大的那个数字进行操作 if (i1 - 1 > 6 - i2) { int target = Math.max(1, i1 - (sum1 - sum2)); count1[i1 - 1]--; count1[target - 1]++; sum1 -= i1 - target; } else { int target = Math.min(6, i2 + (sum1 - sum2)); count2[i2 - 1]--; count2[target - 1]++; sum2 += target - i2; } operationCount++; } return operationCount; } private int lastNonZero(int[] arr) { for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] != 0) { return i; } } return -1; } private int firstNonZero(int[] arr) { for (int i = 0; i < arr.length; i++) { if (arr[i] != 0) { return i; } } return -1; } private int[] count(int[] nums) { int[] counts = new int[6]; for (int n : nums) { counts[n - 1]++; } return counts; }}No.4 车队 II
解题思路
枯燥栈，详见正文。
代码展现
class Solution { public double[] getCollisionTimes(int[][] cars) { // 若 answer[i] > 0, 则 car i 必然会与前面的某辆车相遇 // 一辆车后面的车不会影响它的速度，即便相遇了，所以思考从后往前遍历 double[] answer = new double[cars.length]; // 枯燥栈，车速是枯燥递增的 LinkedList<Integer> stack = new LinkedList<>(); for (int i = cars.length - 1; i >= 0; i--) { while (!stack.isEmpty()) { if (cars[stack.getLast()][1] >= cars[i][1]) { // 栈顶更快，追不上，弹出 stack.pollLast(); } else { if (answer[stack.peekLast()] < 0) { break; } double d = answer[stack.peekLast()] * (cars[i][1] - cars[stack.peekLast()][1]); if (d > cars[stack.peekLast()][0] - cars[i][0]) { break; } else { // 在追上前，前车曾经和它之前的车相遇，弹出 stack.pollLast(); } } } if (stack.isEmpty()) { answer[i] = -1; } else { answer[i] = (double) (cars[stack.peekLast()][0] - cars[i][0]) / (cars[i][1] - cars[stack.peekLast()][1]); } stack.addLast(i); } return answer; }}