455.分发饼干
题目链接：https://leetcode.cn/problems/assign-cookies/description/
思路：
本题目给我们孩子的胃口值和饼干尺寸，每个孩子必须分配比胃口值大的饼干，要求尽可能多的分配。这就要求我们尽可能匹配和胃口值差不多大的饼干。
涉及到大小，我们首先给胃口值和饼干尺寸从小到大排序，这并不影响分配。然后我们采用双指针进行分配，从小到大枚举孩子和饼干：如果当前的饼干尺寸小于当前孩子胃口值，说明这一个孩子及之后的孩子吃这块饼干都不饱，只能把这块饼干舍去，遍历饼干的指针加一；如果当前饼干的尺寸大于等于孩子的胃口值，证明可以分给当前孩子，且这块饼干是最优解，给更大的饼干会浪费，这时双指针共同加一即可。
当饼干遍历完成后，孩子指针遍历了几个，就证明最多给几个孩子分饼干。
核心代码：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int l,r;
l=r=0;
sort(g.begin(),g.end());
sort(s.begin(),s.end());
while(l<g.size()&&r<s.size()){
if(s[r]>=g[l]){
l++;
r++;
}
else r++;
}
return l;
}
};376.摆动序列
题目链接：https://leetcode.cn/problems/wiggle-subsequence/description/
思路：
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。本题目就让我们找出最长的摆动子序列。
首先我们很容易就能想到，我们求摆动序列是看连续数字的差的正负，那我们对原序列求一阶差值即可。对于这个差值序列，我们判断正负是否交替不就好了吗？正负交替一次，摆动序列中的数就加一。连续的正值或者负值可以看成一个值，不影响性质。比如说 a-b 和 b-c ，如果均大于零，那两个数完全可以看成一个数 a-c ，相加即可，不影响对于摆动序列的贡献。
因此我们只需要求原序列的一阶差值序列，然后遍历求正负交替次数即可。正负交替次数加一就是摆动子序列的长度。
核心代码：
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n=nums.size();
if(n<=1) return n;
int last,ans;
last=nums[1]-nums[0];
if(!last) ans=1;
else ans=2;
for(int i=2;i<n;i++){
if(nums[i]==nums[i-1]) continue;
if((nums[i]-nums[i-1])*last<0||!last) ans++;
last=nums[i]-nums[i-1];
}
return ans;
}
};53.最大子数组和
题目链接：https://leetcode.cn/problems/maximum-subarray/description/
思路：
首先子数组和这一点我们可以想到利用前缀和。这样任意一个子数组的和其实就是终点的前缀和减去起点的前缀和。
我们考虑枚举终点，因为需要连续求前缀和，知道当前前缀和时，以前面任意点为起点的前缀和也就都知道了。那当前点为终点，前缀和固定，怎么找出最大子数组和？起点的前缀和越小，相减后的差值不就越大吗？因此我们只需要知道终点之前的最小前缀和就可以了。
枚举终点可以边求前缀和边枚举，找之前的最小前缀和可以开个变量记录。每求一次前缀和比较一次，记录最小值就好了。然后当前前缀和与记录的最小前缀和作差，就是以当前点为终点的最大子数组和，记录这个值的最大值就是整体的最大子数组和。
核心代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
int sum,minn,ans;
sum=minn=0;
ans=nums[0];
for(int i=0;i<n;i++){
sum+=nums[i];
ans=max(ans,sum-minn);
minn=min(minn,sum);
}
return ans;
}
};今日总结
今日学习时长2h，题目还算可以，今天做题状态很好。
