day31打卡

455. 分发饼干 - 力扣（LeetCode）

思路：用贪心的策略，排序两个数组，用最大的饼干倒着遍历孩子找出对应的第一个能满足的孩子，再继续向前遍历，直到饼干吃完即可。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {//排序sort(g.begin(), g.end());sort(s.begin(), s.end());//记录数量int ret = 0;int tmp = s.size() - 1;for(int i = g.size()-1; i >= 0; i--){if(tmp >= 0 && s[tmp] >= g[i]){ret++;tmp--;}}return ret;}
};

376. 摆动序列 - 力扣（LeetCode）

动态规划，思路：

dp表：

​ 使用两个dp表，一个记录以i结尾，最后一个位置呈上升趋势的最长摆动序列的长度；

​ 另一个记录，以i为结尾，最后一个位置呈下降趋势的最长摆动序列的长度

状态转移方程：

​ 以i为结尾，它的前一个位置可以是[0, i-1]，所以我们设j为[0, i-1]区间的某个位置

所以f[i]可以分为：

• 子序列长度为1，f[i] = 1
• 子序列长度大于1，由于结尾要为上升趋势，所以nums[i] > nums[j]并且j结尾需要呈下降趋势，所以最长摆动序列就是g[j]+1。

g[i]可以分为：

• 子序列长度为1，g[i] = 1
• 子序列长度大于1，结尾需要呈下降趋势，所以nums[i] < nums[j]并且j结尾需要呈上升趋势，最长摆动序列就是f[i]+1

所以只需要取，当前长度分别和g[i]+1，f[i]+1的最大值即可。

初始化：

​ 所有元素能单独构成摆动序列，初始化为1即可。

填表顺序：

​ 从左向右

返回值：

​ 返回两个dp表中的最大值即可，我们也可以自己维护一个最大值ret

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if(n < 2) return n;//创建dp数组vector<int> f(n, 1), g(n, 1);//初始化//填表int ret = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j])f[i] = max(f[i], g[j]+1);if(nums[i] < nums[j])g[i] = max(g[i], f[j]+1);}ret = max(ret, max(f[i], g[i]));}//返回值return ret;}
};

53. 最大子数组和

动态规划，思路：

dp表：

​ dp[i]表示以i元素为结尾的所有子数组中的最大和。

状态转移方程：

​ dp[i]分为两种情况：

• 子数组长度为1：dp[i] = nums[i]

• 子数组长度大于1：dp[i]等于以i-1做结尾的dp数组加上nums[i]即可

  为：dp[i] = dp[i-1] + nums[i]

所以，状态转方程为dp[i] = max(nums[i], dp[i-1]+nums[i])

初始化：

​ 在最前面加上一个辅助节点，dp[0] = 0 ，在第一次填表时，会访问到该位置，为了保证结果不出错初始化为0。

填表：

​ 从左到右

返回值：

​ 返回dp表中的最大值即可。

class Solution {
public:int maxSubArray(vector<int>& nums) {//创建dp数组int n = nums.size();if(n == 1) return nums[0];vector<int> dp(n+1);//初始化dp[0] = 0;//填表for(int i = 1; i <= n; i++){dp[i] = max(nums[i-1], dp[i-1] + nums[i-1]);}//返回值int ret = INT_MIN;for(int i = 1; i <= n; i++)ret = max(ret, dp[i]);return ret;}
};