LeetCode刷题笔记【24】：贪心算法专题-2（买卖股票的最佳时机II、跳跃游戏、跳跃游戏II）

前置知识

参考前文

参考文章：
LeetCode刷题笔记【23】：贪心算法专题-1（分发饼干、摆动序列、最大子序和）

122.买卖股票的最佳时机II

题目描述

LeetCode链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

贪心-直观写法

思路: 贪心算法
假设这个股票交易员有预知明天股票价格的能力;
当明天的价格大于今天的时候, 就买入/持有;
当明天价格下跌时, 就在今天抛售/不购买;
最后一天的时候如果手里还有, 就售出;

class Solution {
public:int maxProfit(vector<int>& prices) {int ans=0;if(prices.size()<=1)return ans;bool holding=false;for(int i=0; i<prices.size(); ++i){if(i==prices.size()-1){//最后一天, 手里还有股票if(holding)ans += prices.back();//卖出break;//不管咋样都要break了}if(prices[i+1] > prices[i] && !holding){//明天升值, 并且手里没有股票ans -= prices[i];//买入holding = true;}else if(prices[i+1] <= prices[i] && holding){//明天贬值, 并且手里有股票ans += prices[i];//卖出holding = false;}}return ans;}
};

贪心-优化代码更简洁

以上过程可以抽象为以下操作:
遍历整个prices序列, 只记录其中升序的部分的差值

class Solution {
public:int maxProfit(vector<int>& prices) {int ans=0;for(int i=0; i<prices.size()-1; ++i){ans += max(0, prices[i+1]-prices[i]);}return ans;}
};

55. 跳跃游戏

题目描述

LeetCode链接：https://leetcode.cn/problems/jump-game/description/

贪心-借助ability数组

创建并维护一个vector<bool> ability数组
从头开始遍历nums, 最开始ability[0]=true
然后如果ability[i]==true, 那么将ability[i]~ability[i+nums[i]]都为true
过程中发现某个ability[i]==false, 那么就为false

class Solution {
public:bool canJump(vector<int>& nums) {vector<bool> ability(nums.size(), false);ability[0] = true;for(int i=0; i<nums.size(); ++i){if(ability[i]){for(int j=i+1; j<=i+nums[i]; ++j){if(j>=nums.size())return true;;ability[j] = true;}}else{return false;}}return true;}
};

贪心-只用int far记录最远距离

用不到一个数组, 用一个far表示最远能到达的点就可以了

class Solution {
public:bool canJump(vector<int>& nums) {int far=0;for(int i=0; i<nums.size(); ++i){if(far >= nums.size()-1)return true;if(far>=i){far = max(far, i+nums[i]);}else{return false;}}return true;}
};

核心思想是: 不要纠结这次跳几步, 而是关注最远能跳到哪里

45.跳跃游戏II

题目描述

LeetCode链接：https://leetcode.cn/problems/jump-game-ii/description/

回溯算法

思路: 回溯算法
每一层的回溯过程就是在遍历自己从这一步跳出去, 可以跳的距离的所有可能性
终止条件是index>nums.size()-1, 或者nums[index]==0

class Solution {
private:int ans = INT_MAX;int cur = 0;void backtrack(vector<int>& nums, int index){if(index>=nums.size()-1){ans = min(ans, cur);return;}if(nums[index]==0)return;for(int i=nums[index]; i>0; --i){cur++;backtrack(nums, index+i);cur--;}return;}
public:int jump(vector<int>& nums) {backtrack(nums, 0);return ans;}
};

贪心算法

回溯法肯定是可以解决问题的, 但是奈何回溯的本质是遍历, 时间复杂度过高, 超出时间限制
所以老老实实用贪心吧:
和<55. 跳跃游戏>的核心思路是一样的, 都是尽量往远了跳, 但是这个又不能乱跳, 因为涉及到要不要ans++的问题

所以贪心的思路是: 先看一下这一步能跳多远, 如果可以满足要求, 就结束, 如果不能, 那么就再跳一步
具体的实现是: 用nextDistence记录在当前范围内, 再跳一步可以达到的最远结果;
当遍历达到了curDistence处时, 如果还没有到最后一位, 那么就转nextDistence

class Solution {
public:int jump(vector<int>& nums) {int ans = 0;if(nums.size()<=1)return ans;int nextDistence=0, curDistence=0;for(int i=0; i<nums.size(); ++i){nextDistence = max(nextDistence, i+nums[i]);if(i==curDistence){ans++;curDistence = nextDistence;if(nextDistence>=nums.size()-1)break;}}return ans;}
};

总结

贪心算法大概率就是没法把握, 甚至看起来是"千题千解", 尽量熟悉吧只能说, 如果之后遇到类似的题目了, 可以想起来最好.
实在不行的话或许只能用回溯和动态规划尝试了.

刚才的第二题, 说到不要纠结这次跳几步, 而是关注最远能跳到哪里, 或许也是某种人生哲学呢哈哈哈.
本质上我们或多或少的都在用贪心算法规划自己的人生.
(用贪心还算好了, 至少是当下和未来一部分时间内的最优, 还有不知道多少人是在后视镜开车呢)

本文参考：
买卖股票的最佳时机II
跳跃游戏
跳跃游戏II