MarsCode 错题本

发表于 2025-01-19 更新于 2025-02-21

51 和的逆运算

#全排列
这题在给定的和不重复的情况下很简单：

首先升序排序好数组sums，生成答案数组nums[n]。
nums[0] + nums[1] 必然等于sums[0]（最小值），nums[0] + nums[2] 必然等于sums[1]（次小值）, … , nums[n-2] + nums[n-1] 必然等于sums[lastIndex]（最大值）。
可以反向推测出nums[0] = (sums[0] + sums[1] - sums[n-1]) / 2，论证看下方：

nums[n] = {a, b, c, d, e} 从小到大排列
a + b = sums[0] (1) // 最小
a + c = sums[1] (2)
a + d = sums[2]
a + e = sums[3]
b + c = sums[4] (3)
...
(1) + (2) = 2a + (3)
2a = sums[0] + sums[1] - sums[n-1] = (1) + (2) - (3)

得出了nums[0]，其他数字都可以用nums[i] = sums[i-1] - nums[0]推出来

但是给定的和重复的情况下，上面的第2条就不成立了。例如测试用例3：

sums[] = { 223, 224, 225, 225, 226, 226, 227, 227, 228, 229 }
nums[n] = { 111, 112, 113, 114, 115 }
a + b = 223
a + c = 224
a + d = 225
a + e = 226
b + c = 225 // 打破了第2条假设，不是按升序排序！

在给定的和有重复元素的情况下，我们再按照上面的步骤1排序好数组sums，算出来的nums[0]就是错误的，因为这个时候b+c < a+e，a+e排到了b+c的位置，再套用步骤3的算法就不对了。
$a + b + a + c \neq 2a + a + e$

综上所述，重新整理后我们会发现，排序数组不是目的。真正的目的是能够让数组符合步骤3的公式nums[0] = (sums[0] + sums[1] - sums[n-1]) / 2，让b+c能够正确地出现在sums[n-1]的位置。
可是，我们并没有原数组，怎么做的出来呢？

数学家思维：给定一个有序的数组nums，其中元素按升序排列，一定存在一个有序两两和序列sums。

找到这个有序两两和序列，就可以根据上面的算法反推出原来的数组。

我不知道有没有一种数学算法可以优雅地找到有序两两和序列sums，一举这个问题。但是全排列一定能找到这个sums。以下是第51题的全部代码：

import java.util.Arrays;

public class Main {
    
    static String ans;

    public static String solution(int n, int[] sums) {
        ans = "Impossible";
        fullArrange(sums, 0, n);
        // System.out.println(ans);
        return ans;
    }
    
    private static void check(int n, int[] sums) {
        int[] nums = new int[n];
        nums[0] = (int) Math.round((sums[0] + sums[1] - sums[n-1]) / 2.0);
        for (int i = 1; i < n; i += 1) {
            nums[i] = sums[i-1] - nums[0];
        }
        
        for (int i = 0, k = 0; i < n; i += 1) {
            for (int j = i+1; j < n; j += 1) {
                if (nums[i] + nums[j] != sums[k++]) {
                    return;
                }
            }
        }
    
        StringBuilder result = new StringBuilder();
        Arrays.sort(nums);
        for (int num: nums) {
            result.append(num + " ");
        }
        ans = new String(result.deleteCharAt(result.length()-1));
    }

    // 全排列，确定sums第k位的值
    private static void fullArrange(int[] sums, int k, int n) {
        if (k == sums.length) {
            check(n, sums);
            return;
        }
        
        for (int i = k, l = sums.length; i < l; i += 1) {
            swap(sums, i, k);
            fullArrange(sums, k + 1, n);
            swap(sums, i, k);
        }
    }
    
    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

454 最少时间收集RGB灯

#滑动窗口
之前做过滑动窗口的题目，如最长不重复数组，但是没有理解滑动窗口的本质，遇到这题还是没有思路。

滑动窗口的本质：给定一个数组，你需要遍历所有的子数组才能得到答案，但是并不需要每次都从头扫描。你需要的结果中，有一部分是始终存在的、重复的。

例如这个RGB问题，最先想到的方法就是遍历所有的子数组，检查每个子数组是否包含RGB，然后求最短长度。
但是，扫描RRGGGBR，我们得到两个RGB，分别是RGGGB和GBR。可见，我们不需要重复扫描中间的3个G来得到最终结果。而是要确定开头和结尾，确定范围仅此而已。

滑动窗口就是双指针，确定开头与结尾。
而其中一个指针，结尾，是必定要遍历整个数组的，不然得不到答案。
那么，怎样确定开头呢？

满足条件后，确定本次开头，并寻找下一个开头。

判断满足条件：在我们的题目里，可以维护一个Set，来检查是否找到了RGB三个字母。

if (charSet.size() == 3) { // 满足条件
    // 1. 确认本次长度
    // 2. 从Set中移除第一个字母
    // 3. 确定下一个start
}

确定本次开头：三个字母找到后，我们需要做的是，找到第一个字母最后出现的位置，确认长度。
我们可以分别用R, G, B来记录字母最后下标。

if (ch == 'R') R = end;
if (ch == 'G') G = end;
if (ch == 'B') B = end;
if (charSet.size() == 3) { // 满足条件
    // 1. 确认本次长度
    start = min(R, G, B); // 第一个字母最后位置
    length = Math.min(length, end - start);
    // 2. 从Set中移除第一个字母
    charSet.remove(S.charAt(start));
}

寻找下一个开头：下一个开头，就是第二个字母最后出现的位置。

start = secondRGB(R, G, B);

int secondRGB(int R, int G, int B) {
    int[] arr = {R, G, B}; 
    Arrays.sort(arr); 
    return arr[1];
}

以下是454全部代码（两个函数合并为一次数组排序）：

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static int solution(int N, String S) {
        int start, end;
        int length = Integer.MAX_VALUE;
        Set<Character> charSet = new HashSet<>();
        int R, G, B;
        R = G = B = -1;
        for (start = end = 0; end < N; end += 1) {
            char ch = S.charAt(end);
            charSet.add(ch);
            if (ch == 'R') R = end;
            if (ch == 'G') G = end;
            if (ch == 'B') B = end;
            if (charSet.size() == 3) {
                int[] charIndex = {R, G, B};
                Arrays.sort(charIndex);
                start = charIndex[0];
                length = Math.min(length, end - start);
                charSet.remove(S.charAt(start));
                start = charIndex[1];
            }
        }
        // System.out.println(length);
        return length == Integer.MAX_VALUE ? -1 : length;
    }
    
    public static void main(String[] args) {
        System.out.println(solution(5, "RRGGB") == 3);
        System.out.println(solution(4, "RRRR") == -1);
        System.out.println(solution(6, "RGBRGB") == 2);
    }
}