455. 分发饼干

思想是让每一块饼干给刚刚符合的人吃

class Solution {
public:
    // g孩子 s饼干
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int idx = 0;
        // 遍历饼干
        for (int i = 0; i < s.size(); i ++)
        {
            if (idx == g.size()) break;
            if (s[i] >= g[idx])
            {
                idx ++;
            }
        }
        return idx;
    }
};

376. 摆动序列

这题用贪心比较麻烦，特别是有平坦的情况时。

class Solution {
public:
    // dp
    int dp[1005][2];
    int wiggleMaxLength(vector<int>& nums) {
        memset(dp, 0, sizeof dp);
        int n = nums.size();
        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < n; i ++)
        {
            dp[i][1] = dp[i][0] = 1;
            for (int j = 0; j < i; j ++)
            {
                if (nums[j] < nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
                if (nums[j] > nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
            }
        }
        return max(dp[n-1][0], dp[n-1][1]);
    }
};

53. 最大子数组和

当 <0 时停止计算。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxn = -1e9, sum = 0;
        for (int i = 0; i < nums.size(); i ++)
        {
            sum += nums[i];
            if (sum > maxn) maxn = sum;
            if (sum < 0) sum = 0;
        }
        return maxn;
    }
};