代码随想录算法训练营第二十六天 | leetcode：买卖股票的最佳时机II ,跳跃游戏,跳跃游戏II

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

注意的地方

任何时候最多只能持有一只股票。
求能获得的最大利润，而不用记录买卖时间点。

解题方法

通过分解每一天的利润，将正数的利润相加就是最大利润。假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

复杂度

时间复杂度

O(n)

空间复杂度

O(1)

code

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $count = 0;
        for($i = 1; $i < count($prices); $i++){
            $diff = $prices[$i] - $prices[$i-1];
            if($diff > 0){
                $count += $diff;
            }
        }
        return $count;
    }
}

55. 跳跃游戏

解题方法

因为题目要求最终只需要关注能否到达终点，所以不用关系具体每次该跳几步，该调到哪。可以抽象为每一步的覆盖范围，在当前覆盖范围，每移动一步如果下一步的覆盖范围大于当前的覆盖范围就更新覆盖范围，直到覆盖范围大于等于count()-1。

复杂度

时间复杂度

O(n)

空间复杂度

O(1)

code

class Solution {

    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function canJump($nums) {
        //只有一个元素不用跳也到了。
        if(count($nums) == 1) return true;
        $cover = 0;
        //循环是在当前覆盖范围
        for($i = 0; $i <= $cover; $i++){
            //计算覆盖范围
            $lenth = $nums[$i] + $i;
            //更新更大的覆盖范围
            if($lenth > $cover) $cover = $lenth;
            //覆盖范围大于等于数组长度
            if($cover >= count($nums) - 1) return true;
        }
        return false;
    }
}

45. 跳跃游戏 II

解题方法

痛苦面具!!!!!!
代码随想录算法训练营第二十六天 | leetcode：买卖股票的最佳时机II ,跳跃游戏,跳跃游戏II

这题不怎么懂，死磕了两天实在写不出，只好先放弃了。解题传送门：跳跃游戏II

复杂度

时间复杂度

O(n)

空间复杂度

O(1)

code

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function jump($nums) {
        if (count($nums) == 1) return 0;
        $curDistance = 0;    // 当前覆盖最远距离下标
        $ans = 0;            // 记录走的最大步数
        $nextDistance = 0;   // 下一步覆盖最远距离下标
        for ($i = 0; $i < count($nums); $i++) {
            $nextDistance = max($nums[$i] + $i, $nextDistance);  // 更新下一步覆盖最远距离下标
            if ($i == $curDistance) {                         // 遇到当前覆盖最远距离下标
                $ans++;                                  // 需要走下一步
                $curDistance = $nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）
                if ($nextDistance >= count($nums) - 1) break;  // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
            }
        }
        return $ans;
    }
}