1. 455. 分发饼干

  1. class Solution {
  2. public:
  3.     int findContentChildren(vector<int>& g, vector<int>& s) {
  4.         //先排序
  5.         sort(g.begin(),g.end());
  6.         sort(s.begin(),s.end());
  8.         //遍历s的index,饼干数组的下标
  9.         int index=s.size()-1; 
  11.         //喂饱的小孩数
  12.         int result=0;  
  14.         //大饼干喂给胃口大的-->局部最优
  15.         for(int i=g.size()-1;i>=0;i--){
  16.             //先判断index, 否则若index==0,则 s[index]越界报错
  17.             if(index >= 0 && s[index] >= g[i]){
  18.                 result++;
  19.                 index--;
  20.             }
  21.         }
  22.         return result;
  23.     }
  24. };

2. 376. 摆动序列

  1. //贪心算法
  2. class Solution {
  3. public:
  4.     int wiggleMaxLength(vector<int>& nums) {
  5.         int n=nums.size();
  6.         if(n<=1){
  7.             return n;
  8.         }
  10.         //记录前一差值
  11.         int preDiff=0; 
  12.         //记录当前差值
  13.         int curDiff=0;
  14.         // 记录峰值个数，序列默认序列最右边有一个峰值
  15.         int result=1; 
  17.         for(int i=0;i<n-1;i++){
  18.             curDiff=nums[i+1]-nums[i];
  19.             //出现峰值 
  20.             if(( preDiff>=0 && curDiff<0 ) ||( preDiff<=0 && curDiff>0 ) ){
  21.                 result++;
  22.                 preDiff=curDiff;
  23.             }
  24.         }
  25.         return result;
  26.     }
  27. };
  29. //动态规划
  30. class Solution {
  31. public:
  32.     int wiggleMaxLength(vector<int>& nums) {
  33.         int n=nums.size();
  34.         //status and define dp[][0]代表山峰,dp[][1]为山谷。
  35.         vector<vector<int>> dp(n,vector<int>(2));
  37.         if(n<2){
  38.             return n;
  39.         }
  41.         //base case
  42.         dp[0][0]=1;
  43.         dp[0][1]=1;
  45.         //transform
  46.         for(int i=1;i<n;i++){            
  47.             dp[i][0]=1;
  48.             dp[i][1]=1;
  49.             //找山峰
  50.             for(int j=0;j<i;j++){
  51.                 if(nums[i]>nums[j]){
  52.                     dp[i][0]=max(dp[j][1]+1,dp[i][0]);
  53.                 }
  54.             }
  55.             //找山谷
  56.             for(int j=0;j<i;j++){                
  57.                 if(nums[i]<nums[j]){
  58.                     dp[i][1]=max(dp[j][0]+1,dp[i][1]);
  59.                 }
  60.             }
  61.         }
  62.         return max(dp[n-1][0],dp[n-1][1]); 
  63.     }
  64. };
  66. //另一种动态规划
  67. class Solution {
  68. public:
  69.     int wiggleMaxLength(vector<int>& nums) {
  70.         int n=nums.size();
  71.         //status and define dp_up[]代表最后一个为上升的最长序列长度,dp_down[]为最后一个为下降的最长序列长度。
  72.         vector<int> dp_up(n),dp_down(n);
  74.         if(n<2){
  75.             return n;
  76.         }
  78.         //base case
  79.         dp_up[0]=1;
  80.         dp_down[0]=1;
  82.         //transform
  83.         for(int i=1;i<n;i++){            
  84.             if(nums[i]>nums[i-1]){
  85.                 dp_up[i]=dp_up[i-1];
  86.                 dp_down[i]=max(dp_down[i-1],dp_up[i-1]+1);
  87.             }else if(nums[i]<nums[i-1]){
  88.                 dp_up[i]=max(dp_up[i-1],dp_down[i-1]+1);
  89.                 dp_down[i]=dp_down[i-1];
  90.             }else{
  91.                 dp_up[i]=dp_up[i-1];
  92.                 dp_down[i]=dp_down[i-1];
  93.             }
  94.         }
  95.         return max(dp_up[n-1],dp_down[n-1]); 
  96.     }
  97. };
  99. //另一种动态规划的优化
  100. class Solution {
  101. public:
  102.     int wiggleMaxLength(vector<int>& nums) {
  103.         int n=nums.size();
  104.         //status and define dp_up[]代表最后一个为上升的最长序列长度,dp_down[]为最后一个为下降的最长序列长度。
  106.         if(n<2){
  107.             return n;
  108.         }
  110.         //base case
  111.         int dp_up=1;
  112.         int dp_down=1;
  114.         //transform
  115.         for(int i=1;i<n;i++){            
  116.             if(nums[i]>nums[i-1]){
  117.                 // dp_up[i]=dp_up[i-1];
  118.                 // dp_up=dp_up;
  119.                 // dp_down[i]=max(dp_down[i-1],dp_up[i-1]+1);
  120.                 dp_down=max(dp_down,dp_up+1);
  121.             }else if(nums[i]<nums[i-1]){
  122.                 // dp_up[i]=max(dp_up[i-1],dp_down[i-1]+1);
  123.                 dp_up=max(dp_up,dp_down+1);
  124.                 // dp_down=dp_down;
  125.                 // dp_down[i]=dp_down[i-1];
  126.             }else{
  127.                 // dp_up[i]=dp_up[i-1];
  128.                 // dp_down[i]=dp_down[i-1];
  129.             }
  130.         }
  131.         return max(dp_up,dp_down); 
  132.     }
  133. };

3. 53. 最大子数组和

  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         int n=nums.size();
  6.         int result=0;  //记录累计结果
  7.         int m_max=INT_MIN;   //最大和
  8.         for(int i=0;i<n;i++){
  9.             result+=nums[i];
  10.             if(m_max<result){
  11.                 m_max=result;
  12.             }
  13.             if(result<=0){   //结果为负数 重新计数
  14.                 result=0;
  15.             }
  16.         }
  17.         return m_max;
  18.     }
  19. };

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result=0;
        //局部最优，每天的利润最大化
        for(int i=1;i<prices.size();i++){
            result+=max(prices[i]-prices[i-1],0);
        }
        return result;
    }
};

5. 55. 跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        //跳跃可覆盖的最大距离到终点时为整体最优，每个位置跳跃最大距离为局部最优
        int cover=0;  //当前下标

        //只有1个元素时，肯定可达
        if(nums.size()==1){
            return true;
        }
        for(int i=0;i<=cover;i++){
            //max(此位置上可覆盖的最大距离,之前的cover)
            cover=max(nums[i]+i,cover);
            //可以覆盖
            if(cover>=nums.size()-1){
                return true;
            }
        }
        return false;
    }
};

6. 45. 跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        //局部最优：每次走最远
        if(nums.size()==1){
            return 0;
        }

        int step=0;
        for(int i=0;i<nums.size();i++){

            //在此位置最大覆盖距离可以到达最后一个位置
            if(i+nums[i]>=nums.size()-1){
                step++;
                return step;
            }
            //不能到达时
            //记录每个元素跳跃后可再次可跳跃的最大位置
            int pos_max=0;
            //记录此次跳跃步数下标
            int pos=i+1;
            for(int j=i+1;j<i+1+nums[i];j++){
                //找跳跃到下一个格子的最大距离
                if(j+nums[j]>=pos_max){
                    pos_max=j+nums[j];
                    //下标减1
                    pos=j-1;
                }
            }
            i=pos;
            step++;
        }
        return step;
    }
};

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

class Solution {
public:
    static bool cmp(int a,int b){
        return abs(a)>abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        //按绝对值从大到小排列
        sort(nums.begin(),nums.end(),cmp);
        //遇到负数，转为正数
        for(int i=0;i<nums.size();i++){
            if(k>0&&nums[i]<0){
                nums[i]=-nums[i];
                k--;
            }
        }
        //K还没用完，反复转换最后一个负数
        if(k%2==1) nums[nums.size()-1]*=-1;
        return accumulate(nums.begin(),nums.end(),0);
    }
};

8. 134. 加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //先看总油量和总耗量
        int sum=0;
        //油箱剩余的油最小值
        int min_rest=INT_MAX;

        for(int i=0;i<gas.size();i++){
            sum+=gas[i]-cost[i];
            min_rest=min(sum,min_rest);
        }
        //总油量<总耗量,不可能跑完
        if(sum<0){
            return -1;
        }
        //油箱剩余的油每次都够，从0出发就可以
        if(min_rest>=0){
            return 0;
        }
        //都不行，那就先找油，找最先让油箱有min_rest的油,要从后往前找
        for(int i=gas.size()-1;i>=0;i--){
            min_rest+=gas[i]-cost[i];
            if(min_rest>=0){
                return i;
            }
        }
        return -1;
    }
};

//第二种贪心
//局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。
//全局最优：找到可以跑一圈的起始位置。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start=0;
        int today_sum=0;
        int sum=0;
        for(int i=0;i<gas.size();i++){
            today_sum+=gas[i]-cost[i];
            sum+=gas[i]-cost[i];
            //第i天出现负油量，重新开始计算，从i+1开始
            if(today_sum<0){
                start=i+1;
                today_sum=0;
            }
        }
        if(sum<0){
            return -1;
        }
        return start;
    }
};

9. 738. 单调递增的数字

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum=to_string(n);
        int flag=strNum.size();
        for(int i=strNum.size()-1;i>0;i--){
            if(strNum[i]<strNum[i-1]){
                strNum[i-1]--;
                flag=i;
            }
        }   
        for(int i=flag;i<strNum.size();i++){
            strNum[i]='9';
        }
        return stoi(strNum);

    }
};