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

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

注意的地方

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

解题方法

通过分解每一天的利润,将正数的利润相加就是最大利润。假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
代码随想录算法训练营第二十六天 | leetcode:买卖股票的最佳时机II  ,跳跃游戏,跳跃游戏II

复杂度

时间复杂度

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。
代码随想录算法训练营第二十六天 | leetcode:买卖股票的最佳时机II  ,跳跃游戏,跳跃游戏II

复杂度

时间复杂度

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

解题方法

痛苦面具!!!!!!:weary::weary::weary::weary:
代码随想录算法训练营第二十六天 | 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;
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!