455. 分发饼干
题目链接:https://leetcode.cn/problems/assign-cookies/
题目难度:简单
文章讲解:https://programmercarl.com/0455.分发饼干.html
视频讲解:https://www.bilibili.com/video/BV1MM411b7cq
题目状态:初次有贪心算法的总体概念,有点懵
思路:
先将饼干尺寸大的满足胃口大的小孩,直到遍历完。
代码:
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int index = s.size() - 1;
int res = 0;
for(int i = g.size() - 1; i >= 0; --i) {
if(index >= 0 && s[index] >= g[i]) {
res++;
index--;
}
}
return res;
}
};
376. 摆动序列
题目链接:https://leetcode.cn/problems/wiggle-subsequence/
题目难度:中等
文章讲解:https://programmercarl.com/0376.摆动序列.html
视频讲解:https://www.bilibili.com/video/BV17M411b7NS
题目状态:贪心好难,只能看题解,自己做一点思路也没有
思路:
记录一下每个元素的前后坡度(有正负的),然后判断前后坡度符号是否一致,如果不一致就加1,如果一致就跳过。
注意:当有平坡出现的时候,只需要记录一次,并且前坡只有在发生改变的时候在需要变化。
代码:
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. 最大子数组和
题目链接:https://leetcode.cn/problems/maximum-subarray/
题目难度:中等
文章讲解:https://programmercarl.com/0053.最大子序和.html
视频讲解:https://www.bilibili.com/video/BV1aY4y1Z7ya
题目状态:还是学习思路...
思路:
先遍历前面的和,当前面的和为负数的时候,那个前面所有的内容相加就对后面的元素没有作用,直接从后面元素开始,一直遍历结束。期间会记录所有遍历的最大值。
代码:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int count = 0;
int res = INT_MIN;
for(int i = 0; i < nums.size(); ++i) {
count += nums[i];
if(count > res) res = count;
if(count <= 0) count = 0;
}
return res;
}
};
标签:题目,nums,int,res,随想录,part1,算法,https,com
From: https://www.cnblogs.com/frontpen/p/18330357