打卡第二十七天 455分发饼干 376摆动序列
第一题:
思路:
将大的饼干来满足胃口大的孩子。
先将小孩子的胃口和饼干的尺寸进行排序。然后从后往前遍历胃口,饼干的尺寸也从后往前。如果饼干尺寸大于等于小孩胃口,res++,然后比较下一块饼干。
代码如下:
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 index = s.size() - 1;
for(int i = g.size() - 1; i >= 0; i--){
if(index >= 0 && s[index] >= g[i]){
res++;
index--;
}
}
return res;
}
};
第二题:
思路:
首元素和尾元素都算摆动
考虑三种情况:
第一种是上下坡有平坡
第二种是首尾元素,直降将尾元素记录为1;
第三种是单调坡有平坡。
整体的思路是prediff >= 0 && curdiff < 0 || prediff <= 0 && curdiff > 0 就证明是摆动。
第三种情况就是当有坡度的时候才更行prediff的值。
代码如下:
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() == 1) return 1;
int res = 1;
int prediff = 0;
int curdiff = 0;
for(int i = 0; i < nums.size() - 1; i++){
curdiff = nums[i + 1] - nums[i];
if(prediff >= 0 && curdiff < 0 ||
prediff <= 0 && curdiff > 0){
res++;
prediff = curdiff;
}
}
return res;
}
};
第三题:
原题链接:53. 最大子数组和 - 力扣(LeetCode)
思路:
当前连续子数组的和如果小于0就直接从下一个元素进行计算。切记不能遇到负数就跳过。用res记录每次的遍历的最大和。
代码如下:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN;
int 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;
}
};
原文地址:https://blog.csdn.net/weixin_44593575/article/details/140164162
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!