Leetcode 刷题笔记-Leetcode 101 第2章 贪心算法

Leetcode 刷题笔记-Leetcode 101 第2章 贪心算法

贪心算法

贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。

分配问题

Leetcode 455

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃一个饼干，且只有饼干的大小不小于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int childrenCount = 0;
        for(size_t i = 0;i<s.size() && childrenCount < g.size();i++){
            if(s[i] >= g[childrenCount]){
                ++childrenCount;
            }
        }
        return childrenCount;
    }
};

分析：用最小大小的饼干 (s)去满足最小饥饿度的孩子 (g)，一直满足到饥饿度最大的孩子，相当于双指针的移动。

贪心策略是给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。

错误：忘记检查g是否越界，可能发生所有饼干都能满足所有孩子，然而饼干还剩着的情况。下标运算一定要确认是否越界。

Leetcode 135

一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果。求解最少需要多少个糖果。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyNum(ratings.size(),1);
        for(size_t i = 0;i<ratings.size()-1;++i){
            if(ratings[i+1] > ratings[i] && candyNum[i+1] <= candyNum[i]){
                candyNum[i+1] = candyNum[i] + 1;
            }
        }
        for(size_t i = ratings.size()-1;i>0;--i){
            if(ratings[i-1] > ratings[i] && candyNum[i-1] <= candyNum[i]){
                candyNum[i-1] = candyNum[i] + 1;
            }
        }
        return accumulate(candyNum.cbegin(),candyNum.cend(),0);
    }
};

分析：首先至少有一个糖果分配好，然后从左向右扫一遍，如果右边的孩子评分高，则右边孩子的糖果=左边孩子的糖果+1，再从右往左扫一遍，如果左边的孩子评分高，则左边孩子的糖果=右边孩子的糖果+1。最后求和即可。

贪心策略：在每次遍历中，只考虑并更新相邻一侧的大小关系

错误：没有更新为相邻孩子+1，而是仅仅加了1，考虑不够完整。

区间问题

Leetcode 435

给定一个区间的集合 intervals ，返回 需要移除区间的最小数量，使剩余区间互不重叠。

class Solution {
public:
    static bool cmp(vector<int> &a,vector<int> &b){
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int intervalsCount = 1;
        int searchBack = intervals[0][1];
        size_t n = intervals.size();
        for(size_t i=0;i<n;++i){
            if (intervals[i][0] >= searchBack){
                intervalsCount += 1;
                searchBack = intervals[i][1];
            } 
        }
        return n - intervalsCount;
    }
};

分析：假设第一个区间是 k，k的左边没有任何区间，因此使用其他任何一个区间，只要右端点小于 k的右端点就可以了。而且右端点向左移动，比 k更优。因此首个区间就是所有可以选择的区间中右端点最小的那个区间 。后面只要去寻找其中与首个区间不重合并且右端点最小的区间即可。

贪心策略：优先保留结尾小且不相交的区间

错误1：没想明白右端点的问题

错误2：函数要加 static（但是不太明白）

错误3：使用引用传参，防止拷贝浪费时间

建议：一些比如数组大小的数字提前计算出来，避免反复计算。

练习

Leetcode 605

有一个很长的花坛，一部分地块种植了花，另一部分却没有。花不能种植在相邻的地块上。 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int flowerCount = 0;
        size_t m = flowerbed.size();
        if(m == 1){
            if(flowerbed[0] == 0){
                return true;
            }
            else if (flowerbed[0] == 1 && n == 1){
                return false;
            }
        }
        if(flowerbed[0] == 0 && flowerbed[1] == 0){
            flowerbed[0] = 1;
            flowerCount += 1;
        }
        if(flowerbed[m-1] == 0 && flowerbed[m-2] == 0){
            flowerbed[m-1] = 1;
            flowerCount += 1;
        }
        for(size_t i=1;i<m-1;i++){
            if(flowerbed[i] == 0 && flowerbed[i-1] == 0 && flowerbed[i+1] == 0){
                flowerbed[i] = 1;
                flowerCount += 1;
            }
        }
        return flowerCount >= n;
    }
};

分析：遍历即可，尤其注意开头部分和结尾部分。

错误：最后没有考虑等于条件也为 true

建议：判断太多，有更为简洁的解法，大致思路是计算相邻的 1之间能种多少个 0。

Leetcode 452

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，不知道具体位置，但是知道一个位置的范围。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，射进了气球的位置范围后，该气球就会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。给你一个数组 points ， 返回引爆所有气球所必须射出的最小弓箭数 。

class Solution {
public:
    static bool cmp(vector<int> &a,vector<int> &b){
        return a[1] < b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int n = points.size();
        int arrowCount = 1;
        int endPoint = points[0][1];
        for(size_t i=0;i<n;i++){
            if(points[i][0] > endPoint){
                ++arrowCount;
                endPoint = points[i][1];
            }
        }
        return arrowCount;
    }
};

分析：拿第一个气球来说，要是想射爆，最佳的方法就是射最右侧的位置，这样能射到的其他的气球数量也会增加，以此类推，构成贪心算法。

一遍AC

Leetcode 763

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26,-1);
        for(int i = s.size() - 1;i >= 0;i--){
            if(last[s[i] - 'a'] == -1){
                last[s[i] - 'a'] = i;
            }
        }
        vector<int> result;
        int start = 0;
        int end = 0;
        for(int i=0;i<s.size();i++){
            end = max(end,last[s[i] - 'a']);
            if(i == end){
                result.push_back(end - start + 1);
                start = i + 1;
            }
        }
        return result;
    }
};

分析：首先得到字符出现的最后的下标位置，然后重新遍历字符串，得到每个字符最后出现的位置。一旦前面的所有字符都出现完了，就算一个区间。

上述做法使用贪心的思想寻找每个片段可能的最小结束下标，因此可以保证每个片段的长度一定是符合要求的最短长度，如果取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。由于每次取的片段都是符合要求的最短的片段，因此得到的片段数也是最多的。

错误：思路有问题，没有做对

Leetcode 122

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润 。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int stockSum = 0;
        for(size_t i=0;i<prices.size()-1;i++){
            if(prices[i+1] > prices[i]){
                stockSum = stockSum+prices[i+1]-prices[i];
            }
        }
        return stockSum;
    }
};

分析：什么都不限制，涨了就卖就完事了，比较简单。贪心策略就是只要价格上涨就直接出售。

一遍AC

Leetcode 406

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

class Solution {
public:
    static bool cmp(vector<int> &a,vector<int> &b){
        if(a[0] != b[0]){
            return a[0] < b[0];
        }
        return a[1] > b[1];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        vector<vector<int>> result(people.size());
        sort(people.begin(),people.end(),cmp);
        for(size_t i=0;i<people.size();++i){
            int pos = people[i][1];
            for(size_t j=0;j<result.size();j++){
                if(result[j].empty()){
                    pos--;
                }
                if(pos == -1){
                    result[j] = people[i];
                    break;
                }
            }
        }
        return result;
    }
};

分析：将人员从低往高先排列，然后一个个进行插入。插入的人只会对后面的人有影响，因为后面的人的身高都会大于等于他。而对已经插入的人没有影响。因此插入的时候给后面的人要留出空位置，以便后面的人插入进去。如果身高相同，就去比较 ki。 ki更小一点的，说明这个人在靠前一点，也就是最小的 ki前面是不会有相同身高的人的，由于相同身高也会算在内，因此要先插入大 ki。

错误：思路有问题，没有做对

Leetcode 665

给你一个长度为 n 的整数数组 nums ，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                if(i == 1 || nums[i] >= nums[i - 2]){
                    nums[i - 1] = nums[i];
                }
                else{
                    nums[i] = nums[i - 1];
                }
                ++count;
            }
        }
        return count <= 1;
    }
};

分析：要多种情况一起考虑。。。。

错误：思路有问题，没有做对。另外不要去改 i+1啊。。判断什么修改什么好吧，要不就乱套了。

总结

贪心算法确实是比较好理解的，但是怎么贪心？什么时候贪心？这些问题都要去详细认真的思考，真正出题的时候不会如此直白，要多练多想。