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