第八章贪心

一、简单题目

1.1 分发饼干

思路一：大饼干喂给大胃口

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1; // 饼干数组下标，使用index而不是用for循环更简单
        int res = 0;
        for (int i = g.size() - 1; i >= 0; i -- ) // 遍历胃口
            if (index >= 0 && s[index] >= g[i]) 
                res ++ , index -- ;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

上面的代码一定要是 for 控制胃口，if 控制饼干，因为 for 中的 i 使固定移动的！

思路二：小饼干喂给小胃口

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = 0;
        for (int i = 0; i < s.size(); i ++ )
            if (index < g.size() && s[i] >= g[index])
                index ++ ;
        return index;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

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

Leetcode 1005

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);
        for (int i = 0; i < nums.size(); i ++ )
            if (k && nums[i] < 0) k -- , nums[i] *= -1;
        // 剩余的k为偶数的时候，对同一个数作用不变
        if (k % 2) nums[nums.size() - 1] *= -1;
        int res = 0;
        for (int x: nums) res += x;
        return res;
    }

    static bool cmp(const int &a, const int &b) {
        return abs(a) > abs(b);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.3 柠檬水找零

Leetcode 860

三种情况：

情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5（5 可以给 10 找零，也可以给 20 找零，所以需要后使用 5）

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0, twenty = 0;
        for (int bill: bills) {
            if (bill == 5) five ++ ;
            if (bill == 10) {
                if (five <= 0) return false;
                ten ++ , five -- ;
            }
            if (bill == 20) {
                if (five > 0 && ten > 0) {
                    five -- ;
                    ten -- ;
                    twenty ++ ;
                } else if (five >= 3)
                    five -= 3, twenty ++ ;
                else return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.4 分割平衡字符串

Leetcode 1221

从前往后遍历，只要遇到是平衡字串就计数加一。

class Solution {
public:
    int balancedStringSplit(string s) {
        int res = 0, count = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            if (s[i] == 'R') count ++ ;
            else count -- ;
            if (!count) res ++ ;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

二、中等题目

2.1 序列问题

2.1.1 摆动排序

Leetcode 376

动态规划：

设状态 $d p [i] [0]$ ，表示考虑前 i 个数，第 i 个数作为山峰的摆动子序列的最长长度
设状态 $d p [i] [1]$ ，表示考虑前 i 个数，第 i 个数作为山谷的摆动子序列的最长长度

那么有状态转移方程：

$d p [i] [0] = ma x (d p [i] [0], d p [j] [1] + 1)$ ，其中 $0 < j < i$ 且 $n u m s [j] < n u m s [i]$
$d p [i] [1] = ma x (d p [i] [1], d p [j] [0] + 1)$ ，其中 $0 < j < i$ 且 $n u m s [j] > n u m s [i]$

初始化： $d p [0] [0] = d [0] [1] = 1$

class Solution {
public:
    int dp[1005][2];

    int wiggleMaxLength(vector<int>& nums) {
        memset(dp, 0, sizeof dp);
        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.size(); i ++ ) {
            dp[i][0] = dp[i][1] = 1;
            for (int j = 0; j < i; j ++ ) {
                if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
                if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
            }
        } 
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.1.2 单调递增的数字

Leetcode 738

参考题解

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);
        int flag = strNum.size(); // 标记赋值9从哪里开始
        for (int i = strNum.size() - 1; i > 0; i -- ) 
            if (strNum[i - 1] > strNum[i])
                flag = i, strNum[i - 1] -- ;
        for (int i = flag; i < strNum.size(); i ++ )
            strNum[i] = '9';
        return stoi(strNum);
    }  
};
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2 贪心解决股票问题

2.2.1 买股票的最佳时机 Ⅱ

Leetcode 122

贪心思路：首先要知道，这个题目利润是可以分解的！即f分解为每一天的利润，每天的利润序列如下：

$\cdots , (prices[1] - prices[0)$

那么要是最终利润最多，就只需要统计为正数的利润即可，正利润的区间就是股票买卖的区间。

注意利润是从第二天开始统计的

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

2.2.2 买股票的最佳时机含手续费

2.3 两个维度权衡问题

2.3.1 分发糖果

Leetcode 135

一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

这里第二种情况需要从右向左遍历，是因为 rating[i] 与 rating[i-1] 相比较的时候需要用到 rating[i] 与 rating[i+1] 的信息！

同时也要注意在第二种情况中，需要选择当前情况取值与第一种情况取值的最大值。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i ++ ) // 从左往右
            if (ratings[i] > ratings[i - 1]) 
                candyVec[i] = candyVec[i - 1] + 1;
        for (int i = ratings.size() - 2; i >= 0; i -- ) // 从右往左
            if (ratings[i] > ratings[i + 1])
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
        int res = 0;
        for (int x: candyVec) res += x;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3.2 根据身高重建队列

Leetcode 406

本题有两个维度，h 和 k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列。

先按照身高 h 按从大到小排序，然后只需要按照 k 为下标重新插入队列即可。

版本一：

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> que;
        for (int i = 0; i < people.size(); i ++ ) {
            int pos = people[i][1];
            que.insert(que.begin() + pos, people[i]);
        }
        return que;
    }

    static 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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上面使用 vector 非常费时，C++ 中 vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector 底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。

所以使用 vector（动态数组）来 insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是 $O(n^2)$ 了，甚至可能拷贝好几次，就不止 $O(n^2)$ 了。

版本二：使用链表

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多
        for (int i = 0; i < people.size(); i ++ ) {
            int pos = people[i][1];
            std::list<vector<int>>::iterator it = que.begin();
            while (pos -- ) it ++ ;
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }

    static 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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.4 Dota2 参议院

Leetcode 649

优先消灭自己后面的对手，因为前面的对手已经使用过权利了，而后序的对手依然可以使用权利消灭自己的同伴！

实现代码，在每一轮循环的过程中，去过模拟优先消灭身后的对手，其实是比较麻烦的。

这里有一个技巧，就是用一个变量记录当前参议员之前有几个敌对对手了，进而判断自己是否被消灭了。这个变量我用 flag 来表示。

当 flag 大于 0 时，R 在 D 前出现，R 可以消灭 D。当 flag 小于 0 时，D 在 R 前出现，D 可以消灭 R。

class Solution {
public:
    string predictPartyVictory(string senate) {
        bool R = true, D = true; // 表示该轮结束之后，字符串里依然存在R。D同理
        int flag = 0; 
        while (R && D) {
            R = false, D = false;
            for (int i = 0; i < senate.size(); i ++ ) {
                if (senate[i] == 'R') {
                    if (flag < 0) senate[i] = 0;
                    else R = true; // 本轮循环结束有R
                    flag ++ ;
                }
                if (senate[i] == 'D') {
                    if (flag > 0) senate[i] = 0;
                    else D = true;
                    flag -- ;
                }
            }
        }
        return R == true ? "Radiant" : "Dire";
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、有点难度

3.1 区间问题

3.1.1 跳跃游戏

Leetcode 55

这个问题不在于每次应该跳几步，而应该考虑每次最多能跳到哪里，即最大覆盖范围。

贪心思路：每次取最大跳跃步数（取最大覆盖范围），如果最后能够覆盖到终点，即可以跳到终点。

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

3.1.2 跳跃游戏 Ⅱ

Leetcode 45

思路见参考题解

版本一：

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

版本二：

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

3.1.3 用最少数量的箭引爆气球

Leetcode 452

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (!points.size()) return 0;
        sort(points.begin(), points.end(), cmp); // 按照左边界排序
        int res = 1; // point不空至少一支箭
        for (int i = 1; i < points.size(); i ++ ) 
            if (points[i][0] > points[i - 1][1]) res ++ ; // 不重叠
            else points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小有边界
        return res;
    }

    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.1.4 无重叠区间

Leetcode 435

思路一：按照右边界排序

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (!intervals.size()) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1, end = intervals[0][1]; // count非交叉区间数目 end区间分割点
        for (int i = 1; i < intervals.size(); i ++ ) 
            if (end <= intervals[i][0])
                end = intervals[i][1], count ++ ;
        return intervals.size() - count;
    }

    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路二：按照左边界排序，直接求重叠的区间数目

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (!intervals.size()) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0, end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i ++ ) 
            if (intervals[i][0] >= end) end = intervals[i][1]; // 无重叠
            else end = min(end, intervals[i][1]), count ++ ;
        return count;
    }

    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路二精简版本：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (!intervals.size()) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0;
        for (int i = 1; i < intervals.size(); i ++ ) 
            if (intervals[i][0] < intervals[i - 1][1]) // 重叠
                intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]), count ++ ;
        return count;
    }

    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路三：将 3.1.3 Leetcode 452 用最少数量的箭引爆气球修改一下即可，箭的数目就是重叠区间数目。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (!intervals.size()) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int res = 1;
        for (int i = 1; i < intervals.size(); i ++ ) 
            if (intervals[i][0] >= intervals[i - 1][1]) res ++ ; // 这里条件改了
            else intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
        return intervals.size() - res;
    }

    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1]; // 这里按照左边界或者有边界排序结果一样
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.1.5 划分字母区间

Leetcode 763

统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[30] = {0}; // 记录字符 i 最后出现的位置
        for (int i = 0; i < s.size(); i ++ ) hash[s[i] - 'a'] = i;
        vector<int> res;
        int l = 0, r = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            r = max(r, hash[s[i] - 'a']);
            if (i == r) res.push_back(r - l + 1), l = i + 1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.1.6 合并区间

Leetcode 56

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if (!intervals.size()) return res;
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i ++ )
            if (res.back()[1] >= intervals[i][0]) 
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            else res.push_back(intervals[i]);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2 最大子序和

Leetcode 53

贪心思路：当前 “连续和” 为负数的时候立刻放弃，从下一个元素重新计算 “连续和”，因为负数加上下一个元素 “连续和” 只会越来越小。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN, count = 0; // count记录中间结果
        for (int i = 0; i < nums.size(); i ++ ) {
            count += nums[i];
            if (count > res) res = count;
            if (count <= 0) count = 0;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

3.3 加油站

Leetcode 134

思路一：直接从全局进行贪心选择，情况如下：

情况一：如果 gas 的总和小于 cost 总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i] 为一天剩下的油，i 从 0 开始计算累加到最后一站，如果累加没有出现负数，说明从 0 出发，油就没有断过，那么 0 就是起点。
情况三：如果累加的最小值是负数，汽车就要从非 0 节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0, min = INT_MAX; // curSum油量之和 min油箱里的油量最小值
        for (int i = 0; i < gas.size(); i ++ ) {
            int rest = gas[i] - cost[i]; // 当天剩余的油量
            curSum += rest;
            if (curSum < min) min = curSum;
        }
        if (curSum < 0) return -1; // 情况一
        if (min >= 0) return 0; // 情况二
        for (int i = gas.size() - 1; i >= 0; i -- ) { // 情况三
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路二：

首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明各个站点的加油站剩油量 rest[i] 相加一定是大于等于零的。
假设每个加油站的剩余量 rest[i] 为 gas[i] - cost[i]，i 从 0 开始累加 rest[i]，和记为 curSum，一旦 curSum 小于零，说明 [0, i] 区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从 i+1 算起，再从 0 计算 curSum。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0, totalSum = 0, start = 0;
        for (int i = 0; i < gas.size(); i ++ ) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) start = i + 1, curSum = 0;
        }
        if (totalSum < 0) return -1;
        return start;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

3.4 监控二叉树

Leetcode 968