白天做了五道，晚上九点上课回来补了四道，先睡吧。明天时间多点。

之后也得抽空把没独立完成的题重做一遍。

1. 分发饼干

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

由前向后遍历。但时间复杂度高了点。

看答案是从后向前遍历，优化不少。

因为既然最大的饼干无法满足胃口最大的孩子，那就不用再遍历后续的饼干了。而如果由前向后遍历，就要遍历后续饼干以满足胃口。

补：理解错了，从前向后也可以做到nlogn的时间复杂度。关键问题在于遍历两个数组不一定要两个for，因为饼干数组每次从断点开始遍历。

代码

#include <vector>
#include <algorithm>

using std::vector;
using std::sort;

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int res=0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int j=s.size()-1;
        for (int i=g.size()-1;i>=0&&j>=0;--i) {
            if (g[i]<=s[j]) 
            {
                ++res;
                --j;
            }
        }
        return res;
    }
};

2. 摆动序列

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

作图发现，只要删除峰和谷之间的数值。

还是很巧妙的。没经验不太好想出来……

这里preDiff可以等于0是因为初始值，但不用担心后续有0，因为要用curDiff更新，而后者不会有0。

保持区间波动，只需要把单调区间上的元素移除就可以了。

代码

#include <vector>
using std::vector;
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size()==1) return 1;
        if (nums.size()==2&&nums[0]!=nums[1]) return 2;
        int res=1;
        int preDiff=0,curDiff=0;
        for (int i=0;i<nums.size()-1;++i) {
            curDiff=nums[i+1]-nums[i];
            if ((curDiff>0&&preDiff<=0)||preDiff>=0&&curDiff<0) {
                res++;
                preDiff=curDiff;
            }
        }
        return res;
    }
};

3. 最大子数组和

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

也可以用dp做，但空间占用更大一些。

贪心法其关键在于：不能让“连续和”为负数的时候加上下⼀个元素，⽽不是 不让“连续和”加上⼀个负数，这块要想明白。

代码

#include <vector>
#include <algorithm>

using std::vector;

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

4. 跳跃游戏

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

要求输出true or false，说明不用关心具体在哪一层跳几步，只要知道我们的可达范围能否覆盖终点即可。

随想录说：

⼀些同学可能感觉，我在讲贪⼼系列的时候，题⽬和题⽬之间貌似没有什么联系？是真的就是没什么联系，因为贪⼼⽆套路！没有个整体的贪⼼框架解决⼀些列问题，只能是接触各种类型的题⽬锻炼⾃⼰的贪⼼思维！

确实只能堆经验。

代码

#include <vector>

using std::vector;
using std::max;
class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.size()==1) return true;
        int des=nums[0];
        for (int i=1;i<nums.size()-1;++i) {
            if (i>des) return false;
            else {
                des=max(des,i+nums[i]);
            }
        }
        return des>=nums.size()-1;
    }
};

5. 跳跃游戏 II

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

难度相比上一次又上升了。本来以为这次要考虑跳几步了，结果依然是从覆盖范围的角度考虑。

代码

#include <vector>
using std::vector;
using std::max;
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size()==1) return 0;
        int res=0;
        int curDis=0,nextDis=0;
        for (int i=0;i<nums.size();++i) {
            nextDis=max(nextDis,i+nums[i]);
            if (curDis==i) {
                if (i!=nums.size()-1) {
                    res++;
                    curDis=nextDis;
                    if (curDis>=nums.size()-1) break;
                }
                else break;
            }
        }
        return res;
    }
};

6. 打家劫舍 III

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

第一次遇到树形dp，学到了。

树形问题一定首先考虑遍历顺序，这题里面对父节点决策依赖于子节点状态，所以一定是后续。dp数组长度为2，分别是考虑抢不抢当前节点所能获取的最大收益。

代码

#include <vector>
using std::vector;
using std::max;
class Solution {
public:
    int rob(TreeNode* root) {
        return max(robTree(root)[0],robTree(root)[1]);
    }

    vector<int> robTree(TreeNode* cur) {
        if (cur==nullptr) return vector<int>{0,0};
        vector<int> dp(2,0);
        vector<int> left=robTree(cur->left);
        vector<int> right=robTree(cur->right);
        dp[0]=max(left[0],left[1])+max(right[0],right[1]);
        dp[1]=left[0]+right[0]+cur->val;
        return dp;
    }

};

7. 最长递增子序列

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

原来这题才算dp入门……

dp[i]的状态可以由dp[j]推算出来。其实就是遍历了长度为i时各种可能，取最大的。然后在各i中取最大的。

代码

#include <vector>
using std::vector;
using std::max;
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        int result=1;
        for (int i=0;i<nums.size();++i) {
            for (int j=0;j<i;++j) {
                if (nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1);
            }
            result=max(result,dp[i]);
        }
        return result;
    }
};

8. 最长连续递增序列

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

贪心很容易写出来，类似最大子数组和。

dp做法也不难，放一起了。

代码

#include <vector>
using std::vector;
using std::max;
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        // 贪心算法
        // int res=1;
        // int count=1;
        // for (int i=1;i<nums.size();++i) {
        //     if (nums[i]-nums[i-1]>0) {
        //         ++count;
        //         res=max(res,count);
        //     }
        //     else count=1;
        // }
        // return res;

        // dp
        int res=1;
        vector<int> dp(nums.size(),1);
        for (int i=1;i<nums.size();++i) {
            if (nums[i]>nums[i-1]) {
                dp[i]=dp[i-1]+1;
                res=max(dp[i],res);
            }
            else {
                dp[i]=1;
            }
        }
        return res;
    }
};

9. 最长重复子数组

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

题设有点没说明白，应该是连续子数组，我以为非连续也可。

使用二维dp数组，两层循环。ij表示数组1中以下标i-1元素为结尾，数组2中以下标j-1元素为结尾的子序列的最大公共长度。

代码

#include <vector>

using std::vector;
using std::max;

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        int res=0;
        for (int i=1;i<=nums1.size();++i) {
            for (int j=1;j<=nums2.size();++j) {
                if (nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1] +1;
                res=max(res,dp[i][j]);
            }
        }
        return res;
    }
};