- 力扣面试经典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) O(n)，空间复杂度 O ( n ) 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] = t start += 1 end -= 1 k = k % len(nums) _reverse(0, len(nums)-1) _reverse(0, k-1) _reverse(k, len(nums)-1) - 时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) 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 - 时间复杂度 O ( n 2 ) O(n^2) O(n2)，空间复杂度 O ( 1 ) O(1) 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 - 时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) 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 - 时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)
8.2 解法2：动态规划
- 题目设置满足动态规划的三要素
- 无后效性：当前和未来的交易操作不会影响过去交易操作的收益
- 最优子结构：在整个交易过程中实现最大收益，意味着交易过程中的任意一个时间段的收益都是最优的。问题最优解的结构包含其子问题的最优解
- 重叠子问题：当我们递归地自顶向下分解时，即把 “最大化前n天收益” 不断地递归分解为 “最大化前n-1天收益，同时最大化第n-1天收益” 时，出现了要在递归过程中重复求解的重叠子问题（比如 “最大化前1天收益”），这提示我们使用递推式自底向上的构造解（动态规划的自底向上形式），或使用带备忘录的递归法（动态规划的自顶向下形式）
- 我们使用自底向上的动态规划形式，这时需要构造递推公式（动态规划中称 “状态转移方程”）。定义状态
dp[i][0]和dp[i][1]分别表示第 i i i 天交易完后手里没有和持有股票的最大利润。- 对于
dp[i][0]来说，第 i i 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]} - 对于
dp[i][1]来说，第 i i 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]} - 根据问题定义，第0天交易时有
d p [ 0 ] [ 0 ] = 0 , d p [ 0 ] [ 1 ] = − p r i c e s [ 0 ] dp[0][0]=0,\quad dp[0][1]=−prices[0] dp[0][0]=0,dp[0][1]=−prices[0] - 由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，最后返回 d p [ n − 1 ] [ 0 ] dp[n−1][0] 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 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(n) O(n)，空间复杂度 O ( 1 ) O(1) 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 - 时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)
9.2 解法2：贪心
- 对于每一个可达位置 x x x，它使得 x + 1 , x + 2 , ⋯ , x + nums [ x ] x+1,x+2,⋯ ,x+\text{nums}[x] x+1,x+2,⋯ ,x+nums[x] 这些连续的位置都可以到达。利用贪心的思想，我们遍历数组，并在每一步维护当前可达的最大状态，如果发现最后的位置可达则返回
true，反之若遍历结束后最后位置仍不可达则返回falseclass 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 - 时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) 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 - 时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)