果洛营销网站建设哪家好,做网站买什么服务器 便宜,广告营销策略,网站支付接口怎么做代码随想录算法训练营
—day27 文章目录 代码随想录算法训练营前言一、贪心算法理论基础二、455.分发饼干三、376. 摆动序列53. 最大子数组和总结 前言
今天是算法营的第27天#xff0c;希望自己能够坚持下来#xff01; 今日任务#xff1a; ● 贪心算法理论基础 ● 455.…代码随想录算法训练营
—day27 文章目录 代码随想录算法训练营前言一、贪心算法理论基础二、455.分发饼干三、376. 摆动序列53. 最大子数组和总结 前言
今天是算法营的第27天希望自己能够坚持下来 今日任务 ● 贪心算法理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和 一、贪心算法理论基础 文章讲解 视频讲解 题目大纲
贪心的本质是选择每一阶段的局部最优从而达到全局最优。 贪心没有套路说白了就是常识性推导加上举反例。贪心的题目要么很简单要么没做过就想不出来思路。遇到没思路的题目不要想太久马上看题解积累思路。 二、455.分发饼干 题目链接 文章讲解 视频讲解 思路
这里的局部最优是尽量用大的饼干去满足大的胃口或者反过来用小的饼干满足小的胃口先对饼干和胃口排序从后往前遍历胃口优先用最大的饼干去匹配大胃口如果满足的话则饼干index往前这里要注意index0累加计数。
代码如下
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {//先排列升序sort(g.begin(), g.end());sort(s.begin(), s.end());int index s.size() - 1;int result 0;for (int i g.size() - 1; i 0; i--) { //遍历胃口if (index 0 s[index] g[i]) { //遍历饼干用最大的饼干匹配index--;result;}}return result;}
};三、376. 摆动序列 题目链接 文章讲解 视频讲解 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值头和尾。
整体最优整个序列有最多的局部峰值从而达到最长摆动序列。
因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了
思路
用当前元素分别和前一元素后一元素的差的正负来判断是否有摆动preDiff nums[i 1] - nums[i]curDiff nums[i] - nums[i - 1]preDiff和curDiff一正一负时说明出现了摆动。
这是我们思考本题的一个大体思路但本题要考虑三种情况 情况一上下坡中有平坡 平坡有4个2那么考虑删掉左边3个2的话遍历到最后一个2时的条件就是prediff 0 curdiff 0所以判断峰值的条件就应该是 (preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)
情况二数组首尾两端 题目中说了如果只有两个不同的元素那摆动序列也是 2。 那么为了统计到这种情况默认最右端是一个摆动result初始化为1且遍历只遍历到倒数第二个i nums.size() - 1再加上情况一讨论的判断条件 curDiff 0 preDiff 0那么result就会得到答案2.
情况三单调坡中有平坡 为了避免nums[1]和nums[2]都各自统计了一次摆动只需要在这个坡度摆动变化的时候更新 prediff 就行也就是图上的1这样 prediff 在 单调区间有平坡的时候 就不会发生变化造成我们的误判。
class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size() 1) return nums.size();int preDiff 0; //nums[i 1] - nums[i]int curDiff 0; //nums[i] - nums[i - 1]int result 1; //默认最右边有一个峰值//只遍历到倒数第二个因为最右边一个已经算成一个峰值了for (int i 0; i nums.size() - 1; i ) {curDiff nums[i 1] - nums[i];//出现峰值if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;preDiff curDiff; //当遇到摆动变化时才更新prediff}}return result;}
};53. 最大子数组和 题目链接 文章讲解 视频讲解 思路
当累加和是负数时继续往后加都是让后面的数更加小所以当累加和为负时舍弃掉当前的累加重新从下一个元素开始累加并且在过程中记录累加的最大值。
代码如下
class Solution {
public:int maxSubArray(vectorint nums) {int result INT_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;}
};总结
今天第一天的贪心算法代码其实都不难难的是思路需要多积累一些解题思路才行。
明天继续加油
