【力扣周赛】第 367 场周赛（⭐二维数组当成一维数组，前后缀分解）

数组当成一维数组，前后缀分解）"/>

【力扣周赛】第 367 场周赛（⭐二维数组当成一维数组，前后缀分解）

文章目录

• 竞赛链接
• Q1：100096. 找出满足差值条件的下标 I
• • 竞赛时代码——暴力双循环
• Q2：100084. 最短且字典序最小的美丽子字符串
• • 竞赛时代码——双指针
• Q3：100101. 找出满足差值条件的下标 II
• • 竞赛时代码——记录可用最大最小值下标
• Q4：8026. 构造乘积矩阵⭐（重要思想：把二维数组当成一维的）
• • 解法——前后缀分解
  • 相关题目——前后缀分解题单📕
• 成绩记录

竞赛链接

/

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

/

提示：
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. 最短且字典序最小的美丽子字符串

/

提示：
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

/

提示：
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. 构造乘积矩阵⭐（重要思想：把二维数组当成一维的）

/

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

解法——前后缀分解

/
核心思想：把矩阵想象成一维的，我们需要算出每个数左边所有数的乘积，以及右边所有数的乘积，这都可以用递推得到。

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;}
}

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

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

成绩记录

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