规范数据#

1
nums = [2,5,2,7,3,3,5,3,4,5];

现在我们就获得了一个拥有列表元素和的地图了，我们对这组数据的处理还不够

题目要求我们每次选一个数就得把其相邻的所欲元素删去，就比如说，你选择了3，就得把列表里所有的2与4删了

我们想，删除相邻的数有什么好方法吗，还真有，把数组排序，排序后，每个数的旁边就是与其最接近的数，至于如果两个在列表相邻的数实际不相邻，写个逻辑判断就行了吧

1
//sort接受的第一个参数代表排序开始的地方，第二个代表排序结束的地方
2
sort(nums.begin(),nums.end());
3
//nums.begin()返回数组开头，nums.end()返回数组结尾
4
//值得注意的是，大多数时候sort()就只有这一种用法

这样我们就获得了一个排好序的数组，下例

1
nums = [2,2,3,3,3,4,5,5,5,7];

我们发现现在相同的数都连在一起了，并且题目中说拿走一个数，不会删除其他的那个数，也就是我们可以拿走所有同样的数

所以对于相同的数，我们要全部拿走，所以我们就可以把相同的数和起来算，以便我们的计算

1
map<int,int> add;
2
//map类型数据，给定一个键可以返回一个值，与python中的字典同理，可以理解为一个非常大的数组
3
        for(int i = 0;i < size(nums);i++){
4
            add[nums[i]] += nums[i];
5
      //在add的第nums[i]项加上nums[i]，求得列表中同一元素的和
6
        }

但是这还不够，我们把列表中的数加到一起了，但列表里数的的总量没有变，我们希望这些数都只计算一次，所以我们要给数去重

1
map<int,int> add;
2
add[nums[0]] = nums[0];//为后面的代码做让步
3
vector<int> new_nums;//新数组，用来存储去重后变量
4
new_nums.push_back(nums[0]);//为后面的代码做让步
5
for(int i = 1;i < size(nums);i++){
6
            add[nums[i]] += nums[i];
7
      if(nums[i] != nums[i-1]){
8
        new_nums.push_back(nums[0]);
9
      }
10
      //这里如果从0开始的话，数组就会越界，所以从1开始，第2、4行的让步也是为了这个
11
        }

这样我们就得到了一个去重并排过序的新数组了，唯一剩的就是逻辑处理部分了

1
new_nums = [2,3,4,5,7];

逻辑处理#

这道题的逻辑部分很循规蹈矩，就是一般的动态规划算法——从局部到整体

我们先从局部看起——先看前2项

1
new_nums = [2,3];

前三项的最优拿法是什么呢，因为我们是人，我们可以直接看出来——拿3，但机器可不能直接看出来，需要我们推导出来公式供其使用

所以我们来分析一下，这里有两种可能

1. 拿第1项 总点数=2
2. 拿第2项 总点数=3

看起来很简单，加到3项试试

1
new_nums = [2,3,4];

1. 拿第1、3项 总点数=2+4=6
2. 拿第2项 总点数=3

加到4项

1
new_nums = [2,3,4,5];

1. 拿第1、4项 总点数=2+5=7
2. 拿第2、4项 总点数=3+5=9
3. 拿第1、3项 总点数=2+4=6

这里我们发现拿了第4项之后要在1-2项之间找最大的拿才能获得大数，我们注意到1、2项的最大项我们之前找过，现在可以如果服用的话可以减少一种可能

我们定义一个数组，用来存储之前计算的结果，就取名叫MAX

1
vector<int> MAX={new_nums[0]};
2
//前1项的最大值一定为第1项，因为只有第1项参与计算

这个数组MAX之前计算出的最大值，例如MAX[1] = 3，MAX[2] = 6

有了这个数组之后我们再回看new_nums的前4项

1. 拿第4项和MAX[1] 总点数= 3 + 5 = 9
2. 拿第1、3项 总点数=2 + 4 = 6

加到前5项

1
new_nums = [2,3,4,5,7];

1. 拿第5项和MAX[3] 总点数=5 + 6 = 11
2. 拿第2、4项 总点数=3+5=9
3. 拿第1、4项 总点数=2+5=7

欸，这里的2.3.是不是有些熟悉，我们往前看发现这个我们也算过啊，在算前4项的时候就算过，所有我们也直接拿我们存下的数来算

1. 拿第5项和MAX[3] 总点数=5 + 6 = 11
2. 拿MAX[4] 总点数=9

于此我们就可以推导出公式，对于前i个数来说，最大值有两种可能

1. 第i项本身的值 + MAX[i-2]
2. MAX[i-1]

我们找出其中最大的就行了，写成代码就是

1
MAX[i]={
2
  add[new_nums[i]] + MAX[i-2],
3
  MAX[i-1]
4
  //new_nums[i]返回当前我们正在处理的数
5
  //add寻找其相同的数的和
6
  //add[new_nums[i]] 就是在初始数组里某个数其相同数的和
7
};

我们可以理解为2个值和一个区域的最大值

1
//非实际要这么做，为方便理解
2
new_nums = [(2,3,4),5,7];
3
//(2,3,4)代表在里面的最大拿法
4
//这个就表示在(2,3,4) + 7和5中做选择

我们直接写成代码提交，没通过 /_ \

1
new_nums = [1,2,3,5]

我们的代码在上例中就通不过，最佳选择应该是3和5，但我们的代码会选择2和5，因为我们的代码默认数组为一串连续的整数，而实际上它是不连续的

那我们就加一个条件判断，如果这个数不是连续整数，即new_nums[i] -new_nums[i-1] != 1，那么我们就特殊处理它

因为它不是连续的所以我们可以直接用add[new_nums[i]] + MAX[i-1]，这样就一定是最大的

1
class Solution {
2
public:
3
    int deleteAndEarn(vector<int>& nums) {
4
    sort(nums.begin(),nums.end());//排序需#include <algorithm>
5

6
    map<int,int> add;//需#include <map>
7
    add[nums[0]] = nums[0];//为后面的代码做让步
8

9
    vector<int> new_nums;//新数组，用来存储去重后变量
10
    new_nums.push_back(nums[0]);//为后面的代码做让步
11

12
    for(int i = 1;i < size(nums);i++){
13
            add[nums[i]] += nums[i];
14
      if(nums[i] != nums[i-1]){
15
        new_nums.push_back(nums[i]);
16
      }
17
        }
18

19
    int n1=add[new_nums[0]],n2=0;//观察公式发现只需要两个变量即可代替MAX
20

21
    for(int i = 1;i < size(new_nums);i++){//i = 0的情况无需计算
22
      int curl;//但我们还是需要第三个变量零时存储
23
      if(new_nums[i] - new_nums[i-1] == 1){//判断是否连续
24
        curl = max(add[new_nums[i]] + n2, n1);
25
      }else{
26
        curl = add[new_nums[i]] + n1;
27
        //new_nums[i]返回当前我们正在处理的数
28
        //add寻找其相同的数和
29
        //add[new_nums[i]] 就是在初始数组里某个数其相同数的和
30
      }
31
      n2 = n1;
32
      n1 = curl;
33
      //滚动更新
34
    }
35

36
    return n1;
37
  }
38
};
39
//时间复杂O(n log n)，主要与sort()本身性质决定
40
//空间复杂O(n),与n的增长成正比
41
//这个代码的优化空间极大，为了能代码易读性所以这么写