代码随想录算法训练营Day26 | Leetcode 455 分发饼干 Leetcode 376 摆动序列 Leetcode 53 最大子序和
Leetcode 455 分发饼干
题目链接:455. 分发饼干 - 力扣(LeetCode)
代码随想录题解:代码随想录 (programmercarl.com)
思路:将小饼干优先喂饱小胃口
代码:
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end()); sort(s.begin(),s.end());int index=0;for(int i=0;i<s.size();i++){if(index<g.size()&&g[index]<=s[i]){index++;}}return index;}
};
Leetcode 376 摆动序列
题目链接:376. 摆动序列 - 力扣(LeetCode)
代码随想录题解:代码随想录 (programmercarl.com)
思路:将数组中的数看成折线图的点,只记录波峰和波谷的点。
代码:
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size()<=1){return 1;}if(nums.size()==2&&nums[0]!=nums[1]){return 2;}if(nums.size()==2&&nums[0]==nums[1]){return 1;}int count=1;int curdiff=0;int prediff=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){count++;prediff=curdiff;}}return count;}
};
Leetcode 53 最大子序和
题目链接:53. 最大子数组和 - 力扣(LeetCode)
代码随想录题解:代码随想录 (programmercarl.com)
思路:记录当前和的值,如果和为负数那么就重新记录,因为和为负数肯定就不是最大值了。
代码:
class Solution {
public:int maxSubArray(vector<int>& nums) {int result=INT32_MIN;int count=0;for(int i=0;i<nums.size();i++){count+=nums[i];if(count>result){result=count;}if(count<0){count=0;}}return result;}
};