力扣LeetCode-贪心算法

贪心算法

基本知识

1.思想

基于局部最优的选择逐渐推导出全局最优解

2.一般步骤

1. 将问题分解为若干个子问题；

2. 找出合适的贪心策略；

3. 求解每一个子问题的最优解；

4. 将局部最优解合成为全局最优解；

典型例题

1. LeetCode 376. 摆动序列

题目

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。 子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

思路

1. 求取摆动子序列元素个数，则与原数组峰值个数有关；

2. 遍历原数组，记录相邻两个数的差值，若后面相邻两数差值与之前异号，则摆动子序列元素个数加1；

代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1)return 1;
        int pre_off = 0, cur_off;//pre_off用于记录最后录入两个元素的差值的正负，cur_off用于记录原数组相邻两个数的差值
        int result = 1;
        for(int i=1; i<nums.size(); i  ){
            cur_off = nums[i] - nums[i-1];
            if((pre_off <= 0 && cur_off >0) || (pre_off >=0 && cur_off <0)){//pre_off需要设置=0是由于初始化时pre_off设置为0，后面由于pre_off = cur_off则不可能再出现=0可能
                result  ;
                pre_off = cur_off;
            }
        }
        return result;
    }
};

2. LeetCode 122. 买卖股票的最佳时机II

题目

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。 返回 你能获得的 最大 利润 。

思路

方法一（贪心算法）

1. 遍历数组，若后一天价格高于前一天则累加收益；

2. 上面操作能获得最大利润的原因是，遍历到某一天时并不确定当天是否进行买入，直到第二天看到存在利润才决定前一天的是否进行买入，而看到利润的同时并没有决定是否卖出，直至后面出现新利润才决定是否卖出；

方法二（动态规划）

1. p[i] [0]示第i 1天手中无股票，可能昨天没有或者昨天有今天卖出；

2. p[i] [1]表示第i 1天手中有股票，可能昨天有股票或者昨天没有今天买入；

3. 由前一天两种可能的状态推断今天两种可能的状态（获取较高的利润）；

代码

方法一（贪心算法）

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

方法二（动态规划）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> p(len, vector<int>(2, 0));
        p[0][0] = 0;
        p[0][1] = -prices[0];
        for(int i=1; i<len; i  ){
            p[i][0] = max(p[i-1][0], p[i-1][1] prices[i]);
            p[i][1] = max(p[i-1][1], p[i-1][0]-prices[i]);
        }
        return p[len-1][0];
    }
};

3. LeetCode 45. 跳跃游戏

题目

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

思路

1. 每次跳跃时，计算每个可跳跃节点中最远跳跃距离下标，当可跳跃节点遍历后，即进行下一次跳跃，跳跃次数增加1；

2. 用temp记录尝试过可跳跃节点最远跳跃下标，在每次可跳跃节点遍历后更新reach；

3. 当reach>=nums.size()-1时代表本次跳跃可以跳到最后，增加跳跃次数后，退出循环；

代码

class Solution {
public:
    int jump(vector<int>& nums) {
        int count = 0;//记录跳跃次数
        int reach = nums[0];//记录一次跳跃中可跳跃节点最远跳跃距离下标
        int temp = nums[0];//持续更新跳跃最远距离下标
        for(int i=1; i<nums.size(); i  ){
            temp = max(nums[i] i, temp);
            if(reach >=nums.size()-1){
                count  ;
                break;
            }
            if(i == reach){
                reach = temp;
                count  ;
            }
        }
        return count;
    }
};

4. LeetCode 1005. K次取反后最大化的数组和

题目

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

思路

1. 将数组按绝对值从大到小进行排序；

2. 从头遍历数组，将负数变为正数，同时k减1，当k为0或者数组遍历结束后退出循环；

3. 退出循环后，若k仍大于0，且为奇数时，则将数组最后一个元素取反；

4. 思想就是将最小的负数变为正数，若所有元素均为正数时，且变化次数剩余为奇数，则将最小正数直接取反；（若变化剩余次数为偶数，则可认为将任意一个数做偶次数取反变化，最终值不变化）

代码

class Solution {
private:
    static bool mycompare(const int &a, const int &b){
        return abs(a)>abs(b);
    }
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), mycompare);
        for(int i=0; i<nums.size() && k>0; i  ){
            if(nums[i] < 0){
                nums[i] = -nums[i];
                k--;
            }
        }
        if(k%2==1){
            nums[nums.size()-1] *= -1;
        }

        int result = 0;
        for(int i=0; i<nums.size(); i  ){
            result = nums[i];
        }
        return result;
    }
};

5. LeetCode 134. 加油站

题目

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i 1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

思路

1. 遍历一遍，用run记录总油量是否可以走完全程（即能否完成一圈）

2. oil用于记录从某一位置开始油箱中的当前油量，当油量为负数时，说明前一部分路程不能到达，开始位置应该设置为下一地点

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int oil = 0, run = 0, start = 0;
        for(int i=0; i<gas.size(); i  ){
            oil  = gas[i]-cost[i];
            run  = gas[i]-cost[i];
            if(oil < 0){
                start = i 1;
                oil = 0;
            }
        }
        return run>=0?start:-1;
    }
};

6. LeetCode 135. 分发糖果

题目

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

思路

1. 由于每个孩子所能获得的糖果同时与两边孩子评分有关，则单通过一个方向的遍历不能得到答案；

2. 从两个方向遍历，即可同时兼顾两边情况，当从左向右遍历时，若左边评分大于自身评分，则设置糖果数比左边大1，否则设置为1；

3. 当从右向左遍历时，若右边评分小于自身评分，则比较上次遍历后该位置糖果数与右边糖果数 1，取较大者，从而使该位置同时满足两个方向的要求；

4. 最终得到的数组即为所需糖果数最少的分配方案；

代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int>result(ratings.size(), 1);
        for(int i=1; i<ratings.size(); i  ){
            if(ratings[i] > ratings[i-1]){
                result[i] = result[i-1] 1;
            }
        }

        for(int i=ratings.size()-2; i>=0; i--){
            if(ratings[i] > ratings[i 1]){
                result[i] = max(result[i], result[i 1] 1);
            }
        }

        int count = 0;
        for(int i=0; i<result.size(); i  ){
            count  = result[i];
        }

        return count;
    }
};

7. LeetCode 406. 根据身高重建队列

题目

思路

方法一（vector插入元素）

1. 由于身高较小的人对身高较高的人参数无影响，则将数组按照身高从高到低进行排序，若身高相等则参数二较小的在前面；

2. 按照数组从左向右遍历，设置vector结果数组，依次将每个人按照第二参数添加到vector数组；

方法二（list插入元素）（省时）

1. 思路与方法一相同，唯一不同在于设置list结果链表；

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

   所以使用vector（动态数组）来insert，是费时的，因此使用链表速度更快；

代码

方法一（vector插入元素）

class Solution {
private:
    static bool mycompare(vector<int>a, vector<int>b){
        if(a[0] == b[0])
            return a[1]<b[1];
        return a[0]>b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), mycompare);
        vector<vector<int>>queue;
        for(int i=0; i<people.size(); i  ){
            queue.insert(queue.begin() people[i][1], people[i]);
        }
        return queue;
    }
};

方法二（list插入元素）

class Solution {
private:
    static bool mycompare(vector<int>a, vector<int>b){
        if(a[0] == b[0])
            return a[1]<b[1];
        return a[0]>b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), mycompare);
        list<vector<int>>queue;
        for(int i=0; i<people.size(); i  ){
            list<vector<int>>::iterator it = queue.begin();
            for(int j=0; j<people[i][1]; j  ){
                it  ;
            }
            queue.insert(it, people[i]);
        }
        vector<vector<int>>result(queue.begin(), queue.end());
        return result;
    }
};

8. LeetCode 452. 用最少数量的箭引爆气球

题目

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

思路

1. 将所有气球按照左边界从小到大进行排序，从左向右遍历数组，记录（保证本次射箭开始后至今所有气球均被引爆情况）射箭最大右边界；

2. 若遍历至气球左边界大于射箭右边界，则需要增加射箭次数，并更新射箭最大右边界；

3. 若遍历至气球右边界小于射箭右边界，为保证该气球被引爆，则需更改射箭右边界为该气球右边界；

代码

class Solution {
private:
    static bool mycompare(const vector<int>&a, const vector<int>&b){
        return a[0]<b[0];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size() ==1 )
            return 1;
        sort(points.begin(), points.end(), mycompare);
        int result = 1;
        for(int i=1; i<points.size(); i  ){
            if(points[i][0] > points[i-1][1]){
                result  ;
            }
            else{
                points[i][1] = min(points[i-1][1], points[i][1]);
            }
        }
        return result;
    }
};

9. LeetCode 435. 无重叠区间

题目

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

思路

方法一（记录不交叉区间个数）

1. 由于最右边界越小，为其它区间留下的空间越大，同时存在的区间数越多；

2. 对区间集合按照右边界从小到大进行排序；

3. 利用当前不交叉最右边界判断后面区间是否与前面区间重叠，并记录不交叉区间个数，同时更新最右边界；

4. 用区间总数减去不交叉区间个数即为所求；

方法二（记录交叉区间个数）

1. 将区间按照左边界从小到大进行排序，若左边界相等，则右边界较小的在前面；

2. 记录目前不交叉区间最右边界，若遍历当前区间右边界小于不交叉最右边界，则交叉区间个数加1，并且更新不交叉区间最右边界；

3. 若遍历当前区间左边界小于不交叉最右边界，则交叉区间个数加1；

4. 否则其他情况就为遍历当前区间左边界大于等于不交叉最右边界，则更新不交叉最右边界；

代码

方法一

class Solution {
private:
    static bool mycompare(const vector<int>&a, const vector<int>&b){
        return a[1]<b[1];
    }
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size() == 1)
            return 0;
        sort(intervals.begin(), intervals.end(), mycompare);
        int count = 1;// 用于记录不交叉集合个数
        int pre_end = intervals[0][1];
        for(int i=0; i<intervals.size(); i  ){
            if(pre_end <= intervals[i][0]){
                count  ;
                pre_end = intervals[i][1];
            }
        }
        return intervals.size() - count;
    }
};

方法二

class Solution {
private:
    static bool mycompare(const vector<int>&a, const vector<int>&b){
        if(a[0] == b[0]){
            return a[1]<b[1];
        }
        return a[0]<b[0];
    }
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size() == 1)
            return 0;
        int result = 0, pre_end;
        sort(intervals.begin(), intervals.end(), mycompare);
        pre_end = intervals[0][1];
        for(int i=1; i<intervals.size(); i  ){
            if(intervals[i][1]< pre_end){
                result  ;
                pre_end = intervals[i][1];
            }
            else if(intervals[i][0] < pre_end){
                result  ;
            }
            else{
                pre_end = intervals[i][1];
            }
        }
        return result;
    }
};

10. LeetCode 763. 划分字母区间

题目

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

思路

1. 遍历字符串，记录每个字母最后出现位置；

2. 设置begin用于记录每个段的起始下标，end用于记录每个段中各字母最后出现的最右下标；

3. 重新遍历字符串，不断更新end使其为该段中字母最后出现下标，直至遍历下标到达end则完成一段的分割，记录段中字符个数，继续循环；

代码

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

11. LeetCode 738. 单调递增的数字

题目

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

思路

1. 设置count用于记录循环层数，flag用于记录最左面不满足相邻位数字时循环层数，temp_n用于记录最左面不满足相邻位数字时左边剩余数字，low用于记录相邻位较低位，high用于记录相邻位较高位；

2. 整体相当于对n从右向左按位比较，当不满足时记录循环层数flag及左边剩余数字temp_n，至循环结束就可以找到最左面不满足条件的位置；

3. 利用temp_n与flag将temp_n重新扩充至原来位数，减一后即为不满足单调递增的结果；

4. 若flag为初始值0，则题目所给数字n满足单调递增，同时temp_n仍为初始值n则可以直接返回temp_n;

代码

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        int count = 0, flag=0, temp_n = n, low, high;
        while(n){
            low = n;
            n = n/10;
            high = n;
            count  ;
            if(low < high){
                flag = count;
                temp_n = n;
                n--;
            }
        }
        for(int i=0; i<flag; i  ){
            temp_n*=10;
        }
        return flag?temp_n-1:temp_n;
    }
};

12. LeetCode 714. 买卖股票的最佳时机含手续费

题目

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

思路

1. 设置一个买入的最低票价min，遍历股票价格数组，若股票价格小于min则更新min；

2. 若股票价格大于等于min，但小于等于min fee，则此时卖出不获利，继续循环；

3. 若股票价格大于min fee，此时可以获利，增加获利结果，但并不确定在此时卖出，更改min为该天股票价-fee，若后面出现比该min小，则确定在此次卖出，若后面出现比min fee大的股票价格，则此次不卖出；

代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int min = prices[0];
        int result = 0;
        for(int i=1; i<prices.size(); i  ){ 
            if(prices[i] < min){    //用于寻找股票买入点
                min = prices[i];
            }
            else if(prices[i]>=min && prices[i]<=min fee){    //抛弃无法获利点
                continue;
            }
            else{    //尝试在该点卖出股票，若后面出现新的股票买入点时则确定在该点卖出股票，否则若仍然该分支则为不在该点卖出股票；
                result  = prices[i] - min -fee;
                min = prices[i] - fee;   //用于后面卖出股票时，抵消多用的手续费
                                        //此外，min用于后面寻找买入点，只有比该值小的股票价格才有可能获利
            }
        }
        return result;
    }
};

13. LeetCode 968. 监控二叉树

题目

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

思路

1. 若使监控树所需最小摄像头数，则将每个叶子节点的父节点设置为摄像头；

2. 构造travel函数用于返回遍历节点的状态，返回0表示未覆盖，返回1表示覆盖，返回2表示摄像头；

3. 当遍历一个节点的左右节点都覆盖时，则返回0表示该节点没有必要安装摄像头，可由父节点设置摄像头将该节点覆盖；

4. 当遍历一个节点的左右节点存在未覆盖时，则返回2表示设置摄像头，只有这样才能将子节点覆盖；

5. 当遍历一个节点的左右节点存在摄像头时，则返回1表示覆盖，子节点的摄像头将本节点覆盖；

代码

/**
 * 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 {
private:
    int result;
    //travel返回值为0表示未覆盖
    //返回1表示覆盖
    //返回2表示摄像头
    int travel(TreeNode* node){
        if(!node)return 1;
        int left = travel(node->left);
        int right = travel(node->right);
        if(left==1 && right==1){
            return 0;
        }
        else if(left==0 || right==0){
            result  ;
            return 2;
        }
        else return 1;
        // else if(left==2 || right==2){
        //     return 1;
        // }
    }
public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        if(!root){
            return result;
        }
        if(travel(root) == 0){
            result  ;
        }
        return result;
    }
};

这篇好文章是转载于：学新通技术网