LeetCode贪心算法章节

LeetCode贪心算法章节

分发饼干

思路

以每个人的胃口作为阈值，只有给够饼干才能满足，那么为了满足更多的人，则应根据胃口有小到大排序，在饼干数量一定情况下，先满足胃口小的可以让更多人得到满足

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        if(s.size()==0) return 0;
        int res = 0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int i=0, j=0;
        while(i<g.size() && j<s.size())
        {
            if(g[i]<=s[j])
            {
                res++;
                i++;
                j++;
            }
            else if(g[i]>s[j])
                j++;
        }
        return res;
    }
};

总结

题目中用到的贪心算法思想，局部最优就是小饼干先喂饱小胃口，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩**

摆动序列

思路

根据数组前后差值关系，求出最长的摆动子序列，其中，子序列也可以删除原序列的某个元素。也就是说，不改变序列顺序，忽略非摆动的子序列，从中找到摆动子序列并拼接，求出最大的长度。

局部最优就是通过删除在单一坡度（单调序列）上的元素，使其出现两个峰值，如在5,1,4,6,3中，1,4,6为单一坡度，在删除元素4之后，就变成摆动序列，或者延长了摆动序列。实际操作中，可以忽略掉单调坡上的元素，只取两端，统计使出现峰值的转折点元素

贪心

res初始为1（默认最右面有一个峰值），此时cursub> 0 &&presub<= 0，那么res++（计算了左面的峰值），最后得到的res就是2（峰值个数为2即摆动序列长度为2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()<=1)  return nums.size();
        int res = 1;
        int presub = 0;
        int cursub = 0;
        for(int i = 0; i < nums.size() - 1;i++)
        {  
            cursub = nums[i + 1] - nums[i];
            if((cursub > 0 && presub <= 0)||(cursub < 0 && presub >= 0))
            {
                res++;
                presub = cursub;
            }
        }
        return res;
    }
};

上述版本中，判断条件为presub <= 0和presub> = 0，让presub等于0也进入结果集收集，是因为在一开始presub为0。另外，考虑到出现相邻相同元素时，此时cursub=0，不会被统计到结果中，并且，presub也不会更新成0，就是为了阻止非严格单调序列也会被统计到，如1,5,3,3,2，如果每次都更新presub，令presub=cursub，当遇到相同元素时，所有相同元素不被统计成摆动序列（因为cursub=0)，但相同元素的下一个元素无论是否符合摆动，都会被统计成摆动序列里（因为此时presub=0）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()<=1)  return nums.size();
        int res = 1;
        int presub = 0;
        int cursub = 0;
        for(int i = 0; i < nums.size() - 1;i++)
        {  
            cursub = nums[i + 1] - nums[i];
            if(cursub==0)   continue;
            if(cursub*presub <= 0)
            {
                res++;
            }
            presub = cursub;
        }
        return res;
    }
};

以上版本使用不同方法判断摆动，cursub * presub <= 0，还要增加if(cursub==0) continue;，当遇到相同元素时，cursub=0则直接跳过当次循环，也不会更新presub，直到遇到不同的元素。也就是相当于去重处理

动规

利用动态规划思想

总结

保持区间波动，只需要把单调区间上的元素移除就可以了，通过局部最优达到全局最优

本题关键在于对摆动子序列的统计判断条件，即当遇到相同元素时如何处理

最大子数组和

贪心

寻找相加和最大时的子数组，与上题不同，上题不允许排序但能删掉中间的元素，是一种拼凑的子序列，本题要求是连续的子数组，容易想到的是用两层for循环以及双指针解法，其中，双层for循环能够实现但会导致超时，时间复杂度为O(n^2)；双指针法其实并不能够在单次循环中实现，在有正负交错的情况下，不能找到最大子数组的边界点。

贪心算法的局部最优思路路是，在求和过程中，一旦求和值为负数，则应舍弃掉之前的子序列，再重新从下一个元素开始求和

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int sum = 0;
        for(int i = 0;i<nums.size();i++)
        {
            sum += nums[i];
            if(sum>res)
                res = sum;
            if(sum<0)
                sum = 0;
        }
        return res;
    }
};

其中，

  • 当遇到连续正数时，sum一直增长并更新res
  • 当遇到连续负数时，第一个负数与INT_MIN对比肯定会更新到res中，后面的负数再更新到保持为0的sum中，最后跟已存到res的第一个负数做大小比较，取较大值
  • 当遇到正数+负数+正数时，访问到负数时，只要sum值还没变为负数，都会一直扩大子序列，因为可能后面还会有正数使得子序列和更大，而当后面一直是负数直到sum<0，那么就会重新开始计算子序列的最大和，因为从下一个正数开始的子序列和必然比负数大，这也是为何是if(sum<0)而不是if(nums[i]<0)
  • 时间复杂度为O(n)，遍历数组所有元素一次，空间复杂度为O(1)，占用常数级空间存放变量

动规

分治

分治的思想与递归回溯有些类似，通过划分子区间，直到区间元素个数为1，再回升合并，更新维护相应的变量，直到回到原始数组区间。因此，关键在于1. 要维护的信息 2. 如何在合并区间时更新这些信息

  1. lsum维护包含左端点在内的最大子序列和
  2. rsum维护包含右端点在内的最大子序列和
  3. isum维护区间数组的最大子序列和
  4. sum维护区间数组的总和

在合并s1和s2区间时，为了维护isum即最终求取的结果，都会用到以上的信息，这也是需要维护以上信息的原因

  1. sum = s1.sum + s2.sum数组总和直接相加
  2. lsum = max(s1.sum, s1.sum + s2.lsum)取原左区间lsum和合并区间lsum即s1.sum+s2.lsum的最大值
  3. rsum同上
  4. isum有三种可能，可以是左区间的isum，也可能是右区间的isum，还有一种可能是合并之后跨越两个区间，此时isum = s1.rsum + s2.lsum

整体代码如下

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
class Solution {
public:
    struct status{
        int lsum, rsum, isum, sum;
    };
    status pushup(status&s1, status&s2)
    {
        int sum = s1.sum + s2.sum;
        int lsum = max(s1.lsum, s1.sum+s2.lsum);
        int rsum = max(s2.rsum, s2.sum+s1.rsum);
        int isum = max(max(s1.isum,s2.isum), s1.rsum+s2.lsum);
        return (status) {lsum, rsum, isum, sum};
    }
    status get(vector<int>& nums, int st, int en)
    {
        if(st==en)
        {
            return (status) {nums[st],nums[st],nums[st],nums[st]};
        }
        int mid = (st + en) >> 1;
        status s1 = get(nums, st, mid);
        status s2 = get(nums, mid+1, en);
        return pushup(s1,s2);
    }
    int maxSubArray(vector<int>& nums) {
        return get(nums,0,nums.size()-1).isum;
    }
};

时间复杂度O(n)，遍历数组所有元素一次，空间复杂度O(log n)，递归占用了栈空间

总结

贪心算法能够在遍历数组的时候遇到子数组和为负数时及时舍弃，再重新从零开始，也是其贪的局部最优思想。

分治算法

  • 在于不断切割子区间，利用递归回溯思想把问题转化求解子区间的问题，最关键的地方在于合并区间时对信息的更新维护
  • 如果在合并区间上要存取的信息较多，函数参数冗杂，可以通过结构体来实现信息的传递
  • 虽然分治算法时间复杂度与贪心相同，且空间复杂度上由于递归比贪心要差，但分治算法构建了线段树，能做到快速访问任何子区间上的最大子序列和，访问的时间复杂度为O(log n)，对于大规模查询的情况下，这种方法的优势便体现了出来

买卖股票最佳时机II

贪心

用贪心思想较为简单，由于没有买入卖出次数限制，只考虑每天的盈亏情况，再把所有盈余的情况相加即可

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for(int i = 0;i < prices.size()-1;i++)
        {
            if(prices[i+1]-prices[i]>0)
                res += prices[i+1] - prices[i];
        }
        return res;
    }
};

动规

总结

贪心算法中，局部最优是将最大利润划分成每天能获取的利润，贪在只获取盈余的部分，舍弃亏钱的部分

跳跃游戏

贪心

通过for循环里从头开始遍历数组的所有元素，借助一个变量tmp记录当前元素下往前所能达到的最大范围，并且在遍历过程中不断更新这个变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int tmp = 0;
        for(int i = 0; i < nums.size();i++)
        {
            if(tmp<0)  return false;
            tmp = max(tmp, nums[i]);
            --tmp;
        }
        return true;
    }
};

总结

贪心算法思想中局部最优是 当前位置下能够到达的最远范围，即tmp变量，贪在了不断更新当前位置下的最远范围，通过这个来判断能否到达目的位置

跳跃游戏II

贪心

贪心算法局部最优在于寻找当前能覆盖的最大范围，在遍历数组时遇到这个最大范围的边界点，则更新在遍历时遇到的最大范围以及更新跳数，即遇到了上一个最大范围则需要进行下一跳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0;
        int tmp = 0;
        int en = 0;
        for(int i =0;i<nums.size()-1;i++)
        {
            tmp = max(nums[i]+i,tmp);
            if(i == en)
            {
                en = tmp;
                res++;
            }
        }
        return res;
    }
};

总结

与上一题解法相比，都是用一次的数组遍历，但上题中记录的是以当前位置作为基准，所能到达的最远距离，且在遍历每一个点时都会更新这个距离；而这一题中因为能确保到达数组的最后一个位置，记录的是能够覆盖的最大范围，且只在到达了上一个最大范围时才更新这个范围

K 次取反后最大化的数组和

暴力解法

不断通过排序，对最小的元素进行取反，直到剩余取反次数为0

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        while(k--)
        {
            nums[0] = -nums[0];
            sort(nums.begin(),nums.end());
        }
        return accumulate(nums.begin(),nums.end(),0);
    }
};

贪心1

显然，有着很多的重复排序操作，考虑只进行一次遍历和排序

由于有正数和负数，可以通过由小到大排序数组并分类讨论

  • 如果当前最小元素是正数，且剩余取反次数是偶数，则可以直接返回
  • 如果当前最小元素是正数，且剩余取反次数是奇数，则重新排序对最小值进行取反再返回
  • 如果当前最小元素是负数，且剩余取反次数大于0，则直接取反并移动到下一个元素
  • 如果移动到下一个元素超出数组范围，且剩余取反次数大于0，则移动到数组首元素，这种情况下，原数组全为负数而此时数组全为正数，则只需判断剩余取反次数的奇偶性。

整体代码如下

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
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int res = accumulate(nums.begin(),nums.end(),0);
        sort(nums.begin(),nums.end());
        int i = 0;
        while( k && i<nums.size())
        {
            if(nums[i] >= 0 && k % 2 == 0)
                break;
            else if(nums[i] >= 0 && k % 2 != 0)
            {
                sort(nums.begin(),nums.end());
                nums[0] = -nums[0];
                res += 2*nums[0];
                break;
            }
            nums[i] = -nums[i];
            res += nums[i]*2;
            ++i;
            --k;
            if(k && i == nums.size())       //全负数且k >= num.size()
                i = 0;
        }
        return res;
    }
};

贪心2

另一种解法，用不同的方式排序，按照绝对值大小进行排序

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
class Solution {
public:
    static bool cmp(int a, int b)
    {
        return abs(a) > abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int res = accumulate(nums.begin(),nums.end(),0);
        sort(nums.begin(),nums.end(),cmp);
        int i = 0;
        while( k && i < nums.size())
        {
            if(nums[i]<0)
            {
                nums[i] = -nums[i];
                res += 2*nums[i];
                --k;
            }
            ++i;
        }
        if(k && k%2!=0)
        {
            nums[nums.size()-1] *= -1;
            res += 2*nums[nums.size()-1];
            return res;
        }
        else
            return res;
    }
};

总结

贪心算法局部最优是将最小的负数取反，最大化数组和。

取到最小的负数就需要对数组的排序，可以有两种不同的排序方式，按值从小到大排序和按绝对值从小到大排序。从小到大排序会导致在对所有负数取反 而剩余取反次数大于零时，额外需要排序来对最小的整数进行取反。按绝对值排序则可以解决这个问题，当数组全为正数时，可直接根据剩余取反次数是否对数组末尾元素或首元素进行取反

加油站

容易想到的是暴力解法，判断能否循环一圈，只需要在循环中间油量不会变为负数即返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool ok(vector<int>& gas,vector<int>& cost, int index)
    {
        int times = 1;
        int tank = gas[index];
        while(times <= gas.size())
        {

            tank -= cost[index];
            if(tank<0)
                return false;
            index++;
            if(index>gas.size()-1)
                index = 0;
            tank += gas[index];
            times++;

        }
        return true;
    }

暴力解法

遍历数组，判断以当前元素开始能否循环一圈，但时间复杂度会达到O(n^2)

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
class Solution {
public:
    bool ok(vector<int>& gas,vector<int>& cost, int index)
    {
        int times = 1;
        int tank = gas[index];
        while(times <= gas.size())
        {

            tank -= cost[index];
            if(tank<0)
                return false;
            index++;
            if(index>gas.size()-1)
                index = 0;
            tank += gas[index];
            times++;

        }
        return true;
    }
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int res = -1;
        int tank = 0;
        for(int i = 0; i<gas.size();i++)
        {
            if(gas[i] < cost[i])
                continue;
            if(ok(gas,cost,i))
                return i;
        }
        return res;
    }
};

暴力优化

在暴力法中，每次都会有重复的遍历，因此可以借助容器记录遍历过的元素，记录该元素能走到最远的地方以及剩余的油量，下一次当再次遍历到该元素时则直接跳到保存的最远地方同时加上剩余的油量

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
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int> dist(gas.size(),-1);
        vector<int> tmp(gas.size());
        int res = -1;
        for(int i = 0; i<gas.size();i++)
        {
            int j = i;
            int cur = gas[i];
            while(cur-cost[j]>=0)
            {
                cur -= cost[j];
                j = (j+1) % gas.size();
                if(dist[j]!=-1)
                {
                    cur += tmp[j];
                    j = dist[j];
                }
                else
                    cur += gas[j];
                if(j==i && cur>= 0)
                    return i;
            }
            dist[i] = j;
            tmp[i] = cur;
        }
        return res;
    }
};

虽然减少了重复访问的时间，利用了空间换取时间的思想，但对时间提升并不明显，依然是超出时间限制。

暴力再优化

进一步考虑，假设i能够到达最远的地方为j，且不能绕一圈，那么可以知道，在i+1到j区间上任一点都不能绕一圈，也就是说，在遍历过程中，遍历完i之后即可直接跳转到j+1位置上

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
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int res = -1;
        vector<int> dist(gas.size(),-1);
        vector<int> tmp(gas.size());
        for(int i = 0; i<gas.size();i++)
        {
            int j = i;
            int cur = gas[i];
            while(cur-cost[j]>=0)
            {
                cur -= cost[j];
                j = (j+1)%gas.size();
                if(dist[j]!=-1)
                {
                    cur += tmp[j];
                    j = dist[j];
                }
                else
                    cur += gas[j];
                if(i == j)
                    return i;
            }
            dist[i] = j;
            tmp[i] = cur;
            if(i<j)
                i = j;
        }
        return res;
    }
};

也可以不借助数组，只占用常数级空间，显得更为简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int res = -1;
        for(int i = 0; i<gas.size();i++)
        {
            int j = i;
            int cur = gas[i];
            while(cur-cost[j]>=0)
            {
                cur -= cost[j];
                j = (j+1)%gas.size();
                cur += gas[j];
                if(i == j)
                    return i;
            }
            if(i < j)
                i = j;
        }
        return res;
    }
};

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int res = 0;
        int cursum = 0, tosum = 0;
        for(int i = 0; i<gas.size();i++)
        {
            int tmp = gas[i] - cost[i];
            cursum += tmp;
            tosum += tmp;
            if(cursum < 0)
            {
            	cursum = 0;
            	res = i + 1;
            }
        }
        if(tosum < 0)
        	return -1;
        else
        	return res;
    }
};

贪心算法局部最优在于找到符合当前油量足以到达下一站点的位置，借助cursum来记录，一旦cursum小于零，即在i站点出发不能够循环一圈，就马上从下一个站点重新出发，并把cursum置零

同样使用到上述的一个条件——假设i能够到达最远的地方为j，且不能绕一圈，那么可以知道，在i+1到j区间上任一点都不能绕一圈，那么此时就应该从j+1继续遍历

同时记录总油量，来判断是否存在任何站点都无法循环一圈的情况

贪心special

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
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tosum = 0;
        int tmpsum = 0;
        int mintmp = INT_MAX;
        for(int i = 0; i<gas.size();i++)
        {
            tmpsum = gas[i] - cost[i];
            tosum += tmpsum;
            if(tosum < mintmp)
                mintmp = tosum;
        }
        if(tosum<0)    return -1;
        if(mintmp >= 0)     return 0;
        for(int i = gas.size()-1;i>=0;i--)
        {
            tmpsum = gas[i] - cost[i];
            mintmp += tmpsum;
            if(mintmp >=0)
                return i;
        }
        return -1;
    }
};

有如下几种情况：

  1. 任何一个站点都无法循环一圈，遍历一遍数组后tosum小于0，则返回-1
  2. 从0开始遍历一遍数组后，tosum大于0且中途油箱最小值mintmp都大于0，则可以循环一圈，且从位置0开始，返回0
  3. 从0开始遍历一遍数组后，tosum大于0但中途油箱最小值mintmp小于0，则可以循环一圈，但不从位置0开始，逆向遍历数组，不断加上路径某个站点净获得油量，当mintmp大于等于0时，即从该位置开始可以循环一圈

总结

本题的关键点在于理解到假设i能够到达最远的地方为j，且不能绕一圈，那么可以知道，在i+1到j区间上任一点都不能绕一圈，由暴力解法优化而来的方法，因为都是在遍历数组时要直接模拟一圈循环，因此时间复杂度上会比贪心算法只遍历一遍数组要慢，但却有很好的优化方向，通过减少重复过程优化以及通过空间换取时间优化。贪心算法贪在了从当前站点出发，累加tmp的和curSum一旦小于0就要舍弃，新的起始位置至少要是j+1

分发糖果

贪心1

尽可能少的分发糖果，则每个人初始化为1，for循环遍历一次数组，根据当前元素与其前后元素对比，有以下情况

  • 若一直递增或递减

    • 当前元素i大于i-1，那么tmp++表示当前分发的糖果数量要比i-1多一个

    • 当前元素i小于i-1，则同样tmp++，只考虑总数量

  • 若遇到转折点，用cur记录当前的趋势，即cur>0表示递增，cur<0递减，cur==0表示第一个值或相等值

    • 从cur>=0变成cur<0，tmp重新置为1，tmp++后再加入到总数量中，即在转折点之后应该分发两个糖果
    • 从cur<=0变成cur>0时，tmp就应该置为0，tmp++后再加入到总数量中，因为分数比前一个小，分发的糖果就应该重置为1，同时要区分cur<0和cur==0的情况

代码如下

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
class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = 0;
        int tmp = 1;
        int cur = 0;
        for(int i = 0; i < ratings.size();i++)
        {
            if(i == 0 || ratings[i] == ratings[i-1])
            {
                tmp = 1;
                res += tmp;
                cur = 0;
            }
            else if (ratings[i] > ratings[i-1])
            {
                if(cur <= 0)
                {
                    cur = 1;
                    tmp = 1;
                }
                ++tmp;
                res += tmp;
            }
            else if (ratings[i] < ratings[i-1])
            {
                if(cur > 0)
                {
                    cur = -1;
                    tmp = 0;
                }
                else if(cur == 0)
                {
                    cur = -1;
                    tmp = 1;
                }
                ++tmp;
                res += tmp;
            }
        }
        return res;
    }
};

上述忽略了一种特殊情况——当递增序列转折成递减序列，且递减序列长度大于等于递增序列后，转折点分发的糖果要再随递增序列增加而增加，因为转折点既属于递增也属于递减序列，它的糖果数量由两条序列中较长的一条决定

因此，只是记录序列的转折情况是不足够的，**需要同时记录下递增序列inc和递减序列的长度dec**，以及当前序列的长度tmp，也相当于当前应分发的糖果数量

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
class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = 0;
        int tmp = 1;
        int inc = 0, dec = 0;
        for(int i = 0; i < ratings.size();i++)
        {
            if(i == 0 || ratings[i] == ratings[i-1])
            {
                tmp = 1;
                res += tmp;
                inc = 1;
                dec = 0;
            }
            else if (ratings[i] > ratings[i-1])
            {
                ++tmp;
                res += tmp;
                dec = 0;
                inc = tmp;
            }
            else if (ratings[i] < ratings[i-1])
            {
                ++dec;
                if(dec == inc)
                    ++dec;
                res += dec;               
                tmp = 1; 
            }
        }
        return res;
    }
};

贪心2

另一种思路是，分开两次从头至尾和从尾至头遍历数组，分别完成两条规则，从头至尾遍历保证右边分数高的糖果多于左边分数低的，从尾至头遍历保证左边分数高的糖果多于右边分数低的。

贪心算法局部最优在于保证当前糖果数量与上一个的糖果数量满足规则要求，但每次遍历只能满足一条规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = 0;
        vector<int> can(ratings.size(),1);
        for(int i = 1; i<ratings.size();i++)
        {
            if(ratings[i]>ratings[i-1])
                can[i] = can[i-1] + 1;
        }
        for(int i = ratings.size()-2; i>= 0;i--)
        {
            if(ratings[i] > ratings[i+1])
                can[i] = max(can[i], can[i+1]+1);
        }
        return accumulate(can.begin(),can.end(),0);
    }
};

总结

贪心1中思路更直接，但需要考虑的情况会更复杂，需要注意到转折序列中，递增和递减序列长度对转折点的影响

贪心2分别使用了两次贪心策略，让题目要求更简洁明了

根据身高重建队列

本题中，数组[h, k]序号为i，这意味着 身高为h，并且在队列前面还有k个身高高于或等于h的人，要求在于对打乱的i重新排序成正确顺序，使得h和k排列符合规则

贪心

在一次遍历中，并不能做到满足两条规则，需要分两步走，根据规则各自使用贪心策略。首先，对于数组的第0个元素，即身高，排列时的局部最优在于当前身高小于上一个身高，也就是按照降序排列身高。而对于第1个元素k，根据规则，应当按照升序排列

1
2
3
4
5
6
7
8
bool cmp(const vector<int>& a, const vector<int>& b)
{
	if(a[0] != b[0])
		return a[0] > b[0];
	else
		return a[1] < b[1];
}
sort(people.begin(), people.end(), cmp);

排列过后，数组people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]顺序变为[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]，可知，根据规则，在空的结果集中插入数组，贪心策略局部最优在于优先插入身高较高（即遍历排列后的数组）且其k较低的，如下插入过程所示，这样可以满足插入后的数组满足要求

1
2
3
4
5
6
[7,0]
[7,0],[7,1]
[7,0],[6,1],[7,1]
[5,0],[7,0],[6,1],[7,1]
[5,0],[7,0],[5,2],[6,1],[7,1]
[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]

第二步中的贪心优先处理身高较高的，在较高的排列完成后，就算再插入次高的元素也不会影响排列，依旧符合规则，在插入次高元素时，由于规则要求在此元素之前要有k个身高大于等于其身高的元素，因此，可以直接在位置k插入，使得局部上最优。

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    static bool cmp(vector<int>& v1, vector<int>& v2)
    {
        if (v1[0] != v2[0])
            return v1[0] > v2[0];
        else
            return v1[1] < v2[1];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> res;
        for (int i = 0; i < people.size(); i++)
        {
            res.insert(res.begin() + people[i][1],people[i]);
        }
        return res;
    }
};

在定义cmp函数时，将其定义为static静态函数是因为在类内定义函数，如果定义成非静态函数，则函数属于类的对象，而非类共有的函数，也就是说会隐式传递了this指针，那么类的对象在调用该函数的时候，就会通过指针隐式传递到函数参数列表中，来区分是哪一个对象调用函数，非静态函数实际参数为bool cmp(vector<int>& v1, vector<int>& v2, Solution* this)

贪心优化

在上一版本中的代码中，借助数组来记录结果，而数组在进行insert操作时，时间复杂度为O(n)，显得并不高效，因此可以借助链表来完成多次的插入操作

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
class Solution {
public:
    static bool cmp(vector<int>& v1, vector<int>& v2)
    {
        if (v1[0] != v2[0])
            return v1[0] > v2[0];
        else
            return v1[1] < v2[1];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> res;
        for (int i = 0; i < people.size(); i++)
        {
            auto index = people[i][1];
            auto iter = res.begin();
            while(index--)
            {
                iter++;
            }
            res.insert(iter,people[i]);
        }
        return vector<vector<int>> (res.begin(),res.end());
    }
};

在调整迭代器位置时，还可以使用advance标准库函数，advance(it,n)可以让迭代器it往前移动n个位置

1
2
3
4
auto index = people[i][1];
auto iter = res.begin();
advance(iter, index);
res.insert(iter, people[i]);

总结

与[上一题](# 分发糖果)比较，都是需要分两步走，把规则拆分成两步再分别使用贪心策略，这一题中最关键点在于在第二步中的贪心策略，局部最优在于插入一个元素时，只考虑当前规则是要求只有k个值在其前面，因此可以直接插入到第k个位置上，并且插入之后也不会影响已经插入的元素，符合规则

用最少数量的箭引爆气球

这道题中，使用数量尽可能少的箭引爆更多的气球，首先，可以用过排序让带有重叠区间的数组分布在一起，而排序则又可以分为两种，分别是根据开始位置和结束位置，对应了不同方向的思路

贪心1

按照开始位置来进行排序，定义排序函数，开始位置小的会排在前面，如果开始位置相同，则结束位置更小的排在前面

1
2
3
4
5
6
bool cmp(const vector<int>& a, const vector<int>& b)
{
	if(a[0]==b[0])
		return a[1] < b[1];
	return a[0] < b[0];
}

那么，对于数组[[10,16],[2,8],[1,6],[7,12]]将会排序成[[1,6],[2,8],[7,12],[10,16]]，接着，为了追求最少数量的箭，在区间尽可能排序成重复的基础上，局部最优在于取重复数组区间的最小的结束位置，并在该位置上射出弓箭，这样就能尽可能覆盖到更多的不同区间，即引爆更多的气球

整体代码如下

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
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        if(a[0]!=b[0])
            return a[0] < b[0];
        return a[1] < b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==0)    return 0;
        int res = points.size();
        sort(points.begin(), points.end(),cmp);
        int en = points[0][1];
        for(int i = 1; i < points.size(); i++)
        {
            if(en >= points[i][0]) //有重叠 
            {
                res--;
                en = min(points[i][1], en); 
            }
            else
                en = points[i][1];
        }
        return res;
    }
};

使用一个变量en来记录重复区间结束位置，if(en >= points[i][0]) en = min(points[i][1], en)当遇到有重叠区间时，应对en进行更新，令其等于 当前区间的结束位置 和 原结束位置 的最小值，而不是直接赋值等于当前区间的结束位置或上一个区间的结束位置。也因为不需要返回原数组，可以在原数组上直接修改结束位置，只需要判断上一个区间的结束位置，并不断对其进行维护points[i][1] = min(points[i-1][1], points[i][1])

贪心2

另外一种方法是用不同的排序方法，按照区间的结束位置来进行排序，结束位置较小的则排在前面，如果结束位置相同则让开始位置较小的靠前（这一步不影响）

1
2
3
4
5
6
bool cmp(const vector<int>& a, const vector<int>& b)
{
	if(a[1]==b[1])
		return a[0] < b[0];
	return a[1] < b[1];
}

这种排序下，只需要判断当前区间的开始位置与重复区间的结束位置是否有重叠，用en来对重复区间的结束位置进行记录，如果没有则需要增加弓箭的数量，而如果开始位置小于等于上一个区间的结束位置，则无论如何两个区间都会有重叠，并且有重叠时不用对en进行更新，保持原来的重复区间结束位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==0)    return 0;
        int res = 1;
        sort(points.begin(), points.end(),cmp);
        int en = points[0][1];
        for(int i = 1; i < points.size(); i++)
        {
            if(en < points[i][0]) //无重叠 
            {
                res++;
                en = points[i][1];
            }
        }
        return res;
    }
};

总结

两种排序方法引出两种对重叠区间不同的判断方式，且都是用到了贪心策略，尽可能让当前区间的开始元素与记录区间的结束元素有重叠，即通过排序再加上尽量去重叠区间的最大值，则可以覆盖到更多区间

第一种排序方式，按区间的开始位置升序排列，借助变量en记录有重复区间的结束位置，不论是否有重叠区间，都要对en进行维护，当有重叠时，en取当前区间的结束位置和原结束位置的最小值；当没有重叠时，en则取当前区间的结束位置

第二种排序方式，按区间的结束位置升序排列，同样借助变量en对重叠区间的结束位置进行记录，因为是根据结束位置进行了排序，当有重叠时，对en不需要进行维护，因为en的值已经是当前包括之前所有区间的结束位置的最小值；在没有重叠时，en也同样取当前区间的结束位置

时间复杂度为O(n log n + n)，为排序消耗的时间和遍历数组的时间，空间复杂度为O(log n)，排序所占用的栈空间，最坏情况下为O(n)，需要n次的递归调用

无重叠区间

该题与[上一题](# 用最少数量的箭引爆气球)比较相像，都是有关于重叠的区间，而这题要求的是找出导致重叠的区间并将其删除，返回要删除的个数

贪心

类似的，首先需要排序，让重叠的区间尽可能靠近，这里按照区间的结束位置升序排列，但对于相同的结束位置的区间，应该考虑到优先删除开始位置更小的区间，因为开始位置小，所覆盖的区间更大，出现与其他区间相互重叠的可能性也更大。因此遍历顺序应该是先确定区间结束位置更小，并且区间内所覆盖的范围也要更小，当遇到有重叠的区间则应该增加删除的数量

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
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        if(a[1]==b[1])
            return a[0] > b[0];
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int res = 0;
        if(intervals.size()==1)
            return res;
        sort(intervals.begin(),intervals.end(),cmp);
        int en = intervals[0][1];
        for(int i = 1; i < intervals.size(); i++)
        {
            if(en > intervals[i][0])
            {
                res++;
            }
            else
                en = intervals[i][1];
        }
        return res;
    }
};

总结

该题中，局部优化在于按照区间的结束位置排序，并且要将范围更小的区间排列在先，是为了占用更小的空间，减少重叠的发生

同样的，这题也可以按照区间的开始位置排序，这时要将范围更大的区间排列在先，并且是采用从右往左的遍历方式，也是出于相同的原因

划分字母区间

首先看到划分字符串想到的是回溯法，但在这题中并不需要暴力搜索。题目要求的是同一个字母只出现在一个分段中，而且只有分段最多的分法正确

首先需要遍历一次，得到所有字母对应的下标，借助可变数组来保存每个字母最后一次出现的下标位置

1
2
3
4
5
vector<int> hashmap(26);
for(int i = 0; i < s.size(); i++)
{
	hashmap[s[i]-'a'] = i;
}

贪心

在得到每个字母对应最远的下标后，使用贪心策略，局部最优在于一个分段尽可能小，但同时还要包含出现过的字母的所有范围，再对字符串进行遍历，对于一个片段，划分完成时，当前下标与哈希表中字母的最后一次出现的下标位置相同，并且，在遍历的过程中，对tmp更新为 当前字母的最远距离 和 原字母的最远距离 的较大值，也就是将tmp保持为该片段中含有的字母出现的最大位置或最远距离。也就是说，在一个片段中，划分只与该片段中有最长距离的字母有关，在遍历过程中，不断更新这个字母，当遍历到该字母的最长距离时，即一个片段的划分完成

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> hashmap(26);
        vector<int> res;
        int tmp = 0, count = 1;
        for(int i = 0; i<s.size();i++)
        {
            hashmap[s[i] - 'a'] = i;
        }
        for(int i = 0; i < s.size(); i++)
        {
            tmp = max(tmp, hashmap[s[i]-'a']);
            if(i==tmp)
            {
                res.push_back(count);
                count = 0;
            }
            count++;
        }
        return res;
    }
};

总结

贪心策略在该题中十分巧妙，贪在当前片段下，要让片段尽可能小的同时还要保证出现过的字母只在该片段中出现。这就需要借助哈希表来记录每个字母最后一次出现的位置，即它们各自的最大距离；在对字符串遍历过程中，还要维护保证每个出现过的字母的最远距离，这个距离就是这个片段长度的最小长度

合并区间

该题要求对有重叠的区间进行最大化合并，返回合并后的区间

类似于之前的有关重叠区间题目，该题也是将各区间进行排序后，再使用贪心策略，将尽可能多的区间进行合并

贪心1

先按照区间的结束位置升序排列，结束位置较小的排在前面。因为开始位置不影响结果，所以可不给出排序规则

1
2
3
4
static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];
    }

对于区间数组[[1,10],[2,5],[6,9]]则会排序变为[[2,5],[6,9],[1,10]]，接着，为了能够合并更多的区间，借助变量tmp取值为重叠区间的结束位置，正向遍历数组，当遇到tmp < intervals[i][0]时代表没有重叠区间，则直接把该区间加入到结果集中，但当遍历到[1,10]时，该区间已将前面全部区间所包含，导致不正确的原因是遍历方式选择不正确，在该题中，如果按照区间的结束位置来排列，则遍历顺序应该是从尾到头的逆向遍历

整体代码如下

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
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 1) return intervals;
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> res;
        int st = intervals[intervals.size()-1][0], en = intervals[intervals.size()-1][1];
        for (int i = intervals.size()-1; i >= 0; i--)
        {
            if (st <= intervals[i][1]) // 有重叠
            {
                st = min(st, intervals[i][0]);
            }
            else
            {
                res.push_back(vector<int> {st, en});
                st = intervals[i][0];
                en = intervals[i][1];
            }
        }
        res.push_back(vector<int> {st,en});
        return res;
    }
};

贪心2

另一种方式则是按照开始位置升序排列，此时，应该正向遍历数组

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
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 1) return intervals;
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> res;
        int st = intervals[0][0], en = intervals[0][1];
        for (int i = 0; i < intervals.size(); i++)
        {
            if (en >= intervals[i][0]) // 有重叠
            {
                en = max(intervals[i][1], en);
            }
            else
            {
                res.push_back(vector<int> {st, en});
                st = intervals[i][0];
                en = intervals[i][1];
            }
        }
        res.push_back(vector<int> {st,en});
        return res;
    }
};

总结

该题与无重叠区间相比有相反的感觉，都是要找到重叠区间的部分，但后者是优先寻找到范围更小的区间，是为了减少重叠的可能性；而这题是要优先找到范围更大的区间，就是为了要尽可能多的重叠区间。也因此，要根据不同的目的，针对不同排序方式下选用不同的遍历顺序

单调递增的数字

该题要求返回小于等于给定输入的尽可能大的数，并且返回值按位非严格递增，如给定98则返回89

贪心

要求返回的数尽可能大，那么局部最优在于先从低位修改，这也确定了遍历顺序是从右往左，如果num[i]大于num[i+1]，不符合按位递增规则，则num[i]--; num[i+1]='9';。但是如果给定输入为1000，只修改为900，而原本应该为999，因此，需要另外借助变量记录开始修改为9的位置，即i+1处，在i+1往后的位置都应该赋值为9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string num = to_string(n);
        int flag = num.size();
        for (int i = num.size() - 1; i > 0; i--)
        {
            if (num[i -1] > num[i])
            {
                num[i - 1]--;
                flag = i;
            }
        }
        for(int i = flag; i < num.size();i++)
        {
            num[i] = '9';
        }
        return stoi(num);
    }
};

时间复杂度为O(log n)，n为输入的数，log n对应其位数，空间复杂度为O(log n)，占用log n的空间来存放数的每一位

总结

贪心策略在于 为了取到最大值，从数的低位开始修改，这就确定了从右往左的遍历顺序；还需要有标志位来记录需要变为9的所有位置

买卖股票最佳时机I

与[同系列的上一题](# 买卖股票最佳时机II)相比，该题还增加了手续费，相当于限制了买卖次数，需要找到除去手续费后的最大利润，而不能像上一题那样无限制买入卖出

贪心

思路依旧还是 希望能够在最低点买入，然后在最高点卖出，而因为有了手续费，还会有新的情况需要考虑到：如何知道当前点是最高点

贪心策略就是用于解决这个问题，首先遍历寻找最低点进行买入，并维护buy = prices[l]+fee，此时l为最低点，如果遍历到该点利润大于零，可以虚拟地卖出了这只股票，利润值增加profit += prices[sh] - buy = prices[sh] - prices[l] -fee，此时sh为次高点，并且已经扣除了手续费，模拟在这个次高点虚拟卖出，同时还要更新买入价格为 当前股票价格，即buy = prices[sh]，如此一来，当遍历到下一个点发现股票价格还在上涨时prices[h]>prices[sh]，则又虚拟的假设成在这个最高点上卖出了股票，由于买入价格的更新，利润值更新为profit += prices[h] - buy = prices[h] -prices[sh] ，可以看出，根据这时候获得的利润，可以模拟出最低点买入而在最高点卖出的过程

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int res = 0;
        int buy = prices[0] + fee;
        for(int i = 0; i < prices.size(); i++)
        {
            if(prices[i]+fee < buy)
                buy = prices[i] + fee;
            else if(prices[i] > buy)
            {
                res += prices[i] - buy;
                buy = prices[i];
            }
        }
        return res;
    }
};

时间复杂度为O(n)，空间复杂度为O(1)

相同思路，而不必将buy维护成最低买入点与手续费的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int res = 0;
        int buy = prices[0];
        for(int i = 0; i < prices.size(); i++)
        {
            if(prices[i] < buy)
                buy = prices[i] ;
            else if(prices[i] > buy + fee)
            {
                res += prices[i] - buy - fee;
                buy = prices[i]-fee;
            }
        }
        return res;
    }
};

总结

贪心策略在该题中体现在 遇到次高点时虚拟的卖出，更新利润的同时也更新买入价格，即虚拟地在该点买入，这也是局部最优的所在

遍历数组的时候，会有以下三种情况：

  • 该点比买入点更低，则更新买入的最低点
  • 该点比买入点和手续费的和更高，即利润大于0，此时虚拟地卖出，更新利润以及更新买入点，也为后续更高点准备
  • 该点在[低买入点+手续费，高卖出点]范围，即没有利润，则此时不会卖出，不进行任何操作

监控二叉树

题目要求添加最少的监控，覆盖到所有的二叉树结点

一开始，想到根据父结点的值来判断当前结点是否需要添加监控，如果父结点值为0，则为当前结点添加监控；反之亦然。同时使用层序迭代遍历二叉树即可完成

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
52
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minCameraCover(TreeNode* root) {
        if(!root->left && !root->right) return 1;
        int res = 0;
        queue<TreeNode*> que;//还要存父结点
        //层序遍历
        TreeNode* pre, *cur;
        que.push(nullptr);
        que.push(root);
        while(!que.empty())
        {
            for(int i = 0; i < que.size(); i++)
            {
                pre = que.front();
                que.pop();
                cur = que.front();
                que.pop();

                if(pre && pre->val == 0 && (cur->left||cur->right))
                {
                    res++;
                    cur->val = 1;
                }

                if(cur->left)
                {
                    que.push(cur);
                    que.push(cur->left);
                }
                if(cur->right)
                {
                    que.push(cur);
                    que.push(cur->right);
                }
            }
            
        }
        return res;
    }
};

然而，这种方法下，当遇到的二叉树添加监控的结点的孙子结点是叶子结点时，则无法做到监控的全覆盖

贪心

采用贪心策略，局部最优在于为了添加的监控数量最少，则只给叶子结点的父结点添加监控

针对以上，结点值会有三种状态：0表示无覆盖，1表示有监控，2表示被覆盖。增加结点值为 2 是为了方便表示叶子结点等的状态，进而，二叉树的遍历顺序应为后序遍历，先遍历子结点再遍历中间结点，由下至上的遍历顺序

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	int dfs(TreeNode* node, int& res)
	{
		if(!node)		//遇到空结点应返回2
			return 2;
		int l = dfs(node->left, res);
		int r = dfs(node->right, res);
		
		if(l == 2 && r == 2)
         	return 0;
         if(l == 0 || r == 0)
         {
         	res++;
         	return 1;
         }
         if(l == 1 || r == 1)
         	return 2;
         
         return -1;
	}
    int minCameraCover(TreeNode* root) {
        int res = 0;
        if(dfs(root, res) == 0)
        	res++;
        return res;
    }
};

时间复杂度为O(n)，空间复杂度为O(log n)，最坏情况下为O(n)

因为后序遍历中，中间结点的处理情况需要用到其左右子结点的值来判断，因此，将当前结点的值作为递归函数的返回值。

根据左右子结点的值来判断当前当前结点的值，有四种情况：

  • 左右子结点都是有覆盖，则当前结点返回0，表示无覆盖
  • 左右子结点有任意一个无覆盖，则当前结点应添加监控，返回1
  • 左右子结点有任意一个有监控，则当前结点返回2，表示有覆盖
  • 在对除根结点外的所有结点遍历结束后，对于根结点，可能会出现根结点未覆盖的情况，因此还需要对根结点的返回值进行一次判断，若返回0则需要再添加一个监控

总结

该题中局部最优在于 不让叶子结点添加监控，而让叶子结点的父结点添加监控，在此基础上，推导出3种不同结点值的状况，并进行分类讨论

通过最少操作次数使数组的和相等

该题给定两个数组，限定数组元素值均为1~6，任意修改数组元素，使得两个数组和相等，返回操作次数

贪心

采用贪心策略，局部最优在于优先让数组和大的数组元素改为1，数组和小的数组元素改为6，最快速逼近两个数组的和

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
class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        if(n1*6 < n2 || n2 * 6 < n1 )
            return -1;
        int sub = accumulate(nums1.begin(), nums1.end(),0)-accumulate(nums2.begin(), nums2.end(),0);
        if(sub < 0)
        {
            swap(nums1, nums2);
            sub = -sub;
        }
        //要求nums1 减小， nums2 增大
        vector<int> cnt(6);
        for(auto n:nums1)
        {
            cnt[n-1]++;
        }
        for(auto n:nums2)
        {
            cnt[6-n]++;
        }
        for(int i = 5, res = 0;;i--)
        {
            if(i*cnt[i] >= sub)
                return res + (sub+i-1)/i;
            res += cnt[i];
            sub -= i*cnt[i];
        }
    }
};

让nums1的和比nums2的和大，即让nums1减小，让nums2增大；

分别遍历两个数组，借助vector容器记录两个数组中能够减小或增大的最大范围，如cnt[4]含义是数组中原始值为5或者为2的元素有cnt[4]个；

最后遍历vector容器，若当前减小或增大的最大范围能够覆盖两个数组的和的差，即i*cnt[i] >= sub，意味着仅需要对当前cnt[i]个元素减小或增大i就能够让两个数组的和相等，否则，因为遍历顺序优先遍历修改范围更大的元素，所以先让这些元素对数组差进行填补，再遍历更小范围的元素；

返回值中return res + (sub+i-1)/i;而不是直接返回return res + sub / i;，若sub不能整除i，直接返回会有余数导致结果偏小不正确，若返回return res + sub / i + 1，此时若sub能整除i，没有余数又导致结果偏大不正确。因此sub + i - 1向上取整解决了这个问题

总结

局部最优在于优先让数组中修改范围更大的元素进行修改，以最快速度填补数组和之差

LeetCode贪心算法章节
https://kevin346-sc.github.io/2022/11/15/LeetCode贪心算法章节/
作者
Kevin Huang
发布于
2022年11月15日
许可协议