Medium

题目描述

有一条长度为 n 的三车道道路，由 n + 1 个点标记，从 0 到 n。一只青蛙从第 2 车道的点 0 开始，想要跳到点 n。但是，路上可能会有障碍物。

给你一个长度为 n + 1 的数组 obstacles，其中 obstacles[i]（取值范围从 0 到 3）表示在点 i 处位于车道 obstacles[i] 上的障碍物。如果 obstacles[i] == 0，则表示在点 i 处没有障碍物。每个点最多只有一个障碍物在 3 条车道中的一条上。

  • 例如，如果 obstacles[2] == 1，那么在点 2 处的车道 1 上有一个障碍物。

青蛙只能在同一车道上从点 i 移动到点 i + 1，前提是在点 i + 1 处的车道上没有障碍物。为了避开障碍物，青蛙也可以在同一点执行侧跳，跳到另一个车道（即使它们不相邻），前提是新车道上没有障碍物。

  • 例如，青蛙可以在点 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 + 1
  • 1 <= n <= 5 * 10^5
  • 0 <= obstacles[i] <= 3
  • obstacles[0] == obstacles[n] == 0

解题思路

这是一个典型的动态规划问题。我们需要追踪青蛙在每个位置的每个车道上所需的最少侧跳次数。

核心思路：

  1. 使用 dp[i][j] 表示青蛙到达位置 i 的车道 j 所需的最少侧跳次数
  2. 青蛙从位置 0 的车道 2 开始，初始化 dp[0][2] = 0，其他车道需要一次侧跳
  3. 对于每个位置 i，青蛙可以：
    • 从前一个位置的同一车道直接前进（如果当前车道没有障碍物）
    • 在当前位置侧跳到其他车道（如果目标车道没有障碍物）

状态转移：

  • 如果车道 j 在位置 i 没有障碍物：
    • dp[i][j] = dp[i-1][j]（从前一位置的同一车道直接前进）
    • dp[i][j] = min(dp[i][j], min(dp[i][other_lanes]) + 1)（从其他车道侧跳过来）

优化空间： 由于只需要前一个位置的状态，可以使用一维数组优化空间复杂度，每次处理当前位置时更新数组。

为了避免在同一轮更新中使用已更新的值，我们先计算能直接前进的情况，再计算侧跳的情况。

代码实现

class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
        vector<int> dp = {1, 0, 1}; // 车道1、2、3的最少侧跳次数
        
        for (int i = 1; i < obstacles.size(); i++) {
            int obstacle = obstacles[i];
            
            // 如果当前位置有障碍物，将对应车道设为无穷大
            if (obstacle != 0) {
                dp[obstacle - 1] = 1e6;
            }
            
            // 计算侧跳的情况
            for (int j = 0; j < 3; j++) {
                if (j + 1 != obstacle) {
                    // 从其他车道侧跳过来
                    for (int k = 0; k < 3; k++) {
                        if (k != j) {
                            dp[j] = min(dp[j], dp[k] + 1);
                        }
                    }
                }
            }
        }
        
        return min({dp[0], dp[1], dp[2]});
    }
};

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = [1, 0, 1]  # 车道1、2、3的最少侧跳次数
        
        for i in range(1, len(obstacles)):
            obstacle = obstacles[i]
            
            # 如果当前位置有障碍物，将对应车道设为无穷大
            if obstacle != 0:
                dp[obstacle - 1] = float('inf')
            
            # 计算侧跳的情况
            for j in range(3):
                if j + 1 != obstacle:
                    # 从其他车道侧跳过来
                    for k in range(3):
                        if k != j:
                            dp[j] = min(dp[j], dp[k] + 1)
        
        return min(dp)

public class Solution {
    public int MinSideJumps(int[] obstacles) {
        int[] dp = {1, 0, 1}; // 车道1、2、3的最少侧跳次数
        
        for (int i = 1; i < obstacles.Length; i++) {
            int obstacle = obstacles[i];
            
            // 如果当前位置有障碍物，将对应车道设为无穷大
            if (obstacle != 0) {
                dp[obstacle - 1] = int.MaxValue;
            }
            
            // 计算侧跳的情况
            for (int j = 0; j < 3; j++) {
                if (j + 1 != obstacle) {
                    // 从其他车道侧跳过来
                    for (int k = 0; k < 3; k++) {
                        if (k != j) {
                            dp[j] = Math.Min(dp[j], dp[k] + 1);
                        }
                    }
                }
            }
        }
        
        return Math.Min(Math.Min(dp[0], dp[1]), dp[2]);
    }
}

var minSideJumps = function(obstacles) {
    let dp = [1, 0, 1]; // 车道1、2、3的最少侧跳次数
    
    for (let i = 1; i < obstacles.length; i++) {
        const obstacle = obstacles[i];
        
        // 如果当前位置有障碍物，将对应车道设为无穷大
        if (obstacle !== 0) {
            dp[obstacle - 1] = Infinity;
        }
        
        // 计算侧跳的情况
        for (let j = 0; j < 3; j++) {
            if (j + 1 !== obstacle) {
                // 从其他车道侧跳过来
                for (let k = 0; k < 3; k++) {
                    if (k !== j) {
                        dp[j] = Math.min(dp[j], dp[k] + 1);
                    }
                }
            }
        }
    }
    
    return Math.min(...dp);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要遍历所有位置，每个位置的状态转移是常数时间
空间复杂度O(1) - 只使用了固定大小的数组存储3个车道的状态

相关题目