力扣面试经典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
  1
  2
  3
  4
  5

  这其实等价于用两个指针分别遍历截断的两部分，并将元素依次复制到辅助数组
• 时间复杂度 $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 "-->----->"
  1
  2
  3
  4
  5
  6

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

  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] = t
                  start += 1
                  end -= 1
  
          k = k % len(nums)
          _reverse(0, len(nums)-1)
          _reverse(0, k-1)
          _reverse(k, len(nums)-1)
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

• 时间复杂度 $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 - buy
          profit = 0 if profit < 0 else profit
          return profit
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

• 时间复杂度 $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_price
              if profit > max_profit:
                  max_profit = profit
  
          max_profit = 0 if max_profit < 0 else max_profit
          return max_profit
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

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

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

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

8.1 解法1：贪心

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

  class Solution:
      def maxProfit(self, prices: List[int]) -> int:
          max_profit = 0
          for i in range(len(prices)-1):
              profit = prices[i+1] - prices[i]
              if profit > 0:
                  max_profit += profit
          return max_profit
  1
  2
  3
  4
  5
  6
  7
  8

• 时间复杂度 $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
  1
  2
  3
  4
  5
  6
  7
  8
  9

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

9. [中等] 跳跃游戏

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

9.1 解法1：贪心模拟

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

  class Solution:
      def canJump(self, nums: List[int]) -> bool:
          cur_pos = next_pos = 0
          max_range = nums[cur_pos]   # 当前可达的最大索引位置
          while True:
              # 若从当前位置可以直接到目标，退出
              if max_range >= len(nums) - 1:
                  return True
  
              # 考察从当前位置可达的每个新位置可覆盖的最大范围, 贪心地选择可达范围最大处作为转移到的索引位置 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 + steps
                      max_range = next_range
              
              # 如果当前位置已经是最佳的，且已知当前 max_range 无法到达目标，退出
              if next_pos == cur_pos:
                  return False
  
              # 去向新索引位置
              cur_pos = next_pos
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22

• 时间复杂度 $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 = 0
          for i, step in enumerate(nums):
              if i <= max_range:
                  if i + step > max_range:
                      max_range = i + step
                  if max_range >= len(nums) - 1:
                      return True
          return False
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 时间复杂度 $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 0
  
          cur_pos = next_pos = step_cnt = 0
          max_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 + steps
                      max_range = next_range
  
              # 去向新索引位置
              cur_pos = next_pos
              step_cnt += 1
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23

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