LeetCode | C++ 贪心算法——122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II

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

局部最优：收集每天的正利润，全局最优：求得最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for (int i = 1; i < prices.size(); i++) {
            int delta = prices[i] - prices[i - 1]; 
            if (delta > 0) {
                sum += delta;
            }
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

55. 跳跃游戏

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true;
        for (int i = 0; i <= cover; i++) {
            if ((nums[i] + i) > cover) {
                cover = nums[i] + i;
            }
            if (cover >= nums.size() - 1) {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

45.跳跃游戏II

在每一步可以达到的范围内寻找下一步可达到的最大覆盖范围，以此求得最小步数，一旦覆盖范围覆盖到终点，即输出步数

class Solution {
public:
    int jump(vector<int>& nums) {
        int step = 0;
        int cover = 0, next = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            next = max(next, nums[i] + i);
            if (i == cover && cover != nums.size() - 1) {
                cover = next;
                step++;
                if (cover >= nums.size() - 1) break;
            }   
        }
        return step;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16