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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

贪心-优化代码更简洁

以上过程可以抽象为以下操作:
遍历整个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;
    }
};
1
2
3
4
5
6
7
8
9
10

55. 跳跃游戏

题目描述

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

贪心-借助ability数组

创建并维护一个vector 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

贪心-只用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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

贪心算法

回溯法肯定是可以解决问题的, 但是奈何回溯的本质是遍历, 时间复杂度过高, 超出时间限制
所以老老实实用贪心吧:
和<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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

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

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

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