188. 买卖股票的最佳时机 IV

题目描述 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。 示例 2: 输入: [3,2,6,5,0,3], k = 2 输出: 7 解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润…

Read more

45. 跳跃游戏 II

题目描述 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。 https://leetcode-cn.com/problems/jump-game-ii/ 解法1 解法1是采用贪心解法,解法1很啰嗦,目的是尽可能让我们容易理解。策略是这样的,我们计算nums[i] + i,物理意义代表从当前出发能到达的最远位置。我们尽可能使下一跳落到较远的位置,这样才能使得跳到终点的步数最少。 我们以例子“[2,3,1,1,4]”为例,计算nums[i]+i -> nums[i],nums被更新为“[2,4,3,4,8]”,代表我站在第0个位置上,最远能跳到第2个位置上;站在第1个位置上,最远跳到第4个位置上(也就是终点),站在第2个位置上,最远能跳到第3个位置上……以此类推。那我们从0出发,最远能跳到第二个位置上,也就是说我们可以跳到第1个位置,也可以跳到第2个位置上。我们发现从第一个位置出发最远能到4,而从第2个位置出发最远能跳到3。我们刚刚说过,要保证下一跳落到较远到位置,所以我们选择从0跳到1,接着我们发现从1可以直接到终点,那么我们从1跳到4。 注意,不要落入一个误区:不是使本跳跳的尽可能远,而是从本跳出发,选择一个落脚点,从这个落脚点出发到达的尽可能远。以上面的为例,第一步我们从0跳到2虽然走的比0跳到1远,但是接下来从2出发最多只能到达3,而从1出发我们直接能到达终点。 根据上面的分析,我们能写出如下的代码,时间复杂度与空间复杂度均为O(n)。虽然这个代码包含双重循环,但是内层循环会改变外层循环的计数器,实际上只扫描了一次。 其实,上面的代码还可以继续优化,我们不需第一次扫描,将第一次扫描的逻辑合并到第二次扫描。 解法2 解法2很巧妙,但思想和解法1是差不多的。我们首先计算从当前位置i出发能到到达的最远距离,记为upperBound;我们还使用了另一个变量lastStepBound,记录从上一跳出发能到达的最远位置,最后我们使用res变量记录花费了几跳。我们接下来从i+1出发,继续更新upperBound,直到走到lastStepBound,然后我们更新lastStepBound = upperBound. 我们从i+1出发走到 lastStepBound,是为了寻找更远的下一跳。 我们以“[2,3,1,1,4]”为例,初始化lastStepBound = 0, upperBound = 0. 我们从i=0出发,更新upperBound = max(upperBound, i+nums[i]) = 2,然后我们更新lastStepBound = 2(第一跳起跳, res++),表示我们从0出发最远能到达2。接下来走到i=1更新upperBound = 4;走到i=2发现最远能到达3,则不更新upperBound。这时我们碰到了lastStepBound,得知我们下一跳最远能跳到4,另lastStepBound=upperBound(第一跳落地,第二跳起跳 res++)。当i=3时更新upperBound失败,此时i…

Read more

55. 跳跃游戏

题目描述 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。 https://leetcode-cn.com/problems/jump-game/ 解法1 解法1的方法是一种暴力搜索的方法,既然给出了每个位置能跳跃的最大距离,那我们就挨个尝试能落下的位置,然后以该位置为起点继续重复此过程看看能不能到达末尾。这是一种DFS方法,时间复杂度为O(n^2)。这种做法属于“人思考的少,机器思考的多”,另外代码量也很大,所以不推荐这种做法。 解法2 解法2采用贪心的做法,设置一个变量currMax,表示从当前位置之前的任意一点出发能走到的最远的位置。我们遍历每一个位置,判断i是否大于currMax。如果i>currMax,物理意义表示从i之前的任意位置出发,都到达不了i,则肯定到达不了i之后的任何位置,返回false即可。否则,我们更新currMax = max(currMax, i + nums[i])。 解法3 解法3采用回溯的方法,我们从终点向前回溯,看看终点之前有没有一个点i至少能够到达终点的,如果存在则回溯到点i;我们再看看i之前有没有一个点至少能够到达点i,如果存在我们继续回溯……直到看看能不能回溯到起点。如果能够回溯到起点,那我们从起点正向出发也一定能够到达终点;反之如果不能回溯到起点,那我们就没办法到达终点。

Read more