力扣面试经典150 —— 6-10题

• 力扣面试经典150题
• 在 VScode 中安装 LeetCode 插件即可使用 VScode 刷题，安装 Debug LeetCode 插件可以免费 debug
• 本文使用 python 语言解题，文中 “数组” 通常指 python 列表；文中 “指针” 通常指 python 列表索引

6. [中等] 轮转数组

• 题目链接
• 标签：数组、数学、双指针
  

6.1 解法1：使用额外的数组

• 借助一个额外数据将各个元素放到新位置。注意到从整体上看，输出数组可以看作是在 k % len(nums) 位置截断然后重新组合，可以用 python 的列表操作简单地如下实现

  class Solution:def rotate(self, nums: List[int], k: int) -> None:k = k % len(nums)res = nums[-k:] + nums[:-k]nums[:] = res
  

  这其实等价于用两个指针分别遍历截断的两部分，并将元素依次复制到辅助数组
• 时间复杂度 $O(n)$，空间复杂度 $O(n)$

6.2 解法2：数组翻转

• 和方法一一样，注意到输出数组可以看作是在 k % len(nums) 位置截断然后重新组合，这可以通过三次列表翻转实现，示意如下

  nums = "----->-->"; k =3
  result = "-->----->";reverse "----->-->" we can get "<--<-----"
  reverse "<--" we can get "--><-----"
  reverse "<-----" we can get "-->----->"
  

  下面给出代码，使用双指针进行翻转操作

  class Solution:def rotate(self, nums: List[int], k: int) -> None:def _reverse(start, end):while start < end:t = nums[start]nums[start] = nums[end]nums[end] = tstart += 1end -= 1k = k % len(nums)_reverse(0, len(nums)-1)_reverse(0, k-1)_reverse(k, len(nums)-1)
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

7. [简单] 买卖股票的最佳时机

• 题目链接
• 标签：数组、动态规划
  

7.1 解法1：暴力法

• 直接遍历所有可能的买卖组合情况，但这种方法会超时

  def maxProfit(self, prices: List[int]) -> int:# 暴力法：超时profit = -float('inf')for i in range(len(prices)-1):buy = prices[i]for j in range(i+1, len(prices)):sell = prices[j]if sell > buy and sell - buy > profit:profit = sell - buyprofit = 0 if profit < 0 else profitreturn profit
  

• 时间复杂度 $O(n^2)$，空间复杂度 $O(1)$

7.2 解法2：贪心

• 只遍历一遍，在每个时刻贪心地计算可能的最大利润。为此，需要动态地更新截止目前为止的最低买入价

  class Solution:def maxProfit(self, prices: List[int]) -> int:# 贪心：动态维护历史最低价，进而利用它计算理论最大收益min_price = float('inf')max_profit = -float('inf')for p in prices:# 动态维护历史最低价if p < min_price:min_price = p# 基于历史最低价得到在当前时刻卖出的理论最大收益profit = p - min_priceif profit > max_profit:max_profit = profitmax_profit = 0 if max_profit < 0 else max_profitreturn max_profit
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

8. [中等] 买卖股票的最佳时机II

• 题目链接
• 标签：贪心、数组、动态规划
  

8.1 解法1：贪心

• 基于贪心的思想，实现最大利润意味着每一次可能的盈利都被把握。我们变量把股价曲线折线图，在每一个时刻执行收益最大化操作，即把每一个上升段都加入总收益中，水平或下降段则跳过

  class Solution:def maxProfit(self, prices: List[int]) -> int:max_profit = 0for i in range(len(prices)-1):profit = prices[i+1] - prices[i]if profit > 0:max_profit += profitreturn max_profit
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

8.2 解法2：动态规划

• 题目设置满足动态规划的三要素
  1. 无后效性：当前和未来的交易操作不会影响过去交易操作的收益
  2. 最优子结构：在整个交易过程中实现最大收益，意味着交易过程中的任意一个时间段的收益都是最优的。问题最优解的结构包含其子问题的最优解
  3. 重叠子问题：当我们递归地自顶向下分解时，即把 “最大化前n天收益” 不断地递归分解为 “最大化前n-1天收益，同时最大化第n-1天收益” 时，出现了要在递归过程中重复求解的重叠子问题（比如 “最大化前1天收益”），这提示我们使用递推式自底向上的构造解（动态规划的自底向上形式），或使用带备忘录的递归法（动态规划的自顶向下形式）
• 我们使用自底向上的动态规划形式，这时需要构造递推公式（动态规划中称 “状态转移方程”）。定义状态 dp[i][0] 和 dp[i][1] 分别表示第 $i$ 天交易完后手里没有和持有股票的最大利润。
  1. 对于 dp[i][0] 来说，第 $i$ 天交易完后手里没有股票，意味着要么前一天就没有，要么今天卖了，递推式为
     d p [ i ] [ 0 ] = max ⁡ { d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + p r i c e s [ i ] } dp[i][0]=\max\{dp[i−1][0],dp[i−1][1]+prices[i]\} dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]}
  2. 对于 dp[i][1] 来说，第 $i$ 天交易完后手里有股票，意味着要么前一天有，要么今天刚买，递推式为
     d p [ i ] [ 1 ] = max ⁡ { d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] } dp[i][1]=\max\{dp[i−1][1],dp[i−1][0]−prices[i]\} dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}
  3. 根据问题定义，第0天交易时有
     $$dp[0][0]=0,dp[0][1]=-prices[0]$$
  4. 由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，最后返回 $dp[n-1][0]$ 即可
• 注意到以上状态转移方程1、2中，dp[i] 仅与 dp[i-1] 有关，而与更早的状态都无关，因此不必存储这些无关的状态，只需要将 dp[i−1][0] 和 dp[i−1][1] 存放在两个变量中，通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量，以便于第 $i+1$ 天的状态转移计算即可

  class Solution:def maxProfit(self, prices: List[int]) -> int:dp0 = 0             # 今日交易完后手里没有股票的最大利润dp1 = -prices[0]    # 今日交易完后手里有一支股票的最大利润for i in range(1, len(prices)):dp0_ = max(dp0, dp1 + prices[i])dp1_ = max(dp1, dp0 - prices[i])dp0, dp1 = dp0_, dp1_            return dp0
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

9. [中等] 跳跃游戏

• 题目链接
• 标签：贪心、数组、动态规划
  

9.1 解法1：贪心模拟

• 直接模拟整个转移过程，每次都贪心地跳到能去向的最远处，直到达到终点或无法前进

  class Solution:def canJump(self, nums: List[int]) -> bool:cur_pos = next_pos = 0max_range = nums[cur_pos]   # 当前可达的最大索引位置while True:# 若从当前位置可以直接到目标，退出if max_range >= len(nums) - 1:return True# 考察从当前位置可达的每个新位置可覆盖的最大范围, 贪心地选择可达范围最大处作为转移到的索引位置 next_posfor steps in range(1, nums[cur_pos] + 1):next_range = cur_pos + steps + nums[cur_pos + steps]if next_range > max_range:next_pos = cur_pos + stepsmax_range = next_range# 如果当前位置已经是最佳的，且已知当前 max_range 无法到达目标，退出if next_pos == cur_pos:return False# 去向新索引位置cur_pos = next_pos
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

9.2 解法2：贪心

• 对于每一个可达位置 $x$，它使得 $x+1,x+2,\cdots ,x+\text{nums}[x]$ 这些连续的位置都可以到达。利用贪心的思想，我们遍历数组，并在每一步维护当前可达的最大状态，如果发现最后的位置可达则返回 true，反之若遍历结束后最后位置仍不可达则返回 false

  class Solution:def canJump(self, nums: List[int]) -> bool:max_range = 0for i, step in enumerate(nums):if i <= max_range:if i + step > max_range:max_range = i + stepif max_range >= len(nums) - 1:return Truereturn False
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$

10. [中等] 跳跃游戏II

• 题目链接
• 标签：贪心、数组、动态规划
  

10.1 解法1：贪心模拟

• 和 9.1 完全一直，直接模拟整个转移过程，每次都贪心地跳到能去向的最远处，直到达到终点或无法前进。模拟的同时记录总跳跃次数并返回

  class Solution:def jump(self, nums: List[int]) -> int:# 特殊情况直接退出if len(nums) == 1:return 0cur_pos = next_pos = step_cnt = 0max_range = nums[cur_pos]while True:# 若从当前位置可以直接到目标，退出if max_range >= len(nums) - 1:return step_cnt + 1# 考察每一个新位置可以覆盖的最大范围，next_pos 设置为范围最大新索引位置for steps in range(1, nums[cur_pos] + 1):next_range = cur_pos + steps + nums[cur_pos + steps]if next_range > max_range:next_pos = cur_pos + stepsmax_range = next_range# 去向新索引位置cur_pos = next_posstep_cnt += 1
  

• 时间复杂度 $O(n)$，空间复杂度 $O(1)$