代码随想录算法训练营刷题复习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;
    }
};

相关推荐

  1. 代码随想算法训练复习5 : 贪心算法 1/2

    2024-06-19 09:02:04       19 阅读
  2. 代码随想训练27day-贪心算法5

    2024-06-19 09:02:04       16 阅读
  3. 代码随想算法训练复习4 :单调栈

    2024-06-19 09:02:04       10 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-19 09:02:04       3 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-19 09:02:04       3 阅读
  3. 在Django里面运行非项目文件

    2024-06-19 09:02:04       2 阅读
  4. Python语言-面向对象

    2024-06-19 09:02:04       2 阅读

热门阅读

  1. Paddleocr数据增强调用逻辑

    2024-06-19 09:02:04       16 阅读
  2. leetcode139-Word Break

    2024-06-19 09:02:04       11 阅读
  3. Angular 2 数据显示

    2024-06-19 09:02:04       26 阅读
  4. 新手怎么使用GitLab?

    2024-06-19 09:02:04       17 阅读
  5. word常用的通配符大全

    2024-06-19 09:02:04       19 阅读
  6. Mellanox&nvidia ib高速网络异常排查FAQ

    2024-06-19 09:02:04       14 阅读
  7. Ubuntu 查看设备温度

    2024-06-19 09:02:04       11 阅读
  8. 5、分支对比 - 课件

    2024-06-19 09:02:04       16 阅读
  9. Python----多线程使用

    2024-06-19 09:02:04       13 阅读