欢迎大家加QQ群：623375442，可以方便群里面交流。这周发烧了，比赛后四天补一下周赛和双周赛的题解。
3392. Count Subarrays of Length Three With a Condition
给你一个整数数组 nums ，请你返回长度为 3 的 子数组，满足第一个数和第三个数的和恰好为第二个数的一半。
子数组 指的是一个数组中连续 非空 的元素序列。
测试样例：
输入：nums = [1,2,1,4,1]
输出：1
解释：只有子数组 [1,4,1] 包含 3 个元素且第一个和第三个数字之和是中间数字的一半。
解答：按照题意，暴力计算。
class Solution {
public int countSubarrays(int[] nums) {
int res = 0;
for (int i = 2; i < nums.length; ++i) {
int sum = nums[i] + nums[i - 2];
if (sum * 2 == nums[i - 1]) ++res;
}
return res;
}
}3393. Count Paths With the Given XOR Value
给你一个大小为 m x n 的二维整数数组 grid 和一个整数 k 。
你的任务是统计满足以下 条件 且从左上格子 (0, 0) 出发到达右下格子 (m - 1, n - 1) 的路径数目：
- 每一步你可以向右或者向下走，也就是如果格子存在的话，可以从格子 (i, j) 走到格子 (i, j + 1) 或者格子 (i + 1, j) 。
- 路径上经过的所有数字 XOR 异或值必须 等于 k 。
请你返回满足上述条件的路径总数。
由于答案可能很大，请你将答案对 10^9 + 7 取余 后返回。
测试样例：
输入：grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11
输出：3
解释：3 条路径分别为：
- (0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2)
- (0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2)
- (0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)
解答：典型动态规划题目。
class Solution {
private static final int mod = 1_000_000_007;
private static final int[] empty = new int[16];
public int countPathsWithXorValue(int[][] grid, int k) {
int n = grid[0].length;
int[][] last = new int[n][16];
last[0][0] = 1;
for (int[] r : grid) {
int[][] cur = new int[n][16];
for (int i = 0; i < n; ++i) {
int[] pre = i == 0 ? empty : cur[i - 1];
for (int j = 0; j < 16; ++j) {
cur[i][j ^ r[i]] = (pre[j] + last[i][j]) % mod;
}
}
last = cur;
}
return last[n - 1][k];
}
}3394. Check if Grid can be Cut into Sections
给你一个整数 n 表示一个 n x n 的网格图，坐标原点是这个网格图的左下角。同时给你一个二维坐标数组 rectangles ，其中 rectangles[i] 的格式为 [startx, starty, endx, endy] ，表示网格图中的一个矩形。每个矩形定义如下：
- (startx, starty)：矩形的左下角。
- (endx, endy)：矩形的右上角。
注意 ，矩形相互之间不会重叠。你的任务是判断是否能找到两条 要么都垂直要么都水平 的 两条切割线 ，满足：
- 切割得到的三个部分分别都 至少 包含一个矩形。
- 每个矩形都 恰好仅 属于一个切割得到的部分。
如果可以得到这样的切割，请你返回 true ，否则返回 false 。
测试样例：
输入：n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]
输出：true
解释：我们可以在 y = 2 和 y = 4 处进行水平切割，所以返回 true 。
解答：排序之后分解。
class Solution {
public boolean checkValidCuts(int n, int[][] rectangles) {
List<int[]> x = new ArrayList<>(), y = new ArrayList<>();
for (int[] rect : rectangles) {
x.add(new int[]{rect[0], rect[2]});
y.add(new int[]{rect[1], rect[3]});
}
return isValid(x) || isValid(y);
}
private boolean isValid(List<int[]> list) {
Collections.sort(list, (a, b) -> (Integer.compare(a[0], b[0])));
int[] pre = null;
int res = 0;
for (int[] t : list) {
if (pre == null || t[0] >= pre[1]) {
++res;
pre = new int[]{t[0], t[1]};
} else {
pre[1] = Math.max(pre[1], t[1]);
}
}
return res >= 3;
}
}3395. Subsequences with a Unique Middle Mode I
给你一个整数数组 nums ，请你求出 nums 中大小为 5 的 子序列的数目，它是 唯一中间众数序列 。
由于答案可能很大，请你将答案对 10^9 + 7 取余 后返回。
众数 指的是一个数字序列中出现次数 最多 的元素。
如果一个数字序列众数只有一个，我们称这个序列有 唯一众数 。
一个大小为 5 的数字序列 seq ，如果它中间的数字（seq[2]）是唯一众数，那么称它是 唯一中间众数 序列。
测试样例：
输入：nums = [1,1,1,1,1,1]
输出：6
[1, 1, 1, 1, 1] 是唯一长度为 5 的子序列。1 是它的唯一中间众数。有 6 个这样的子序列，所以返回 6 。
解答：这题确实挺难的。我是计算了总共可能的情况。包括当前数出现次数分别是2，3，4和5.出现2次比较复杂，可能会有2个数出现2次，导致不是众数，需要额外去除。
class Solution {
private static final Combination combine = new Combination(1000);
private static final int mod = 1_000_000_007;
public int subsequencesWithMiddleMode(int[] nums) {
HashMap<Integer, Integer> rightMap = new HashMap<>();
for (int n : nums) {
rightMap.put(n, rightMap.getOrDefault(n, 0) + 1);
}
List<Integer> distinct = new ArrayList<>(rightMap.keySet());
long res = 0;
HashMap<Integer, Integer> leftMap = new HashMap<>();
int left = 0, right = nums.length;
for (int i = 0; i < nums.length - 2; ++i) {
rightMap.put(nums[i], rightMap.getOrDefault(nums[i], 0) - 1);
--right;
if (left >= 2) {
int lc = leftMap.getOrDefault(nums[i], 0), rc = rightMap.getOrDefault(nums[i], 0);
if (lc >= 1) {
long tmp = combine.getCombine(lc, 1)
* (combine.getCombine(left - lc, 1) * combine.getCombine(right - rc, 2)
- removeWrong(leftMap, rightMap, distinct, nums[i], left, right) + mod) % mod;
res = (res + tmp) % mod;
}
if (rc >= 1) {
long tmp = combine.getCombine(rc, 1)
* (combine.getCombine(left - lc, 2) * combine.getCombine(right - rc, 1)
- removeWrong(rightMap, leftMap, distinct, nums[i], right, left) + mod) % mod;
res = (res + tmp) % mod;
}
if (lc >= 1 && rc >= 1) {
long tmp = combine.getCombine(lc, 1) * combine.getCombine(rc, 1) % mod;
tmp = tmp * combine.getCombine(left - lc, 1) % mod;
tmp = tmp * combine.getCombine(right - rc, 1) % mod;
res = (res + tmp) % mod;
}
if (lc >= 2) {
long tmp = combine.getCombine(lc, 2) * combine.getCombine(right - rc, 2) % mod;
res = (res + tmp) % mod;
}
if (rc >= 2) {
long tmp = combine.getCombine(rc, 2) * combine.getCombine(left - lc, 2) % mod;
res = (res + tmp) % mod;
}
if (lc >= 2 && rc >= 1) {
long tmp = combine.getCombine(lc, 2) * combine.getCombine(right - rc, 1) % mod * combine.getCombine(rc, 1);
res = (res + tmp) % mod;
}
if (lc >= 1 && rc >= 2) {
long tmp = combine.getCombine(rc, 2) * combine.getCombine(left - lc, 1) % mod * combine.getCombine(lc, 1);
res = (res + tmp) % mod;
}
if (lc >= 2 && rc >= 2) {
long tmp = combine.getCombine(lc, 2) * combine.getCombine(rc, 2) % mod;
res = (res + tmp) % mod;
}
}
leftMap.put(nums[i], leftMap.getOrDefault(nums[i], 0) + 1);
++left;
}
return (int)res;
}
private long removeWrong(HashMap<Integer, Integer> map1, HashMap<Integer, Integer> map2, List<Integer> all, int num, int left, int right) {
long sum = 0;
for (Integer k : all) {
if (k == num) continue;
if (map1.getOrDefault(k, 0) >= 1 && map2.getOrDefault(k, 0) >= 2) {
sum += combine.getCombine(map1.get(k), 1) * combine.getCombine(map2.get(k), 2);
sum %= mod;
}
if (map2.getOrDefault(k, 0) >= 2) {
sum += combine.getCombine(left - map1.getOrDefault(k, 0) - map1.getOrDefault(num, 0), 1) * combine.getCombine(map2.get(k), 2);
sum %= mod;
}
if (map1.getOrDefault(k, 0) >= 1 && map2.getOrDefault(k, 0) >= 1) {
sum += combine.getCombine(map1.get(k), 1) * combine.getCombine(map2.get(k), 1) % mod * combine.getCombine(right - map2.get(k) - map2.getOrDefault(num, 0), 1);
sum %= mod;
}
}
return sum;
}
}
class Combination {
private long[][] combine;
private static final int mod = 1_000_000_007;
public Combination(int len) {
combine = new long[len + 1][len + 1];
combine[0][0] = 1;
for (int i = 1; i <= len; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
combine[i][j] = 1;
} else {
combine[i][j] = (combine[i - 1][j] + combine[i - 1][j - 1]) % mod;
}
}
}
}
public long getCombine(int n, int c) {
return combine[n][c];
}
}3396. Minimum Number of Operations to Make Elements in Array Distinct
给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：
- 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。
注意：空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。
测试样例：
输入：nums = [1,2,3,4,2,3,3,5,7]
输出：2
解释：
- 第一次操作：移除前 3 个元素，数组变为 [4, 2, 3, 3, 5, 7]。
- 第二次操作：再次移除前 3 个元素，数组变为 [3, 5, 7]，此时数组中的元素互不相同。
因此，答案是 2。
解答：按照题意，暴力计算。
class Solution {
public int minimumOperations(int[] nums) {
HashMap<Integer, Integer> set = new HashMap<>();
int max = -1;
for (int i = 0; i < nums.length; ++i) {
if (set.containsKey(nums[i])) max = Math.max(set.get(nums[i]), max);
set.put(nums[i], i + 1);
}
if (max == -1) return 0;
return max / 3 + (max % 3 == 0 ? 0 : 1);
}
}3397. Maximum Number of Distinct Elements After Operations
给你一个整数数组 nums 和一个整数 k。
你可以对数组中的每个元素 最多 执行 一次 以下操作：
- 将一个在范围 [-k, k] 内的整数加到该元素上。
返回执行这些操作后，nums 中可能拥有的不同元素的 最大 数量。
测试样例：
输入：nums = [1,2,2,3,3,4], k = 2
输出：6
解释：对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。
解答：遍历暴力计算。
class Solution {
public int maxDistinctElements(int[] nums, int k) {
Arrays.sort(nums);
int last = Integer.MIN_VALUE;
int res = 0;
for (int n : nums) {
if (n - k > last) {
last = n - k;
++res;
} else if (n + k > last) {
last = last + 1;
++res;
}
}
return res;
}
}3399. Smallest Substring With Identical Characters II
给你一个长度为 n 的二进制字符串 s 和一个整数 numOps。
你可以对 s 执行以下操作，最多 numOps 次：
- 选择任意下标 i（其中 0 <= i < n），并 翻转 s[i]，即如果 s[i] == '1'，则将 s[i] 改为 '0'，反之亦然。
你需要 最小化 s 的最长 相同 子字符串 的长度，相同子字符串是指子字符串中的所有字符都相同。
返回执行所有操作后可获得的 最小 长度。
测试样例：
输入：s = "000001", numOps = 1
输出：2
解释：将 s[2] 改为 '1'，s 变为 "001001"。最长的所有字符相同的子串为 s[0..1] 和 s[3..4]。
解答：这题难度不大。别忘了算长度为1的情况。
class Solution {
public int minLength(String s, int numOps) {
if (oneLengthCost(s, 0) <= numOps || oneLengthCost(s, 1) <= numOps) return 1;
List<Integer> seq = new ArrayList<>();
int st = 0;
for (int i = 1; i <= s.length(); ++i) {
if (i == s.length() || s.charAt(i) != s.charAt(i - 1)) {
seq.add(i - st);
st = i;
}
}
st = 2; int ed = s.length();
while (st < ed) {
int mid = (st + ed) / 2;
if (isValid(seq, numOps, mid)) {
ed = mid;
} else {
st = mid + 1;
}
}
return st;
}
private int oneLengthCost(String s, int start) {
int res = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) - '0' != start) ++res;
start ^= 1;
}
return res;
}
private boolean isValid(List<Integer> seq, int numsOps, int target) {
for (int n : seq) {
if (n > target) {
numsOps -= n / (target + 1);
if (numsOps < 0) return false;
}
}
return true;
}
}