竞赛链接

https://leetcode.cn/contest/weekly-contest-367/

Q1：100096. 找出满足差值条件的下标 I

https://leetcode.cn/problems/find-indices-with-index-and-value-difference-i/description/

提示：
1 <= n == nums.length <= 100
0 <= nums[i] <= 50
0 <= indexDifference <= 100
0 <= valueDifference <= 50

竞赛时代码——暴力双循环

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

Q2：100084. 最短且字典序最小的美丽子字符串

https://leetcode.cn/problems/shortest-and-lexicographically-smallest-beautiful-string/description/

提示：
1 <= s.length <= 100
1 <= k <= s.length

竞赛时代码——双指针

双指针取符合条件的子字符串，最后取出最小的那个。

class Solution {public String shortestBeautifulSubstring(String s, int k) {List<String> ans = new ArrayList<>();int mnL = Integer.MAX_VALUE, cnt = 0;for (int l = 0, r = 0; r < s.length(); ++r) {if (s.charAt(r) == '1') cnt++;while ((cnt > k || s.charAt(l) == '0') && l < r) {cnt -= (s.charAt(l++) == '1'? 1: 0);}if (cnt == k) {int len = r - l + 1;if (len < mnL) ans.clear();mnL = Math.min(mnL, len);if (len == mnL) ans.add(s.substring(l, r + 1));}}Collections.sort(ans);return ans.size() > 0? ans.get(0): "";}
}

Q3：100101. 找出满足差值条件的下标 II

https://leetcode.cn/problems/find-indices-with-index-and-value-difference-ii/description/

提示：
1 <= n == nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= indexDifference <= 10^5
0 <= valueDifference <= 10^9

竞赛时代码——记录可用最大最小值下标

class Solution {public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {int n = nums.length;int mnId = 0, mxId = 0;         // 记录可用最大值和最小值的下标for (int l = 0, r = indexDifference; r < n; ++r, ++l) {if (nums[l] > nums[mxId]) mxId = l;if (nums[l] < nums[mnId]) mnId = l;if (nums[r] - nums[mnId] >= valueDifference) return new int[]{mnId, r};if (nums[mxId] - nums[r] >= valueDifference) return new int[]{mxId, r};}return new int[]{-1, -1};}
}

Q4：8026. 构造乘积矩阵⭐（重要思想：把二维数组当成一维的）

https://leetcode.cn/problems/construct-product-matrix/description/

提示：
1 <= n == grid.length <= 10^5
1 <= m == grid[i].length <= 10^5
2 <= n * m <= 10^5
1 <= grid[i][j] <= 10^9

解法——前后缀分解

https://leetcode.cn/problems/construct-product-matrix/solutions/2483137/zhou-sai-chang-kao-qian-hou-zhui-fen-jie-21hr/
核心思想：把矩阵想象成一维的，我们需要算出每个数左边所有数的乘积，以及右边所有数的乘积，这都可以用递推得到。

class Solution {public int[][] constructProductMatrix(int[][] grid) {final int MOD = 12345;int m = grid.length, n = grid[0].length;int[][] p = new int[m][n];long suf = 1;       // 后缀乘积for (int i = m - 1; i >= 0; --i) {for (int j = n - 1; j >= 0; --j) {p[i][j] = (int)suf;suf = suf * grid[i][j] % MOD;}}long pre = 1;       // 前缀乘积for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {p[i][j] = (int)(p[i][j] * pre % MOD);pre = pre * grid[i][j] % MOD;}}return p;}
}

相关题目——前后缀分解题单📕

见：【算法】前后缀分解题单

成绩记录

最后一题想了还久还是没做出来。。遗憾掉分