代码随想录训练营二刷第三十二天 | 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

代码随想录训练营二刷第三十二天 | 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
思路：可以当天买当天卖，只要nums[i]-nums[i-1]>0就可以进行买卖，这样只要收益大于0我就交易局部最优全局最优。

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

二、 55. 跳跃游戏

题目链接：https://leetcode.cn/problems/jump-game/
思路：nums数组每走一步就更新能抵达最远的距离，只要当前距离i大于能抵达的最远距离即无法到达。

public boolean canJump(int[] nums) {
        if (nums.length == 1) return true;
        int far = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i > far) return false;
            far = Math.max(i+nums[i], far);
        }
        return true;
    }
1
2
3
4
5
6
7
8
9

三、45.跳跃游戏II

题目链接：https://leetcode.cn/problems/jump-game-ii/
思路：记录下当前能抵达的范围和在当前范围内下一条最远能抵达的距离，当抵达当前范围的终点之后，就算走了一步，更新当前范围，当下一跳可以抵达终点时直接返回无效再跳。

class Solution {
     public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int cur = 0, pre = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            pre = Math.max(pre, i + nums[i]);
            if (i == cur) {
                cur = pre;
                count++;
                if (pre >= nums.length - 1) return count;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15