100096. Find Indices With Index and Value Difference 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 可能 相等 。
测试样例：
输入：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] 也是符合题目要求的答案。
解答：这道题目和第三题一样，这次就贴一题了。优化的方案是寻找符合条件的，之前数字符合indexDifference中的最小和最大值，能够满足valueDifference条件就输出。最大和最小值可以利用红黑树（Java里面就是TreeMap了）。
class Solution {
private static final int[] invalid = {-1, -1};
public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < nums.length; ++i) {
if (i >= indexDifference) {
map.put(nums[i - indexDifference], i - indexDifference);
}
if (!map.isEmpty()) {
Map.Entry<Integer, Integer> first = map.firstEntry(), last = map.lastEntry();
if (Math.abs(nums[i] - first.getKey()) >= valueDifference) {
return new int[]{first.getValue(), i};
}
if (Math.abs(nums[i] - last.getKey()) >= valueDifference) {
return new int[]{last.getValue(), i};
}
}
}
return invalid;
}
}100084. Shortest and Lexicographically Smallest Beautiful String
给你一个二进制字符串 s 和一个正整数 k 。
如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。
令 len 等于 最短 美丽子字符串的长度。
返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。
对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。
- 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。
测试样例：
输入：s = "1011", k = 2
输出：“11”
解释：
示例中共有 3 个美丽子字符串：
- 子字符串 "1011" 。
- 子字符串 "1011" 。
- 子字符串 "1011" 。
最短美丽子字符串的长度是 2 。长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。
解答：这道题目其实可以用双指针，但是s.length <= 100，我就直接用暴力算法了，编写比较简单。
class Solution {
public String shortestBeautifulSubstring(String s, int k) {
String result = "";
for (int i = 0; i < s.length(); ++i) {
for (int j = i; j < s.length(); ++j) {
String sub = s.substring(i, j + 1);
if (isValid(sub, k)) {
if (result.length() == 0) {
result = sub;
} else if (result.length() > sub.length()) {
result = sub;
} else if (result.length() == sub.length() && result.compareTo(sub) > 0) {
result = sub;
}
}
}
}
return result;
}
private boolean isValid(String sub, int k) {
int count = 0;
for (int i = 0; i < sub.length(); ++i) {
if (sub.charAt(i) == '1') {
++count;
}
}
return count == k;
}
}8026. Construct Product Matrix
给你一个下标从 0 开始、大小为 n m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：
- 对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。
返回 grid 的乘积矩阵。
测试样例
输入：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]] 。
解答：这道题目其实蛮讨厌的。因为n * m最大可以是100000，直接暴力运算肯定是不行的，但是12345这个mod也不能用乘法逆元。为了能完成计算，能想到的就是分组。把这些数分为长度350的region，最多就是285个region。这样每个数的计算可以分成当前region中的数和非当前region group结果的取余。这样可以大幅度减少计算复杂度。
class Solution {
private static final int mod = 12345, region = 350;
public int[][] constructProductMatrix(int[][] grid) {
int n = grid.length, m = grid[0].length, max = (n - 1) * m + m - 1;
int[][] res = new int[n][m];
List<Integer> regionMul = new ArrayList<>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
grid[i][j] %= mod;
int key = i * m + j, regionNum = key / region;
if (regionNum == regionMul.size()) {
regionMul.add(1);
}
int last = regionMul.get(regionNum);
last = (last * grid[i][j]) % mod;
regionMul.set(regionNum, last);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
grid[i][j] %= mod;
int key = i * m + j, regionNum = key / region;
int regionSt = regionNum * region, regionEd = Math.min(max, regionNum * region + region - 1);
int result = 1;
for (int k = 0; k < regionMul.size(); ++k) {
if (k != regionNum) {
result = (result * regionMul.get(k)) % mod;
}
}
for (int k = regionSt; k <= regionEd; ++k) {
int x = k / m, y = k % m;
if (x != i || y != j) {
result = (result * grid[x][y]) % mod;
}
}
res[i][j] = result;
}
}
return res;
}
}昨天的双周赛真的是好难，做不来。这周周赛倒是手速场挺容易的。