740. 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
1
2
3
4
5
|
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
|
示例 2：
1
2
3
4
5
6
|
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
|
提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104
这一题很迷惑人，什么“每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。”这都是些什么鬼操作。绕了我那么久，实际上就是打家劫舍。
不能连着获得两个挨着的点数。
打家劫舍中，挨着的是数组，nums[1]和nums[2]不能同时存在；这一题中，nums[x]+1和nums[x]不能同时存在，怎么办呢？
可以把点数映射到另一个数组中，比如 1 1 3 3 3 4 6 8 8 10这9个数，稍微处理一下
| 值 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 个数 |
2 |
0 |
3 |
1 |
0 |
1 |
0 |
2 |
0 |
1 |
这样就变成了打家劫舍的题目了，不能同时存在相邻的值
dp[i]=Math.max(dp[i-2]+a[i]*i,dp[i-3]+a[i]*i);
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
|
public static int deleteAndEarn(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
} else if (nums.length == 1) {
return nums[0];
}else if(nums.length==2){
if(nums[1]==nums[0]){
return 2*nums[0];
}else if(nums[0]-nums[1]==1||nums[0]-nums[1]==-1){
return Math.max(nums[1],nums[0]);
}
return nums[1]+nums[0];
}
Arrays.sort(nums);
int n=nums.length;
int maxnum=nums[n-1];
int []a=new int[maxnum+1];
for(int i=0;i<n;i++){
a[nums[i]]++;
}
int []dp=new int[maxnum+1];
System.out.println(Arrays.toString(a));
dp[1]=a[1]*1;
dp[2]=a[2]*2;
dp[3]=a[3]*3+dp[1];
for(int i=3;i<=maxnum;i++){
dp[i]=Math.max(dp[i-2]+a[i]*i,dp[i-3]+a[i]*i);
}
System.out.println(Arrays.toString(dp));
return Math.max(dp[maxnum-1],dp[maxnum]);
}
|