算法训练Day32|● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

1class Solution {
2    public int maxProfit(int[] prices) {
3        int res = 0;
4        for (int i = 1; i < prices.length; i++) {
5            res += Math.max(prices[i] - prices[i - 1], 0);
6        }
7        return res;
8    }
9}

 1// 顺序遍历
 2class Solution {
 3    public boolean canJump(int[] nums) {
 4        if (nums.length == 1) {
 5            return true;
 6        }
 7        int cover = 0;
 8        for (int i = 0; i <= cover; i++) {
 9            cover = Math.max(i + nums[i], cover);
10            if (cover >= nums.length - 1) {
11                return true;
12            }
13        }
14        return false;
15    }
16}
17
18// 逆序遍历：看懂了顺序遍历，逆序似乎更好理解
19class Solution {
20    public boolean canJump(int[] nums) {
21        int lastPos = nums.length - 1;
22        for (int i = nums.length - 2; i >= 0; i--) {
23            if (i + nums[i] >= lastPos) {
24                lastPos = i;
25            }
26        }
27        return lastPos == 0;
28    }
29}

 1class Solution {
 2    public int jump(int[] nums) {
 3        if (nums.length == 1) {
 4            return 0;
 5        }
 6        // 计数器
 7        int count = 0;
 8        // 当前索引下的最大覆盖范围
 9        int curDistance = 0;
10        // 该覆盖范围下的覆盖范围
11        int maxDistance = 0;
12
13        for (int i = 0; i < nums.length; i++) {
14            maxDistance = Math.max(maxDistance, i + nums[i]);
15
16            if (maxDistance >= nums.length - 1) {
17                count++;
18                break;
19            } else if (i == curDistance) {
20                curDistance = maxDistance;
21                count++;
22            }
23        }
24        return count;
25    }
26}