🚀竞赛
统计符合条件长度为3的子数组数目
做题过程
滑动窗口即可。
算法概述
本题要求为求多少个子数组中第一个和第三个数之和为第二个数的一半。 滑动窗口 秒了。
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int countSubarrays(int[] nums) {
int l=0,r=2;
int ans=0;
while(r<nums.length){
if((float)nums[l]+nums[r]==(float)nums[(l+r)/2]/2) ans++;
l++;
r++;
}
return ans;
}
}
|
总结
要转换为浮点数避免奇数除法只取整的问题。
统计异或值为给定值的路径数目
做题过程
使用了深度优先搜索遍历所有路径，使用了哈希表进行记忆化搜索剪枝优化，但是时间还是超了。因为哈希集合的查找开销还是高，即使是常数（毕竟是hash🥔）。
算法概述
本题要求位路径上所有值的异或值必须为给定值，统计符合要求的路径数。采用灵神的解法，用 动态规划 替代散列集。
- 时间复杂度为O(m*n*u)：u是最大的异或值范围，最坏情况下范围内每个异或值都可能出现
- 空间复杂度为O(m*n*u)：dp数组
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
private static final int MOD = 1_000_000_007;
public int countPathsWithXorValue(int[][] grid, int k) {
int mx = 0;
for (int[] row : grid) {
for (int val : row) {
mx = Math.max(mx, val);
}
}
int u = 1 << (32 - Integer.numberOfLeadingZeros(mx));
if (k >= u) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int[][][] memo = new int[m][n][u];
for (int[][] mat : memo) {
for (int[] row : mat) {
Arrays.fill(row, -1);
}
}
return dfs(grid, m - 1, n - 1, k, memo);
}
private int dfs(int[][] grid, int i, int j, int x, int[][][] memo) {
if (i < 0 || j < 0) {
return 0;
}
int val = grid[i][j];
if (i == 0 && j == 0) {
return x == val ? 1 : 0;
}
if (memo[i][j][x] != -1) {
return memo[i][j][x];
}
int left = dfs(grid, i, j - 1, x ^ val, memo);
int up = dfs(grid, i - 1, j, x ^ val, memo);
return memo[i][j][x] = (left + up) % MOD;
}
}
|
重要实例方法及属性(JAVA)
Integer.numberOfLeadingZeros(mx)：计算前导0的数量<<1：生成一个2的幂次方的数字int u = 1 << (32 - Integer.numberOfLeadingZeros(mx));：计算异或值的最大范围
总结
重要😠 ：
- 哈希集合的常数时间 不如 记忆化搜索！
- 逆序搜索更易于处理边界，在其他类型的题目中(e.g., 符合条件的路径)还能剪枝
- 用 要求条件的最大值 作为多维动态规划的 第三维 ！
判断网格图能否被切割成块
算法概述
本题要求为在只能横着且两刀或者竖着切两刀的情况下，能不能使图中的矩形只属于一个分区。可以转换为“合并区间”问题，参考灵神解法。
- 时间复杂度为O(mlogm)：排序
- 空间复杂度为O(m)
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
boolean checkValidCuts(int n, int[][] rectangles) {
int m = rectangles.length;
int[][] a = new int[m][2];
int[][] b = new int[m][2];
for (int i = 0; i < m; i++) {
int[] rect = rectangles[i];
a[i][0] = rect[0];
a[i][1] = rect[2];
b[i][0] = rect[1];
b[i][1] = rect[3];
}
return check(a) || check(b);
}
private boolean check(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int cnt = 0;
int maxR = 0;
for (int[] interval : intervals) {
if (interval[0] >= maxR) {
cnt++;
}
maxR = Math.max(maxR, interval[1]);
}
return cnt >= 3;
}
}
|
总结
早说不做第二题，做第三题了。
唯一中间众数子序列 I
算法概述
本题要求为求出有多少个唯一中间众数子序列（子序列：指的是将一个数组删除一些（也可以不删除）元素后，剩下元素不改变顺序得到的非空数组），规定长度为5。参考灵神，这道题偏数学。
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
public int subsequencesWithMiddleMode(int[] nums) {
int n = nums.length;
long ans = (long) n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 120;
Map<Integer, Integer> suf = new HashMap<>();
for (int x : nums) {
suf.merge(x, 1, Integer::sum);
}
Map<Integer, Integer> pre = new HashMap<>(suf.size());
for (int left = 0; left < n - 2; left++) {
int x = nums[left];
suf.merge(x, -1, Integer::sum);
if (left > 1) {
int right = n - 1 - left;
int preX = pre.getOrDefault(x, 0);
int sufX = suf.get(x);
ans -= (long) comb2(left - preX) * comb2(right - sufX);
for (Map.Entry<Integer, Integer> e : suf.entrySet()) {
int y = e.getKey();
if (y == x) {
continue;
}
int sufY = e.getValue();
int preY = pre.getOrDefault(y, 0);
ans -= (long) comb2(preY) * sufX * (right - sufX);
ans -= (long) comb2(sufY) * preX * (left - preX);
ans -= (long) preY * sufY * preX * (right - sufX - sufY);
ans -= (long) preY * sufY * sufX * (left - preX - preY);
}
}
pre.merge(x, 1, Integer::sum);
}
return (int) (ans % 1_000_000_007);
}
private int comb2(int num) {
return num * (num - 1) / 2;
}
}
|
总结
后面再回头看，这道题偏数学不偏算法。
