代码随想录算法训练营刷题复习5 : 贪心算法 1/2

贪心复习01

每个题的思路都比较巧妙，没有太多的共通之处，今天的题复习起来稍有些慢。

1. 455. 分发饼干
   大饼干优先给大胃口，外层胃口内层饼干，双层遍历需要两个数组来记录是否使用过该饼干or胃口
2. 376. 摆动序列
   ①不需要逐个保留差值，使用pre和cur能够体现峰值就行，cur计算当前两个值的差值，pre为上一个差值，
   ②判断条件，pre总是>=0 或者 <=0 ，能够处理遇到相同元素的情况
3. 53. 最大子数组和
4. 122. 买卖股票的最佳时机 II
   这里进行n次交易（交易次数不限制），就假定进行的交易次数越多获得的利润越大。计算相邻两天的差值，大于0就计入我们的利润总和中。
5. 55. 跳跃游戏
   限制i的遍历范围为0到cover,也就是说在前面元素所能到达的最远范围内进行遍历
6. 45. 跳跃游戏 II
7. 1005. K 次取反后最大化的数组和
   按照绝对值排序，然后将负值转为正值，再看剩余的k，奇数则改变最小值的符号，为偶数说明一正一负抵消不需要修改
8. 134. 加油站 重点复习
   复习的时候才发现，第一遍只用暴力去做 超出时间限制了。
   局部最优：累加到达每一个加油站的gas[i]-cost[i]，得到的和如果为负值说明无法再继续前行，需要更换起点为i+1;
   判断所有加油站的gas[i]-cost[i]的和为负值说明没有办法实现，返回-1
9. 135. 分发糖果
   初始化为每个小朋友发1个糖果
   从左到右判断+从右到左判断（此轮需要比较更新值），最后累加

455. 分发饼干
大饼干优先给大胃口，外层胃口内层饼干，双层遍历需要两个数组来记录是否使用过该饼干or胃口

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        if(s.size()==0)
            return 0;
        //sort函数 不需要变量获取函数执行结果
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());

        vector<bool> used_g(g.size(),false);
        vector<bool> used_s(s.size(),false);
        int res=0;
        for(int i=g.size()-1;i>=0;i--) {
            for(int j=s.size()-1;j>=0;j--) {
                if(s[j] >= g[i] && used_s[j]==false && used_g[i]==false) {
                    res++;
                    used_g[i]=true;
                    used_s[j]=true;
                }
                else if(s[j]<g[i])
                    break;
                else if(used_s[j]==false){
                    continue;
                }
            }
        }
        return res;
    }
};

376. 摆动序列
①不需要逐个保留差值，使用pre和cur能够体现峰值就行，cur计算当前两个值的差值，pre为上一个差值，
②判断条件，pre总是>=0 或者 <=0 ，能够处理遇到相同元素的情况

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()<=1)
            return nums.size();
        
        int pre = 0;
        int cur = 0;
        int res = 1;
        for(int i=0;i<nums.size()-1;i++) {
            cur = nums[i+1]-nums[i];
            if((pre>=0 && cur<0) || (pre<=0 && cur>0) ){
                res++;
                pre = cur;
            }
        }
        return res;
    }
};

53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0]; 
        if(nums.size()==1)
            return res;
        else if(nums.size()==0)
            return 0;
        int max=nums[0];
        for(int i=1;i<nums.size();i++) {
            if(nums[i]+res < nums[i]) {
                res = nums[i];
            }
            else {
                res+=nums[i];
            }
            if(max<res)
                max = res;
        }
        return max;
    }
};

122. 买卖股票的最佳时机 II
这里进行n次交易（交易次数不限制），就假定进行的交易次数越多获得的利润越大。计算相邻两天的差值，大于0就计入我们的利润总和中。

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

55. 跳跃游戏
限制i的遍历范围为0到cover,也就是说在前面元素所能到达的最远范围内进行遍历

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()<=1)
            return true;
        int cover=0;
        //这里是限制i的遍历范围为0到cover,也就是说在前面元素所能到达的最远范围内进行遍历
        for(int i=0;i<=cover;i++) {
            cover = max(cover, i+nums[i]);
            if(cover >= nums.size()-1)
                return true;
        }
        return false;
    }
};

45. 跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1) {
            return 0;
        }
        int cur_cover = 0;
        int next_cover = 0;
        int res=0;
        for(int i=0;i<nums.size();i++) {
            next_cover = max(next_cover,i+nums[i]);
            //如果i走到了当前最大覆盖的下标位置
            if(i==cur_cover) {
                res++;
                cur_cover = next_cover;

                if(next_cover >= nums.size()-1) {
                    break;
                }
            }
        }
        return res;
    }
};

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

class Solution {
public:
    static bool cmp(int a, int b){
        return abs(a) > abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        //先按绝对值进行排序，然后k步内对负值改为正值
        sort(nums.begin(),nums.end(),cmp);
        for(int i=0;i<nums.size();i++) {
            if(nums[i] < 0 && k>0) {
                k--;
                nums[i]*=-1;
            }
        }
        // 如果负值都处理完了，就把最小值改为负值（偶次不用修改，奇数次改为负值）
        if(k%2!=0)
            nums[nums.size()-1]*=-1;
        int res = 0;
        for(int a : nums)
            res+=a;
        return res;
    }
};

134. 加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        //之前用暴力算法做的，超出时间限制
        //本题的贪心做法：如果到达每一个加油站计算gas[i]-cost[i]为正值 且其和total_sum 为正值，就一定有解
        int cur_sum=0;
        int total_sum=0;
        int start=0;
        for(int i=0;i<gas.size();i++) {
            cur_sum+=gas[i]-cost[i];
            total_sum += gas[i]-cost[i];
            //重新规划起点为i+1;
            if(cur_sum <0) {
                start = i+1;
                cur_sum = 0;
            }
        }
        //如果total_sum为负值，说明一定没解
        if(total_sum < 0)
            return -1;
        return start;
        
    }
};

135. 分发糖果

class Solution {
public:
    int candy(vector<int>& ratings) {
        if(ratings.size()<=1)
            return ratings.size();
        vector<int> t(ratings.size(),1);

        for(int i=1;i<ratings.size();i++) {
            if(ratings[i] > ratings[i-1])
                t[i] = t[i-1]+1;
        }

        for(int j=ratings.size()-2;j>=0;j--) {
            if(ratings[j+1] < ratings[j]) {
                t[j] = max(t[j],t[j+1]+1);
            }
        }

        int res = 0;
        for(int a:t) {
            res+=a;
        }
        return res;
    }
};