LeetCode 31天

455. 分发饼干

class Solution {
   
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
   
        // 先排序
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0;
        int j = 0;
        while (i < g.size() && j < s.size()) {
   
            if (s[j] >= g[i]) {
   
                i++;
                j++;
            }
            else {
   
                j++;
            }
        }
        return i;
    }
};

376. 摆动序列

class Solution {
   
public:
    int wiggleMaxLength(vector<int>& nums) {
   
        // 贪心策略
        if (nums.size() <= 1) {
   
            return nums.size();
        }
        int curDiff = 0;
        int preDiff = 0;
        int res = 1;
        for (int i = 0; i<nums.size()-1; i++) {
   
            curDiff = nums[i+1]-nums[i];
            if ((preDiff >=0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)){
   
                res++;
                preDiff = curDiff;
            }
        }
        return res;
    }
};

53. 最大子数组和

class Solution {
   
public:
    int maxSubArray(vector<int>& nums) {
   
        // 贪心
        // int res = INT32_MIN;
        // int count = 0;
        // for (int i = 0; i<nums.size();i++) {
   
        //     count += nums[i];
        //     if (count > res)
        //         res = count;
        //     if (count < 0) {
   
        //         count = 0;
        //     }
        // }
        // 动态规划
        if (nums.size() == 0)
            return 0;
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i<nums.size(); i++) {
   
            dp[i] = max(dp[i-1] + nums[i],nums[i]);
            if(dp[i] > res)
                res = dp[i];
        }
        return res;
    }
};

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

class Solution {
   
public:
    int maxProfit(vector<int>& prices) {
   
        // 贪心
        int res = 0;
        for (int i = 1; i<prices.size(); i++) {
   
            if (prices[i]-prices[i-1] > 0){
   
                res += prices[i] - prices[i-1];
            }
        }
        // 动态规划
        
        return res;
    }
};

55. 跳跃游戏

class Solution {
   
public:
    bool canJump(vector<int>& nums) {
   
        // 能覆盖的最远范围
        int cover = 0;
        if (nums.size() == 0)
            return true;
        // 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 ans = 0;
        int curDistance = 0;
        int nextDisdance = 0;
        for (int i = 0; i < nums.size(); i++) {
   
            nextDisdance = max(nextDisdance, nums[i] + i);
            if (curDistance == i) {
   
                ans ++;
                curDistance = nextDisdance;
                if (nextDisdance >= nums.size()-1)
                    break;
            }
        }
        return ans;
    }
};