Day 32 | 122.买卖股票的最佳时机 II、55.跳跃游戏、45.跳跃游戏 II

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

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

初始思路

只有一只股票，可以反复买卖，只要有利润可以赚我就进行买卖，至少2天为一个交易单位。

代码

var maxProfit = function (prices) {
    if (prices == null || prices.length <= 1) return 0
    // 贪心算法
    let result = 0
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            result += prices[i] - prices[i - 1]
        }
    }
    return result
};

感想

1. 假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。
   相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
   此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
2. 

Leetcode 55.跳跃游戏

题目：55.跳跃游戏

初始思路

不确定跳几步

代码

var canJump = function (nums) {
    if (nums.length === 1) return true
    let cover = 0
    for (let i = 0; i <= cover; i++){
        // 覆盖的最大范围
        cover = Math.max(cover, i + nums[i])
        // 如果可以覆盖到终点
        if (cover >= nums.length - 1) {
            return true
        }
    }
    return false
};

感想

1. 不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。
2. 如果终点在覆盖范围内，就一定能跳过来。

Leetcode 45.跳跃游戏 II

题目：45.跳跃游戏 II

初始思路

跟上一题相比，默认了可以跳到终点，但是要求跳的最少步数。
如果只是单纯的每次都跳最大步数的话，全局不一定最优。

代码

var jump = function (nums) {
    // 当前覆盖的范围
    let curDistance = 0
    // 下一步覆盖的范围
    let nextDistance = 0
    // 需要的步骤数
    let steps = 0
    for (let i = 0; i < nums.length - 1; i++) {
        // 在可覆盖的区域内更新最大的覆盖范围
        nextDistance = Math.max(nums[i] + i, nextDistance)
        // 遇到当前覆盖的最远距离下标，不得不往后走
        if (i === curDistance) {
            // 往后走一步扩大范围
            steps++
            // 更新当前覆盖的最远距离下标
            curDistance = nextDistance
        }
    }
    return steps
};

感想

1. 要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！
2. 这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。
3. 移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。想要达到这样的效果，只要让移动下标，最大只能移动到nums.length - 2的地方就可以了。