最少侧跳次数

难度: Medium

给你一个长度为 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 + 1
1 <= n <= 5 * 10⁵
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0

Submission

运行时间: 191 ms

内存: 37.2 MB

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        w = 2
        l = 0
        r = 1
        n = len(obstacles)
        ans = 0
        while l < n - 1:
            if obstacles[l + 1] == w:
                ans += 1
                r = l + 1
                if obstacles[l]:
                    w = 6 -(w + obstacles[l])
                else:
                    while r < n and (obstacles[r] == w or obstacles[r] == 0):
                        r += 1
                    if r != n:
                        w = 6 - (w + obstacles[r])
                    else:
                        break
            l += 1
        return ans

Explain

题解采用了贪心和模拟的策略。青蛙从第二条跑道开始，使用变量 w 来表示当前所在的跑道。变量 l 用来表示当前位置，而 r 代表可以前进到的最远位置。策略是在每一步尝试前进，当遇到障碍时进行侧跳。青蛙前进到下一个位置时，如果该位置有障碍，那么需要进行侧跳。侧跳的选择是基于当前跑道和障碍的位置，使用公式 '6 - (w + obstacles[l])' 来确定最优的跳跃目标跑道。在没有障碍的情况下，尽量在当前跑道上前进直到遇到障碍或到达终点。这个过程通过 while 循环进行模拟。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        w = 2  # 当前所在跑道，起始为第二条跑道
        l = 0  # 当前所在位置的索引
        r = 1  # 可以前进到的最远位置（初始值不重要，因为立即更新）
        n = len(obstacles)  # 道路的总长度
        ans = 0  # 侧跳的次数
        while l < n - 1:  # 直到达到最后一个位置前
            if obstacles[l + 1] == w:  # 如果下一个位置有障碍
                ans += 1  # 需要侧跳
                r = l + 1  # 更新可以前进到的位置
                if obstacles[l]:  # 当前位置有障碍
                    w = 6 - (w + obstacles[l])  # 计算新的跑道
                else:  # 当前位置没有障碍
                    while r < n and (obstacles[r] == w or obstacles[r] == 0):  # 寻找下一个有障碍的位置
                        r += 1
                    if r != n:  # 如果找到了障碍
                        w = 6 - (w + obstacles[r])  # 计算新的跑道
                    else:  # 如果没有找到障碍，即达到终点
                        break
            l += 1  # 前进到下一个位置
        return ans

Explore

题解中的公式 '6 - (w + obstacles[l])' 用于计算侧跳后的跑道，其设计基于跑道编号的特性（通常是1, 2, 3）。此公式在理论上并不总能确保侧跳到没有障碍的跑道，因为它没有检查侧跳目标跑道上是否存在障碍。它仅仅通过数学运算试图找到一个不同于当前跑道和当前位置障碍所在跑道的新跑道。在实际应用中，此公式需要结合对目标跑道障碍情况的检查，以确保侧跳的有效性。如果未进行这样的检查，可能会导致错误的跑道选择，从而需要额外的侧跳来纠正。

在题解中，当当前位置（l）有障碍时使用 '6 - (w + obstacles[l])' 来计算新跑道，似乎是一种简化处理，它假设必须立即离开当前跑道至一个安全的跑道。实际上，这种处理可能并不总是最优，因为它没有考虑l+1处的障碍情况。理论上，应该考虑从当前位置到下一个位置（l到l+1）的整体情况，选择一个既能避开当前位置也能避开下一个位置障碍的跑道。这样的处理更能符合实际情况，降低不必要的跳跃次数，提高算法的效率和正确性。

如果当前位置和下一个位置都有障碍，题解中的策略需要更加详细的处理。在实际应用中，应该评估所有可用的跑道，在当前位置和下一个位置的障碍情况下选择一个可行的跑道。这可能涉及到不只一次的侧跳，特别是当三个跑道中的两个都被障碍占据时。理想的处理方式是，通过检查所有跑道上接下来几个位置的障碍分布，选择一个最优的跑道，这样可以最小化总的侧跳次数，确保青蛙能够继续向前进。