前言
本篇为贪心算法专题，总共5道题目，记录我的解题思路和一些感悟，供大家参考~
376. 摆动序列
链接：376. 摆动序列
解题思路
- 主要的思路是处理平坡，也就是都是一样的值的情况
- 怎么找到峰值？左边比当前节点小，右边比当前节点小，或者反过来
- 如果只有两个值怎么办呢？我们需要为他先创建一个值放在左边，它和第一个值相同即可，这样就不会影响结果。
- 平坡是峰值：也就是说峰值是连续一样的值，此时只能记录一个峰值
AC代码
class Solution { public: int wiggleMaxLength(vector<int>& nums) { if(nums.size()<=1)return nums.size(); int curGap=0;//后一个节点和当前节点的差值 int preGap=0;//当前节点和前一个节点的差值 int result=1; for(int i=0;i<nums.size()-1;++i){ curGap = nums[i+1] - nums[i]; if((preGap>=0&&curGap<0)||(preGap<=0&&curGap>0)){//判断峰值的条件 result++; preGap = curGap;//只在波动的时候更新前一个差值 } } return result; } };
53. 最大子数组和
链接：53. 最大子数组和
解题思路
下面是四种实现方法，这次只讲贪心怎么实现
- 题目要求是最长子数组和，所以就要连续还要找最大的
- 我们可以这样，先用最小整数作为结果的初始值
- 然后，用另一个值count来加
- 如果比res大，就更新res
- 当这个值为负数时说明这个情况可以舍弃了，从+1的位置继续，同时更新count
AC代码
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; } //滑动窗口 // int maxSubArray(vector<int>& nums) { // int left = 0, right = 0; // int windowSum = 0, maxSum = INT_MIN; // while(right < nums.size()){ // // 扩大窗口并更新窗口内的元素和 // windowSum += nums[right]; // right++; // // 更新答案 // maxSum = windowSum > maxSum ? windowSum : maxSum; // // 判断窗口是否要收缩 // while(windowSum < 0) { // // 缩小窗口并更新窗口内的元素和 // windowSum -= nums[left]; // left++; // } // } // return maxSum; // } //动态规划 // int maxSubArray(vector<int>& nums) // { // int n=nums.size(); // if(n==0)return 0; // vector<int> dp(n); // dp[0]=nums[0]; // for(int i=1;i<n;++i) // { // dp[i]=max(nums[i],nums[i]+dp[i-1]); // } // int ret=INT_MIN; // for(int j=0;j<n;++j) // { // ret=max(ret,dp[j]); // } // return ret; // } // int maxSubArray(vector<int>& nums) // { // int n=nums.size(); // if(n==0)return 0; // int dp_0=nums[0]; // int dp_1=0,ret=dp_0; // for(int i=1;i<n;++i) // { // dp_1=max(nums[i],nums[i]+dp_0); // dp_0=dp_1; // ret=max(ret,dp_1); // } // return ret; // } //前缀和 // int maxSubArray(vector<int>& nums) // { // int n=nums.size(); // vector <int> presum(n+1); // presum[0]=0; // for(int i=1;i<=n;++i) // { // presum[i]=presum[i-1]+nums[i-1]; // } // int minval=INT_MAX; // int ret=INT_MIN; // for(int j=0;j<n;++j) // { // minval=min(minval,presum[j]); // ret=max(ret,presum[j+1]-minval); // } // return ret; // } };
55. 跳跃游戏
链接：55. 跳跃游戏
解题思路
- 题目的意思是 从当前位置能否到达最后一个位置 可以超过 但是不能小于
- 所以可以理解为是在一个位置上它的覆盖范围包含了最后一个位置就算是true
- 所以只要不断更新新位置范围 到最后找到是否大于最后一个位置的坐标即可
AC代码
class Solution { public: bool canJump(vector<int>& nums) { if(nums.size() == 1) return true; int cover = 0; for(int i = 0;i <= cover;++i){ cover = max(cover,i+nums[i]); if(cover >= nums.size()-1)return true; } return false; } };
45 跳跃游戏2
链接：45 跳跃游戏2
解题思路
- 和前面的"跳跃游戏"一样 它也要覆盖最后一个点 不同在于本题要求的是次数 也就是要第几次跳跃才能覆盖最后一个点
- 当移动下标移动到覆盖范围的最大值还没有覆盖到最后一个点 此时的jmp就要+1
- 值得注意的是题目说了 生成的测试用例可以到达 nums[n - 1] 就不用考虑其他情况了
AC代码
class Solution { public: int jump(vector<int>& nums) { if(nums.size()==1)return 0; int curmax=0,nextmax=0,jum=0;; for(int i=0;i<nums.size();++i){ nextmax = max(nextmax,nums[i]+i); if(i==curmax){ curmax = nextmax; jum++; if(curmax >= nums.size()-1)break; } } return jum; } };
134. 加油站
链接：134. 加油站
解题思路
参考代码随想录
我的感觉：
- 贪心的题目没有一种具体的模板，有的只是一种类似技巧性的思想，一般都不会这么想，可能是我写贪心写的太少了，”局部最优推出全局最优“这种思路还不够清晰，继续加油吧
AC代码
class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int curSum=0; int totalSum=0; int start=0; for(int i=0;i<gas.size();++i){ curSum += gas[i] - cost[i]; totalSum += gas[i] - cost[i]; if(curSum < 0){//当前累加rest[i]和curSum一旦小于0 start = i + 1; //起始位置更新为i+1 curSum = 0;//curSum从0开始 } } if(totalSum < 0)return -1;//说明怎么走都不可能跑一圈了 return start; } };
