LeetCode周记 EP16

阅读数：21次 2024-10-13

字数统计: 2k字 | 阅读时长: 9分

前言

这周AI喜提两项诺奖，工作定下来后还是要多研究一下AI应用。

本周主题：动态规划、滑动窗口、枚举

题目：

241007每日一题—Minimum Number of Refueling Stops
241009每日一题—Find Subarray With Bitwise OR Closest to K
241010每日一题—Find the Number of Good Pairs II

Minimum Number of Refueling Stops

这道题磕磕绊绊也是写出来了，只是优化的有些慢，还是记录一下。

下面是我解题过程中写的注释，包含了状态定义与状态转移：

A pick or no-pick problem, can be solved by DP, stations is sorted
Define dp[i][j] = remain fuel at i when pick j stations
Final problem = dp[target][x] where x >= 0 and no more y>=0&&y<x
dp[i][j] = max(dp[i-1][j]-1, dp[i-1][j-1] + stations[i][1] - 1), where stations[i][0]=i

动态规划

从dp[i-1][j-1]转移，存在“代偿”情况，即dp[i-1][j-1]是一条不通的路，但由于后期遇到大station导致该路通行。为解决代偿，应仅从合法状态转移至新状态，实现方式是遇到不合法状态直接置为极小值后再参与比较。
定义好状态后，发现直接实现仍会超时，采取两步优化：

通过转移方程可以了解到当前状态仅与上一状态有关，可采用滚动数组压缩为两行，优化空间。
基于stations is sorted和stations[n-1]<target可采用优化遍历，转而遍历stations，优化时间。

// author: SilenceZheng66
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        if(startFuel>=target) return 0; // 边界处理1
        int n = stations.length;
        if(n==0) return -1; // 边界处理2
        int[][] dp = new int[2][n+1]; // 滚动数组
        Arrays.fill(dp[0], startFuel);
        int last = 0, cur = 1, cnt = 0;
        for(int i=0;i<n;i++){ // 优化遍历
            int dist = stations[i][-1] 
            dp[cur][-1] 
            for(int j=1;j<=n;j++){
                dp[cur][j] = Math.max(dp[last][j]>=dist?dp[last][j] - dist:Integer.MIN_VALUE, 
                dp[last][j-1]>=dist?dp[last][j-1] + stations[i][0] 
            }
            cnt = stations[i][0]; // 移动已走过的距离
            int t = last;
            last = cur;
            cur = t;
        }
        int res = -1;
        for(int j=0;j<=n;j++){
            if(dp[last][j]>=target-stations[n-1][0]){ // 注意此时last才是cur
                res = j;
                break;
            }
        }
        return res;
    }
}

Find Subarray With Bitwise OR Closest to K

连续子数组变形题，上来就应该想到滑窗的…但是我还是选择了枚举，尝试了一下卡到 $O(n^2)$ 优化不出来了，尝试了用每一位计数的方式也没什么用，下面贴灵神思路，更优些。

基础枚举：

// 暴力算法，会超时
class Solution {
    public int minimumDifference(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            ans = Math.min(ans, Math.abs(x - k)); // 单个元素也算子数组
            for (int j = i - 1; j >= 0; j--) {
                nums[j] |= x; // 现在 nums[j] = 原数组 nums[j] 到 nums[i] 的 OR
                ans = Math.min(ans, Math.abs(nums[j] - k));
            }
        }
        return ans;
    }
}

优化思路：把二进制数看成集合，两个数的 OR 就是两个集合的并集。

在上述枚举过程中，nums中最左侧是最大的集合，从左向右依次是前序元素的子集，则当从右向左并入元素x的过程中，如果发现x已经是某元素的子集，则不需要再向左传播了，因为此时x已经是左侧所有元素的子集。

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            ans = Math.min(ans, Math.abs(x - k));
            // 如果 x 是 nums[j] 的子集，就退出循环
            for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
                nums[j] |= x;
                ans = Math.min(ans, Math.abs(nums[j] - k));
            }
        }
        return ans;
    }
}

滑动窗口

参考引文[2]的解法，再看一下滑动窗口，由于连续子数组的“OR和”有单调性，因此可以使用。滑动窗口右移，窗口内的元素“OR和”只能变大或者不变；滑动窗口左移，窗口内的元素“OR和”只能变小或者不变。

我们需要找到一个连续的子数组，使得它们的“OR和”的结果尽可能接近 k。通过滑动窗口的方式，我们可以不断扩大和缩小窗口来尝试找到符合条件的子数组。

由于按位或运算具有不可逆的特点（即不像加法有逆运算减法），一旦某个位被置为 1，即使移除某些数字，OR 的结果中该位仍然可能保持为 1。因此，我们需要仔细追踪每个位的最后贡献位置。

可以使用一个大小为 32 的数组 maxBitPos，记录每个位上最后一次贡献 1 的索引。当左边界移动时，我们检查是否需要移除某个位的贡献，如果该位的最后贡献位置是当前的 left，就可以安全地将该位清除。（这里太妙了，我也想到了用32位数组计数但是没想到和索引建立连接！）

最后，在滑动窗口过程中，计算当前窗口的“OR和”curr，并通过比较abs(curr - k)来更新最小的绝对差。如果当前curr正好等于 k，直接返回 0，因为绝对差已经最小。

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length, left = 0, right = 0, ans = Integer.MAX_VALUE, curr = 0;
        int[] maxBitPos = new int[32]; // 记录每个位的最大位置
        Arrays.fill(maxBitPos, -1); // 初始化数组

        while (right < n) {
            curr |= nums[right]; // 当前窗口内的 OR 值
            // 更新 maxBitPos，记录每个位的最后出现位置
            for (int i = 0; i < 32; i++) {
                if (((nums[right] >> i) & 1) == 1) {
                    maxBitPos[i] = right;
                }
            }
            ans = Math.min(ans, Math.abs(curr - k));
            if (curr == k) {
                return 0; // 如果当前窗口正好匹配 k，直接返回
            }
            // 如果当前 OR 值大于 k，开始收缩窗口
            while (left < right && curr > k) {
                // 检查当前 left 是否在某个位上做出了贡献
                for (int i = 0; i < 32; i++) {
                    if (((nums[left] >> i) & 1) == 1 && maxBitPos[i] == left) {
                        curr &= ~(1 << i); // 清除该位的贡献
                    }
                }
                ans = Math.min(ans, Math.abs(curr - k));
                if (curr == k) {
                    return 0; // 匹配到 k，返回
                }
                left++; // 缩小窗口
            }
            right++; // 扩展窗口
        }

        return ans;
    }
}

Find the Number of Good Pairs II

优化枚举，暴力枚举对于每个nums1[i]都需要遍历nums2长度，优化思路是先组织两个Map把查找效率降低，再遍历nums2，对于每个nums2[j]，遍历它的n*k倍，其中n为正整数，上界为nums1中的最大值。此时底层遍历的时间复杂度由 $O(nums2.length)$ 变为了 $O(\max(nums1)/k \times \log nums2.length)$ ，其中 $\log nums2.length$ 是调和级数求和的结果，因此在 $nums2.length$ 大的情况下这种优化可以显著降低底层遍历的耗时。

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> count2 = new HashMap<>();
        int max1 = 0;
        for (int num : nums1) {
            count.put(num, count.getOrDefault(num, 0) + 1);
            max1 = Math.max(max1, num);
        }
        for (int num : nums2) {
            count2.put(num, count2.getOrDefault(num, 0) + 1);
        }
        long res = 0;
        for (int a : count2.keySet()) {
            for (int b = a * k; b <= max1; b += a * k) {
                if (count.containsKey(b)) {
                    res += 1L * count.get(b) * count2.get(a); // 避免乘积溢出
                }
            }
        }
        return res;
    }
}

参考文献

[1] https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/solutions/2798206/li-yong-and-de-xing-zhi-pythonjavacgo-by-gg4d/?envType=daily-question&envId=2024-10-09
[2] https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/solutions/2943534/hua-dong-chuang-kou-by-hypnotised-e-3jcd/?envType=daily-question&envId=2024-10-09
[3] https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/solutions/2928182/you-zhi-shu-dui-de-zong-shu-ii-by-leetco-obro/?envType=daily-question&envId=2024-10-11

后记

首发于 silencezheng.top，转载请注明出处。