第 367 场力扣周赛

找出满足差值条件的下标 I

同下。

最短且字典序最小的美丽子字符串

滑动窗口。

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        int n = s.length();

        int lo = s.indexOf('1');
        if (lo < 0) {
            return "";
        }

        String ans = "";
        int hi = lo, cnt = 0;
        while (hi < n) {
            cnt += s.charAt(hi++) - '0';
            while (cnt > k || s.charAt(lo) == '0') {
                cnt -= s.charAt(lo++) - '0';
            }
            if (cnt == k) {
                String t = s.substring(lo, hi);
                if (ans.isEmpty() || t.length() < ans.length() || t.length() == ans.length() && t.compareTo(ans) < 0) {
                    ans = t;
                }
            }
        }
        return ans;
    }
}

找出满足差值条件的下标 II

维护最大值和最小值就行。

class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        int minIndex = 0, maxIndex = 0;
        for (int j = indexDifference; j < n; j++) {
            int i = j - indexDifference;
            
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            } else if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }

            if (nums[maxIndex] - nums[j] >= valueDifference) {
                return new int[]{maxIndex, j};
            }
            if (nums[j] - nums[minIndex] >= valueDifference) {
                return new int[]{minIndex, j};
            }
        }
        return new int[]{-1, -1};
    }
}

构造乘积矩阵

前后缀分解，将二维数组看作一维数组。

class Solution {
    private static final int MOD = 12345;

    public int[][] constructProductMatrix(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] p = new int[n][m];

        long suf = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                p[i][j] = (int) suf;
                suf = suf * grid[i][j] % MOD;
            }
        }

        long pre = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i][j] = (int) (p[i][j] * pre % MOD);
                pre = pre * grid[i][j] % MOD;
            }
        }

        return p;
    }
}