力扣热题之贪心算法
1.买卖股票
最终还是选择了贪心
class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size()==1) return 0;vector<int> gap;for(int i=1;i<prices.size();i++) gap.push_back(prices[i]-prices[i-1]);vector<int> dp(gap.size(),0);dp[0]=gap[0];for(int i=1;i<dp.size();i++)dp[i]=max(dp[i-1]+gap[i],gap[i]);return *max_element(dp.begin(),dp.end())>0?*max_element(dp.begin(),dp.end()):0;}
};2.跳跃游戏
也是比较简单，每一步都选跳的最远的，i+step[i]取最大，因为这样可选择的范围最大。
（1）稍等， 我发现deepseek给出的一个更简洁的贪心简直是神。。O(N)的算法，就是一遍过去，维护一个最远可达距离，你要是遍历索引的时候超过了，就说明不可达
class Solution {
public:bool canJump(vector<int>& nums) {int maxReach=0;for(int i=0;i<nums.size();i++){if(i>maxReach) return false;//指针根本不可能移动到这里来maxReach=max(maxReach,i+nums[i]);if(maxReach>=nums.size()-1) return true;}return true;}
};（2）还有神，逆序遍历。逆序遍历，只有在当前的数大于步数的时候才能实现跳跃，实现以后将步数重置
let step = 1for (let i = nums.length - 2; i >= 0; i--) {if (nums[i] < step) {step++} else {step = 1}
}return step === 13.跳跃游戏2
（1）动规
class Solution {
public:int jump(vector<int>& nums) {int n=nums.size();vector<int> dp(n,INT_MAX);dp[0]=0;for(int i=0;i<nums.size();i++){int x=nums[i];for(int j=0;j<=x;j++){if(i+j<n) dp[i+j]=min(dp[i+j],dp[i]+1);}}return dp[n-1];}
};（2）贪心
class Solution {
public:int jump(vector<int>& nums) {if(nums.size()==1) return 0;int count=0;int now=0;//右区间int next=0;//下一次可能到达的右区间for(int i=0;i<nums.size()-1;i++){next=max(next,i+nums[i]);if(i==now){count++;now=next;}if(now>=nums.size()-1) return count;}return count;}
};必须过拟合，才能应用到其他的
4.字母区间划分
跟上一题有相似的地方，也有不相似的地方，我觉得就是，end不是跳出来的，不用i+，或者说用滑动窗口更好理解
class Solution {
public:vector<int> partitionLabels(string s) {vector<int> lastOccur(26, -1);// 记录每个字符最后出现的位置for (int i = 0; i < s.size(); i++) {lastOccur[s[i] - 'a'] = i;}vector<int> result;int start = 0; // 当前分段的起始位置int end = 0; // 当前分段的最远结束位置for (int i = 0; i < s.size(); i++) {// 关键修正：这里应该是 lastOccur[s[i]-'a']，不是 i + lastOccur[...]end = max(end, lastOccur[s[i] - 'a']);// 如果到达当前分段的边界if (i == end) {result.push_back(end - start + 1); // 直接存储分段长度start = end + 1; // 更新下一个分段的起始位置}}return result;}
};好难。。。我不会贪心算法。。。