关于redis:上岸算法-I-LeetCode-Weekly-Contest-230解题报告

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