526互联

[Leetcode Weekly Contest]367

发布时间 2023-10-16 20:07:42作者: Jamest

链接：LeetCode

[Leetcode]2903. 找出满足差值条件的下标 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 可能 相等 。

遍历循环即可。

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

[Leetcode]2904. 最短且字典序最小的美丽子字符串

如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。
令 len 等于 最短 美丽子字符串的长度。
返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。
对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。
例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。

滑动窗口。如果窗口内的 1 的个数超过 k，或者窗口端点是 0，就可以缩小窗口。

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        String res = "";
        int minLength = Integer.MAX_VALUE;
        int start = 0, count = 0;
        for(int i=0;i<s.length();++i) {
            if(s.charAt(i) == '1') count ++;
            while (start < i && (count > k || s.charAt(start) == '0')) {
                count -= (s.charAt(start) - '0');
                start ++;
            }

            if(count == k) {
                if(i-start+1 <= minLength) {
                    if(i-start+1 == minLength) res = getMinString(res, s.substring(start, i+1));
                    else res = s.substring(start, i+1);
                    minLength = i-start+1;
                }
            }
        }
        return res;
    }

    private String getMinString(String a, String b) {
        for(int i=0;i<a.length();++i) {
            if(a.charAt(i) < b.charAt(i)) return a;
            else if(a.charAt(i) > b.charAt(i)) return b;
        }
        return a;
    }
}

[Leetcode]2905. 找出满足差值条件的下标 II

给你一个下标从 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 可能 相等 。

滑动窗口。维护每个元素的前缀和后缀的最大值和最小值的「下标」；模拟窗口大小为 indexDifference 的滑动窗口，判断端点的前后缀的最值能否构造目标方案。另外，可以我们发现最值具备单调性，因此我们没必要预处理所有下标的最值，可以在一次遍历的过程中边维护最值，边检查方案。

class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int[] res = new int[]{-1, -1};
        int min = nums[0], max = nums[0];
        // Also can use two points to point to the min index and max index
        Map<Integer, Integer> indexs = new HashMap<>();
        for(int i=indexDifference;i<nums.length;++i) {
            min = Math.min(min, nums[i-indexDifference]);
            max = Math.max(max, nums[i-indexDifference]);
            indexs.put(nums[i-indexDifference],i-indexDifference);
            if(nums[i] - min >= valueDifference) {
                res[0] = i;
                res[1] = indexs.get(min);
                return res;
            }
            if(max - nums[i] >= valueDifference) {
                res[0] = i;
                res[1] = indexs.get(max);
                return res;
            }
        }
        return res;
    }
}

[Leetcode]2906. 构造乘积矩阵

给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：
对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。
返回 grid 的乘积矩阵。

前后缀分解。核心思想：把矩阵拉成一维的，我们需要算出每个数左边所有数的乘积，以及右边所有数的乘积，这都可以用递推得到。
时间复杂度：\(\mathcal{O}(nm)\)，其中 n 和 m 分别为 \(\textit{grid}\) 的行数和列数。
空间复杂度：\(\mathcal{O}(1)\)。返回值不计入。

class Solution {
    public int[][] constructProductMatrix(int[][] grid) {
        int n = grid.length,  m = grid[0].length;
        int[][] res = new int[n][m];
        int[] left = new int[n*m];
        int[] right = new int[n*m];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for(int i=0;i<n;++i) {
            for(int j=0;j<m;++j) {
                if(i == n-1 && j == m-1) continue;
                left[i*m+j+1] = (left[i*m+j] * (grid[i][j] % 12345))% 12345;
            }
        }
        for(int i=n-1;i>=0;--i) {
            for(int j=m-1;j>=0;--j) {
                if(i == 0 && j == 0) continue;
                right[i*m+j-1] = (right[i*m+j] * (grid[i][j] % 12345))% 12345;
            }
        }
        for(int i=0;i<n;++i) {
            for(int j=0;j<m;++j) {
                res[i][j] = (left[i*m+j] * right[i*m+j]) % 12345;
            }
        }
        return res;
    }
}

参考：LeetCode