Leetcode - 146双周赛

一，3392. 统计符合条件长度为 3 的子数组数目

二，3393. 统计异或值为给定值的路径数目

三，3394. 判断网格图能否被切割成块

四，3395. 唯一中间众数子序列 I

一，3392. 统计符合条件长度为 3 的子数组数目

本题就是暴力求解，假设相邻的三个数 x，y，z，要求满足 x + z = y / 2，注意 y / 2 它表示向下取整，如果 y = 5，y / 2 = 2，这时如果 x = 1，z = 1，它会加到答案中，但是它实际上不满足条件。为避免这一情况，可以使用（x + z) * 2 == y 来进行判断或者额外判断 y % 2 == 0。

代码如下：

class Solution {public int countSubarrays(int[] nums) {int ans = 0;int n = nums.length;for(int i=0; i<n-2; i++){int a = (nums[i]+nums[i+2])*2, b = nums[i+1];if(a == b) ans++;}return ans;}
}

二，3393. 统计异或值为给定值的路径数目

本题是一道网格题，只不过多了一点要求——路径上的所有数组异或值必须为 k，也就是说在 dfs 的时候需要增加一个变量，定义 dfs(i，j，xor)：从 (i，j) 到 (m-1，n-1) 且 xor ^ 路径上的所有数字 = k 的所有路径。

向下移动一格，接下来要计算的是从 (i+1，j) 到 (m-1，n-1) 且 xor ^ grid[i][j] ^ 路径上的所有数字 = k 的所有路径，即 dfs(i+1，j，xor ^ grid[i][j])
向右移动一格，接下来要计算的是从 (i，j+1) 到 (m-1，n-1) 且 xor ^ grid[i][j] ^ 路径上的所有数字 = k 的所有路径，即 dfs(i，j+1，xor ^ grid[i][j])
结束条件是 i == m-1 && j == n-1，返回 xor == k ? 1 : 0

代码如下：

class Solution {public int countPathsWithXorValue(int[][] grid, int k) {int n = grid.length, m = grid[0].length;memo = new int[n][m][32];for(int[][] r : memo){for(int[] x : r)Arrays.fill(x, -1);}int ans = dfs(0, 0, grid[0][0], grid, k) % MOD;return ans;}int MOD = 1_000_000_007;int[][][] memo;int dfs(int i, int j, int xor, int[][] g, int k){if(i == g.length-1 && j == g[0].length-1){return xor == k ? 1 : 0;}if(memo[i][j][xor] != -1){return memo[i][j][xor];}int res = 0;if(i+1 < g.length)res = (res + dfs(i+1, j, xor^g[i+1][j], g, k)) % MOD;if(j+1 < g[0].length)res = (res + dfs(i, j+1, xor^g[i][j+1], g, k)) % MOD;return memo[i][j][xor] = res;}
}

三，3394. 判断网格图能否被切割成块

所以本题实际上是一个区间分割问题，对所有矩阵的横坐标区间和纵坐标区间分别进行划分，如果横坐标区间或者纵坐标区间可以分成 3 份及以上，返回 true，否则返回 false

代码如下：

class Solution {public boolean checkValidCuts(int n, int[][] r) {int m = r.length;int[][] col = new int[m][2];int[][] row = new int[m][2];for(int i=0; i<m; i++){col[i] = new int[]{r[i][0], r[i][2]};row[i] = new int[]{r[i][1], r[i][3]};}Arrays.sort(col, (x, y) -> x[0] - y[0]);Arrays.sort(row, (x, y) -> x[0] - y[0]);return check(col) || check(row);}boolean check(int[][] a){int ans = 0;//统计切了几刀int R = a[0][1];for(int i=1; i<a.length; i++){int l = a[i][0], r = a[i][1];if(l >= R){ans++;}R = Math.max(R, r);}return ans >= 2;}
}

四，3395. 唯一中间众数子序列 I

本题是一道排列组合题，假设众数为 X，如果直接算，需要计算 2，3，4，5 个 X 满足条件的所有组合，正难则反，如果求不满足条件的，只需要计算 1，2 个 X 不满足条件的所有组合，然后拿总数（Cn5） - 不满足条件的所有组合。反过来算相对容易一点。

题目要求众数必须在子序列的中间，所以需要枚举众数，还需要统计前缀每个数字的出现次数以及后缀每个数字的出现次数。

代码如下：

class Solution {int MOD = 1_000_000_007;public int subsequencesWithMiddleMode(int[] nums) {int n = nums.length;Map<Integer, Integer> suf = new HashMap<>();for(int x : nums){suf.merge(x, 1, Integer::sum);}Map<Integer, Integer> pre = new HashMap<>();long ans = comb(n, 5);for(int i=0; i<n-2; i++){int x = nums[i];suf.merge(x, -1, Integer::sum);if(i > 1)ans -= count(i, nums, pre, suf);pre.merge(x, 1, Integer::sum);}return (int)(ans%MOD);}long count(int i, int[] nums, Map<Integer, Integer> pre, Map<Integer, Integer> suf){int x = nums[i];int l = i;int r = nums.length - i - 1;int preX = pre.getOrDefault(x, 0);int sufX = suf.getOrDefault(x, 0);// **x**long ans = comb(l - preX, 2) * comb(r - sufX, 2);for(int y : suf.keySet()){if(x == y) continue;int sufY = suf.get(y);int preY = pre.getOrDefault(y, 0);// yy x xz => z 可以为 yans += comb(preY, 2) * sufX * (r - sufX);// zx x yy => z 可以为 yans += (l - preX) * preX * comb(sufY, 2);// xy x yz => z != yans += preX * sufY * preY * (r - sufX - sufY);// zy x yx => z != yans += (l - preX - preY) * preY * sufY * sufX;}return ans;}long comb(int x, int y){if(x == 0) return 0;long res = 1;for(int i=x; i>x-y; i--){res *= i;}for(int i=2; i<=y; i++){res /= i;}return res;}
}