LeetCode 题解工作台
最少侧跳次数
给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。 给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （ 取值范围从 0 到 …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示青蛙到达第 个点，且处于第 条跑道（下标从 开始）的最小侧跳次数。 注意到青蛙起始位置处于第 条跑道（题目这里下标从 开始），因此 的值为 ，而 和 的值均为 。答案为 $min(f[n][0], f[n][1], f[n][2])$
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。
给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。
- 比方说，如果
obstacles[2] == 1，那么说明在点 2 处跑道 1 有障碍。
这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。
- 比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。
注意：点 0 处和点 n 处的任一跑道都不会有障碍。
示例 1：
输入：obstacles = [0,1,2,3,0] 输出：2 解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。 注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。
示例 2：
输入：obstacles = [0,1,1,3,3,0] 输出：0 解释：跑道 2 没有任何障碍，所以不需要任何侧跳。
示例 3：
输入：obstacles = [0,2,1,0,3,0] 输出：2 解释：最优方案如上图所示。总共有 2 次侧跳。
提示：
obstacles.length == n + 11 <= n <= 5 * 1050 <= obstacles[i] <= 3obstacles[0] == obstacles[n] == 0
解题思路
方法一：动态规划
我们定义 表示青蛙到达第 个点，且处于第 条跑道（下标从 开始）的最小侧跳次数。
注意到青蛙起始位置处于第 条跑道（题目这里下标从 开始），因此 的值为 ，而 和 的值均为 。答案为
对于 从 到 的每个位置，我们可以枚举青蛙当前所处的跑道 ，如果 ，说明第 条跑道上有障碍，此时 的值为正无穷；否则，青蛙可以选择不跳跃，此时 的值为 ，或者青蛙可以从其它跑道侧跳过来，此时 。
在代码实现上，我们可以将第一维空间优化掉，只用一个长度为 的数组 来维护。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def minSideJumps(self, obstacles: List[int]) -> int:
f = [1, 0, 1]
for v in obstacles[1:]:
for j in range(3):
if v == j + 1:
f[j] = inf
break
x = min(f) + 1
for j in range(3):
if v != j + 1:
f[j] = min(f[j], x)
return min(f)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assess whether the candidate can identify the state transition dynamic programming pattern for pathfinding problems.
- question_mark
Evaluate the candidate’s understanding of how greedy choices fit within dynamic programming for optimization.
- question_mark
Check if the candidate is comfortable dealing with arrays representing multiple possible states at each step.
常见陷阱
外企场景- error
Overcomplicating the problem by attempting unnecessary backtracking or multiple state recalculations.
- error
Forgetting to account for all three lanes and the possibility of switching between them at each point.
- error
Misunderstanding the role of side jumps and assuming that forward movement is always possible.
进阶变体
外企场景- arrow_right_alt
The problem can be extended to more than three lanes, increasing complexity.
- arrow_right_alt
Consider variations where side jumps are only allowed to adjacent lanes, limiting the flexibility of the solution.
- arrow_right_alt
Introduce time constraints or additional dynamic programming states based on different types of obstacles.