文章目录
1. 删除并获得点数
题干:
一个整数数组 nums
选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数
删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素
返回获得的最大点数
算法原理:
预处理:将数组中的数,统计到 arr 中
arr[i] 表示:i 这个数字出现的总和
1. 状态表示:
f[i] 表示:选到 i 位置时,选 nums[i],此时能获得的最大点数
g[i] 表示:选到 i 位置时,不选 nums[i],此时能获得的最大点数
2. 状态转移方程
f[i] = g[i - 1] + nums[i]
g[i] = max(f[i - 1], g[i- 1])
3. 初始化
f[0] = nums[0]
g[0] = 0
4. 填表顺序
从左往右,两个表⼀起填
5. 返回值
max(f[n - 1], g[n - 1])
代码:
class Solution {
public int deleteAndEarn(int[] nums) {
int n = 10001;
int[] arr = new int[n];
for(int x : nums) {
arr[x] += x;
}
int[] f = new int[n];
int[] g = new int[n];
f[0] = arr[0];
for(int i = 1; i < n; i++) {
f[i] = g[i - 1] + arr[i];
g[i] = Math.max(f[i - 1], g[i - 1]);
}
return Math.max(f[n - 1], g[n - 1]);
}
}
2. 连续数组
题干:
二进制数组 nums
含有相同数量的 0 和 1 的最长连续子数组
返回该子数组的长度
算法原理:(前缀和 + 哈希表)
转化:
- 将所有的 0 修改成 -1
- 在数组中,找出最长子数组,使数组为 0
接下来就按照 和为 K 的子数组 的方法来写
引入 以 i 为结尾的所有的子数组
这样就可以转化为:
在 [0,i-1] 区间内,有多少个前缀和 等于 sum[i] - k
这样就可以使用哈希表 <int,int>
细节问题:
- 哈希表中存什么?
hash<int, int>
第一个 int:前缀和
第二个 int:下标 - 前缀和加入哈希表的时机
使用完之后,放入哈希表 - 如果有重复的<sum, i>,如何处理
只保留前面的那一对<sum, i> - 默认的前缀和为 0 的情况,如何存
hash[0] = -1; - 长度怎么算?
i - j + i - 1 = i - j
代码:
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
hash.put(0, -1);//默认存在一个前缀和为 0 的情况
int sum = 0;
int ret = 0;
for(int i = 0; i < nums.length; i++) {
sum += (nums[i] == 0 ? -1 : 1);//计算当前位置的前缀和
if(hash.containsKey(sum)) {
ret = Math.max(ret, i - hash.get(sum));
}else {
hash.put(sum, i);
}
}
return ret;
}
}
3. 矩阵区域和
题干:
一个 m x n 的矩阵 mat
一个整数 k
返回一个矩阵 answer
answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:
i - k <= r <= i + k,j - k <= c <= j + k 且 (r, c) 在矩阵内
算法原理:(二维前缀和)
(1)求ans[i][j]
左上⻆坐标: x1 = i - k,y1 = j - k ,但是由于会「超过矩阵」的范围,因此需要对 0 取⼀个 max
(2)下标的映射关系
所以dp[i][j] = dp[i-1][j] +dp[i][j-1] - dp[i-1][j-1] +arr[i+1][j+1]
上面求 ans[i][j] 的时候 后面 +1
代码:
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
//1.预处理前缀和矩阵
int[][] dp = new int[m + 1][n + 1];
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j -1] + mat[i - 1][j - 1];
}
}
//2.使用
int[][] ret = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int x1 = Math.max(0, i - k) + 1;
int y1 = Math.max(0, j - k) + 1;
int x2 = Math.min(m - 1, i + k) + 1;
int y2 = Math.min(n - 1, j + k) + 1;
ret[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
}
}
return ret;
}
}