本文主要是介绍周赛367（模拟、枚举 + 有序哈希、同向双指针、前后缀分解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 周赛367
- [2903. 找出满足差值条件的下标 I](https://leetcode.cn/problems/find-indices-with-index-and-value-difference-i/)
- 模拟
- [2904. 最短且字典序最小的美丽子字符串](https://leetcode.cn/problems/shortest-and-lexicographically-smallest-beautiful-string/)
- 枚举
- 同向双指针
- [2905. 找出满足差值条件的下标 II](https://leetcode.cn/problems/find-indices-with-index-and-value-difference-ii/)
- 枚举 + 有序哈希
- [2906. 构造乘积矩阵](https://leetcode.cn/problems/construct-product-matrix/)
- 前后缀分解
- [238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/)
周赛367
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 可能 相等 。
示例 1：
输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。
示例 2：
输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。
因此，[0,0] 是一个符合题目要求的答案。
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。
示例 3：
输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。
提示：
1 <= n == nums.length <= 1000 <= nums[i] <= 500 <= indexDifference <= 1000 <= 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(Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference)return new int[]{i, j};}}return new int[]{-1, -1};}
}
2904. 最短且字典序最小的美丽子字符串
中等
给你一个二进制字符串 s 和一个正整数 k 。
如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。
令 len 等于 最短 美丽子字符串的长度。
返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。
对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。
- 例如，
"abcd"的字典序大于"abcc"，因为两个字符串出现不同的第一个位置对应第四个字符，而d大于c。
示例 1：
输入：s = "100011001", k = 3
输出："11001"
解释：示例中共有 7 个美丽子字符串：
1. 子字符串 "100011001" 。
2. 子字符串 "100011001" 。
3. 子字符串 "100011001" 。
4. 子字符串 "100011001" 。
5. 子字符串 "100011001" 。
6. 子字符串 "100011001" 。
7. 子字符串 "100011001" 。
最短美丽子字符串的长度是 5 。
长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。
示例 2：
输入：s = "1011", k = 2
输出："11"
解释：示例中共有 3 个美丽子字符串：
1. 子字符串 "1011" 。
2. 子字符串 "1011" 。
3. 子字符串 "1011" 。
最短美丽子字符串的长度是 2 。
长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。
示例 3：
输入：s = "000", k = 1
输出：""
解释：示例中不存在美丽子字符串。
提示：
1 <= s.length <= 1001 <= k <= s.length
枚举
class Solution {public String shortestBeautifulSubstring(String s, int k) {// 1 的个数不足 kif (s.replace("0", "").length() < k) {return "";}// 否则一定有解for (int size = k; ; size++) {String ans = "";for (int i = size; i <= s.length(); i++) {String t = s.substring(i - size, i);if ((ans.isEmpty() || t.compareTo(ans) < 0) && t.replace("0", "").length() == k) {ans = t;}}if (!ans.isEmpty()) {return ans;}}}
}
同向双指针
class Solution {public String shortestBeautifulSubstring(String s, int k) {int cnt1 = 0;// 统计字符串s中1的个数，若大于k，则一定有答案for(char c : s.toCharArray()) if(c == '1') cnt1 += 1;if(cnt1 < k) return "";cnt1 = 0;String res = s;int minlen = Integer.MAX_VALUE;int left = 0, right = 0;// 枚举右端点，缩小左端点for(; right < s.length(); right++){if(s.charAt(right) == '1')cnt1 += 1;while(cnt1 > k){if(s.charAt(left) == '1')cnt1 -= 1;left += 1;}// 即使排除s[left]=0 的合法情况，确保当前字符串长度最小while(cnt1 == k && s.charAt(left) == '0')left += 1;if(cnt1 == k && minlen >= (right - left + 1)){if(minlen == right - left + 1)res = s.substring(left, right + 1).compareTo(res) < 0 ? s.substring(left, right + 1) : res;else{minlen = right - left + 1;res = s.substring(left, right + 1);}}}return res;}
}
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 可能 相等 。
示例 1：
输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。
示例 2：
输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。
因此，[0,0] 是一个符合题目要求的答案。
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。
示例 3：
输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。
提示：
1 <= n == nums.length <= 1050 <= nums[i] <= 1090 <= indexDifference <= 1050 <= valueDifference <= 109
枚举 + 有序哈希
class Solution {/**i - j >= indexDifi >= indexDif + j从小到大枚举iabs(nums[i] - nums[j]) >= valDiffnums[i] - nums[j] >= valDiff or nums[i] - nums[j] <= -valDiffnums[i] >= valDiff + nums[j]nums[i] <= -valDiff + nums[j]*/public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {int n = nums.length;if(n == 1){if(indexDifference == 0 && valueDifference == 0)return new int[]{0, 0};return new int[]{-1, -1};}TreeMap<Integer, Integer> map = new TreeMap<>();for(int i = indexDifference; i < n; i++){// 将窗口外的值i - indexDifference放入treemap中此时满足i - j >= indexDif条件map.put(nums[i - indexDifference], i - indexDifference);// 查看另外一个条件是否满足if(map.floorEntry(nums[i] - valueDifference) != null)return new int[]{map.floorEntry(nums[i] - valueDifference).getValue(), i};if(map.ceilingEntry(nums[i] + valueDifference) != null)return new int[]{map.ceilingEntry(nums[i] + valueDifference).getValue(), i};}return new int[]{-1, -1};}
}
2906. 构造乘积矩阵
中等
给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：
- 对于每个元素
p[i][j]，它的值等于除了grid[i][j]外所有元素的乘积。乘积对12345取余数。
返回 grid 的乘积矩阵。
示例 1：
输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。
示例 2：
输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。
提示：
1 <= n == grid.length <= 1051 <= m == grid[i].length <= 1052 <= n * m <= 1051 <= grid[i][j] <= 109
前后缀分解
class Solution {// 同238 前后缀分解，把二维数组看成一维数组private static final int MOD = 12345;public int[][] constructProductMatrix(int[][] grid) {int n = grid.length, m = grid[0].length;int[][] res = new int[n][m];long suf = 1; // 后缀乘积for(int i = n-1; i >= 0; i--){for(int j = m-1; j >= 0; j--){res[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++){res[i][j] = (int)(res[i][j] * pre % MOD);pre = pre * grid[i][j] % MOD;}}return res;}
}
238. 除自身以外数组的乘积
中等
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(*n*) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
class Solution {/**第 i 位的乘积 = [0:i]的乘积 * [i+1:]的乘积==> 前后缀分解*/public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] suf = new int[n+1];suf[n] = 1;for(int i = n-1; i >= 0; i--){suf[i] = suf[i+1] * nums[i];}int pre = 1;int[] res = new int[n];for(int i = 0; i < n; i++){res[i] = pre * suf[i+1];pre *= nums[i];}return res;}
}
空间优化
class Solution {/**第 i 位的乘积 = [0:i]的乘积 * [i+1:]的乘积==> 前后缀分解枚举后缀的时候直接记到答案数组里*/public int[] productExceptSelf(int[] nums) {int n = nums.length;int suf = 1;int[] res = new int[n];for(int i = n-1; i >= 0; i--){res[i] = suf;suf *= nums[i];}int pre = 1;for(int i = 0; i < n; i++){res[i] = pre * res[i];pre *= nums[i];}return res;}
}
这篇关于周赛367（模拟、枚举 + 有序哈希、同向双指针、前后缀分解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
