力扣第 365 场周赛

比赛时间 2023-10-15。本场周赛国服共 620 人 AK。

T1. 找出满足差值条件的下标 I（3 分）

解题思路

见 T3。

参考代码

略。

T2. 最短且字典序最小的美丽子字符串（4 分）

解题思路

滑动窗口 + 字符串比较。

滑动窗口求最短子串类问题。

时间复杂度：O(n^2)。

参考代码

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int l = 0, r = 0;
        String ans = s;
        int sum = 0;
        boolean flag = false;
        while (r < n) {
            sum += cs[r] - '0';
            while (sum >= k) {
                if (sum == k) {
                    flag = true;
                    String sub = s.substring(l, r + 1);
                    if (ans.length() > sub.length()) {
                        ans = sub;
                    } else if (sub.length() == ans.length() && sub.compareTo(ans) < 0) {
                        ans = sub;
                    }
                }

                sum -= cs[l] - '0';
                l++;
            }

            r++;
        }
        return flag ? ans : "";
    }
}

T3. 找出满足差值条件的下标 II（5 分）

解题思路

记录 前缀最小值、最大值。

时间复杂度：O(n)。

参考代码

class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        int max = 0, maxI = 0, min = (int) 1e9, minI = 0;
        for (int i = 0; i + indexDifference < n; i++) {
            int j = i + indexDifference;
            if (max < nums[i]) {
                max = nums[i];
                maxI = i;
            }
            if (min > nums[i]) {
                min = nums[i];
                minI = i;
            }
            if (max - nums[j] >= valueDifference) {
                return new int[]{maxI, j};
            }
            if (nums[j] - min >= valueDifference) {
                return new int[]{minI, j};
            }
        }
        return new int[]{-1, -1};
    }
}

T4. 构造乘积矩阵（5 分）

解题思路

前后缀分解，注意 逆元 是错误解法。因为 0 不存在逆元。

时间复杂度：O(nm)。

相似题目: 238. 除自身以外数组的乘积 https://leetcode.cn/problems/product-of-array-except-self/

参考代码

class Solution {
    public int[][] constructProductMatrix(int[][] grid) {
        int mod = 12345;
        int n = grid.length;
        int m = grid[0].length;

        int[] L = new int[n * m];
        int[] R = new int[n * m];
        L[0] = 1;
        for (int i = 1; i < n * m; i++) {
            int x = (i - 1) / m, y = (i - 1) % m;
            L[i] = grid[x][y] % mod * L[i - 1] % mod;
        }
        R[n * m - 1] = 1;
        for (int i = n * m - 2; i >= 0; i--) {
            int x = (i + 1) / m, y = (i + 1) % m;
            R[i] = grid[x][y] % mod * R[i + 1] % mod;
        }

        int[][] ans = new int[n][m];
        for (int i = 0; i < n * m; i++) {
            int x = i / m, y = i % m;
            ans[x][y] = L[i] * R[i] % mod;
        }
        return ans;
    }
}

（全文完）