LeetCode Contest 367

100096. Find Indices With Index and Value Difference I

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

• abs(i - j) >= indexDifference 且
• abs(nums[i] - nums[j]) >= valueDifference

返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

注意：i 和 j 可能 相等 。

测试样例：

输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4

输出：0,3]

解释：
在示例中，可以选择 i = 0 和 j = 3 。abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。因此，[0,3] 是一个符合题目要求的答案。[3,0] 也是符合题目要求的答案。

解答：这道题目和第三题一样，这次就贴一题了。优化的方案是寻找符合条件的，之前数字符合indexDifference中的最小和最大值，能够满足valueDifference条件就输出。最大和最小值可以利用红黑树（Java里面就是TreeMap了）。

class Solution {
    private static final int[] invalid = {-1, -1};

    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (i >= indexDifference) {
                map.put(nums[i - indexDifference], i - indexDifference);
            }
            if (!map.isEmpty()) {
                Map.Entry<Integer, Integer> first = map.firstEntry(), last = map.lastEntry();
                if (Math.abs(nums[i] - first.getKey()) >= valueDifference) {
                    return new int[]{first.getValue(), i};
                }
                if (Math.abs(nums[i] - last.getKey()) >= valueDifference) {
                    return new int[]{last.getValue(), i};
                }
            }
        }
        return invalid;
    }
}

100084. Shortest and Lexicographically Smallest Beautiful String

给你一个二进制字符串 s 和一个正整数 k 。

如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。

令 len 等于 最短 美丽子字符串的长度。

返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。

对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。

• 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。

测试样例：

输入：s = "1011", k = 2

输出：“11”

解释：
示例中共有 3 个美丽子字符串：

1. 子字符串 "1011" 。
2. 子字符串 "1011" 。
3. 子字符串 "1011" 。
   最短美丽子字符串的长度是 2 。长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。

解答：这道题目其实可以用双指针，但是s.length <= 100，我就直接用暴力算法了，编写比较简单。

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        String result = "";
        for (int i = 0; i < s.length(); ++i) {
            for (int j = i; j < s.length(); ++j) {
                String sub = s.substring(i, j + 1);
                if (isValid(sub, k)) {
                    if (result.length() == 0) {
                        result = sub;
                    } else if (result.length() > sub.length()) {
                        result = sub;
                    } else if (result.length() == sub.length() && result.compareTo(sub) > 0) {
                        result = sub;
                    }
                }
            }
        }
        return result;
    }

    private boolean isValid(String sub, int k) {
        int count = 0;
        for (int i = 0; i < sub.length(); ++i) {
            if (sub.charAt(i) == '1') {
                ++count;
            }
        }
        return count == k;
    }
}

8026. Construct Product Matrix

给你一个下标从 0 开始、大小为 n m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

• 对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

返回 grid 的乘积矩阵。

测试样例

输入：grid = [[1,2],[3,4]]

输出：[[24,12],[8,6]]

解释：
p[0][0] = grid[0][1] grid[1][0] grid[1][1] = 2 3 4 = 24
p[0][1] = grid[0][0] grid[1][0] grid[1][1] = 1 3 4 = 12
p[1][0] = grid[0][0] grid[0][1] grid[1][1] = 1 2 4 = 8
p[1][1] = grid[0][0] grid[0][1] grid[1][0] = 1 2 3 = 6
所以答案是 [[24,12],[8,6]] 。

解答：这道题目其实蛮讨厌的。因为n * m最大可以是100000，直接暴力运算肯定是不行的，但是12345这个mod也不能用乘法逆元。为了能完成计算，能想到的就是分组。把这些数分为长度350的region，最多就是285个region。这样每个数的计算可以分成当前region中的数和非当前region group结果的取余。这样可以大幅度减少计算复杂度。

class Solution {
    private static final int mod = 12345, region = 350;

    public int[][] constructProductMatrix(int[][] grid) {
        int n = grid.length, m = grid[0].length, max = (n - 1) * m + m - 1;
        int[][] res = new int[n][m];
        List<Integer> regionMul = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                grid[i][j] %= mod;
                int key = i * m + j, regionNum = key / region;
                if (regionNum == regionMul.size()) {
                    regionMul.add(1);
                }
                int last = regionMul.get(regionNum);
                last = (last * grid[i][j]) % mod;
                regionMul.set(regionNum, last);
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                grid[i][j] %= mod;
                int key = i * m + j, regionNum = key / region;
                int regionSt = regionNum * region, regionEd = Math.min(max, regionNum * region + region - 1);
                int result = 1;
                for (int k = 0; k < regionMul.size(); ++k) {
                    if (k != regionNum) {
                        result = (result * regionMul.get(k)) % mod;
                    }
                }
                for (int k = regionSt; k <= regionEd; ++k) {
                    int x = k / m, y = k % m;
                    if (x != i || y != j) {
                        result = (result * grid[x][y]) % mod;
                    }
                }
                res[i][j] = result;
            }
        }
        return res;
    }
}

昨天的双周赛真的是好难，做不来。这周周赛倒是手速场挺容易的。