455.分发饼干
这道题我用的其实是双指针的做法。还没看Carl的视频，不知道这算不算贪心算法。
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int res = 0;
int s_ptr = 0;
for(int i=0; i<g.size() && s_ptr<s.size(); i++){
if(g[i] <= s[s_ptr]){
res++;
s_ptr++;
}
else{
while(s_ptr<s.size() && g[i] > s[s_ptr]){
s_ptr++;
}
if(s_ptr<s.size() && g[i] <= s[s_ptr]){
res++;
s_ptr++;
}
}
}
return res;
}
};
因为上面那个看起来比较不好理解，我又写了个简单易读的版本。逻辑还是一样的。这两次写都忘了在匹配之后给相应的ptr++。
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int res = 0;
int s_ptr = 0;
int g_ptr = 0;
while(g_ptr<g.size() && s_ptr<s.size()){
if(g[g_ptr] <= s[s_ptr]){
res++;
s_ptr++;
g_ptr++;
}
else{
s_ptr++;
}
}
return res;
}
};
376. 摆动序列
这道题不是独立做出来的。自己想的有些复杂，其实没那么复杂。我总想着会不会正确答案的初始的点会不是第一个数，其实不会这样。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1)
return nums.size();
int pre_gap = 0;
int cur_gap = 0;
int result = 1;
for(int i=0; i<nums.size()-1; i++){
cur_gap = nums[i+1]-nums[i];
if((cur_gap>0 && pre_gap<=0) || (cur_gap<0 && pre_gap>=0)){
result++;
pre_gap = cur_gap;
}
}
return result;
}
};
53. 最大子序和
想了一个下午都没写出来。这道题之前做过好几遍了，可就是写不出来。
我理解的思路是对的：如果当前的sum小于0，那就不和后面的数加到一起。因为加到一起只会越来越小。但是我就是无法把它代码化。
看了Carl的视频理解了，是需要一个即时更新的count，去算加上当前的数等于多少，然后就有了两种情况：
- 如果大于result，那就把result赋值为现在的数。
- 如果当前更新过的count成了负数，那就把这个count算成0。我们通过这种方式去模拟了把前面的值取消，而从下一个值重新加出一个新的count。
我们还有一个result，去记整个数据里最大的子序和是多少。如果当前的count值比result大，就说明找到了更大的子序和，就需要更新result了。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for(int i=0; i<nums.size(); i++){
count = count + nums[i];
if(count > result){
result = count;
}
if(count<0){
count = 0;
}
}
return result;
}
};
