算法：贪心算法

引言376. 摆动序列 - 力扣LeetCode55. 跳跃游戏 - 力扣LeetCode45. 跳跃游戏 II - 力扣LeetCode134. 加油站 - 力扣LeetCode135. 分发糖果 - 力扣LeetCode代码第一题这是一道简单的贪心题目目的是找最长的摆动序列我们的想法就是记录上一个差值和本次差值只要差值相反那么我们就对结果1class Solution { public: int wiggleMaxLength(vectorint nums) { if (nums.size() 1) { return nums.size(); } int preDiff 0; int curDiff 0; int res 1; for (int i 0; i nums.size() - 1; i) { curDiff nums[i 1] - nums[i]; if ((curDiff 0 preDiff 0) || (curDiff 0 preDiff 0)) { res; preDiff curDiff; } } return res; } };第二题这一题思路不是很难但是实现起来却比较困难就是要实现一个最大的覆盖面积在已经遍历过了的点里面而且还要做到循环的处理这里就是改变了停止的条件cover每一次都是要保证是最大的而只要遍历的点超过了这个最大的覆盖区说明根本到达不了这个地方。class Solution { public: bool canJump(vectorint nums) { int cover 0; if (nums.size() 1) { return true; } for (int i 0; i cover; i) { cover max(cover, i nums[i]); if (cover nums.size() - 1) { return true; } } return false; } };第三题这一题相比于上一题有一个不同的地方就是判断走到终点要几步那么我们可以延续上一题的思路我们每当走到一个范围的终点的时候就会更新我们的范围不过在更新之前我们会判断这个范围与终点之间的关系。不过这一题和上一题有一个不同的地方就是这一题的范围不是在一边循环一边变化的是走完一个范围之后才会更新的这个也是因为我们题目里面已经保证了可以到达终点。class Solution { public: int jump(vectorint nums) { if (nums.size() 1) { return 0; } int ans 0; int nextDistance 0; int curDistance 0; for (int i 0; i nums.size(); i) { nextDistance max(nums[i] i, nextDistance); if (i curDistance) { ans; curDistance nextDistance; if (nextDistance nums.size() - 1) { break; } } } return ans; } };第四题我们创建一个数组来记录一下两个数组的差这样子就可以转化问题为从哪一个地方开始相加可以让和一直是正数。首先我们一定要先判断一下整个和相加一定要是正数否则无论从哪里开始都不可能保证是正数。然后我们按照顺序开始相加但是只要遇到了负数我们就从下一个开始重新计数。首先我们一开始都会对这个方法有疑问因为如果满足之后的和是正数但是一定可以保证再次加上之前的数也能是正数嘛~~~ 但是注意我们之前已经单独判断所有和加上去一定是正数了所以我们现在的所有操作是找到起点因为是这个起点是一定存在的既然之前的点已经测试过了不可以那么就往后面继续测呗~~~class Solution { public: int canCompleteCircuit(vectorint gas, vectorint cost) { vectorint nums(gas.size(), 0); for (int i 0; i gas.size(); i) { nums[i] gas[i] - cost[i]; } int index gas.size(); int sum 0; for (int i 0; i index; i) { sum nums[i]; } if (sum 0) { return -1; } sum 0; int startPos 0; bool flag true; for (int i 0; i index; i) { sum nums[i]; if (sum 0) { sum 0; startPos i 1; continue; } } return startPos; } };第五题这一题很难因为我们需要顾及左边又要顾及右边这种题目我们千万不要一下子兼顾两边我们要遍历两边先左边再右边。我们先把所有的数组都设置为1然后从左到右遍历只要右边比左边大那么右边的值就比左边的值大1。然后我们再从右边到左边遍历也就是如果右边大于左边那么就比左边的糖果大1但是因为也要满足上一次遍历的结果也就是右边比左边大的这个所以我们要利用上一次已经得到的结果1。不过一定要注意的是这两个数组是两个结果所以很可能对于一个点有两个结果我们为了要满足两次遍历的结果所以要取最大值。比如有可能1 2 3 4 5 1那么对于5这个数我们最后的结果应该是5个糖果。class Solution { public: int candy(vectorint ratings) { int sum 0; vectorint res(ratings.size(), 1); int index ratings.size(); for (int i 1; i index; i) { if (ratings[i] ratings[i - 1]) { res[i] res[i - 1] 1; } } for (int i index - 1; i 0; i--) { if (ratings[i - 1] ratings[i]) { res[i - 1] max(res[i - 1], res[i] 1); } } for (int result : res) { sum result; } return sum; } };