最少侧跳次数

1824. 最少侧跳次数

给你一个长度为 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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minSideJumps(vector<int>& obstacles) { } };

golang 解法, 执行用时: 204 ms, 内存消耗: 23.9 MB, 提交时间: 2022-11-28 14:37:38

func min(lhs,rhs int)int{
    if lhs<rhs {
        return lhs
    }
    return rhs
}
func minSideJumps(obstacles []int) int {
    n := len(obstacles)
    MAX_V:=10000000
    cur:=[3]int{1,0,1}
    for i:=1;i<n;i++ {
        if obstacles[i]!=0 {
            cur[obstacles[i]-1]=MAX_V
        }
        switch obstacles[i-1] {
            case 1:
                cur[0]=min(cur[1],cur[2])+1
            case 2:
                cur[1]=min(cur[0],cur[2])+1
            case 3:
                cur[2]=min(cur[1],cur[0])+1
        }
    }
    return min(cur[0],min(cur[1],cur[2]))
}

python3 解法, 执行用时: 368 ms, 内存消耗: 28.9 MB, 提交时间: 2022-11-28 14:36:59

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        #跳跃次数
        l=0
        #位置列表更新使用
        loc=[1,2,3]
        #当前位置列表
        ru=[2]
        for i in range(1,len(obstacles)):
            if obstacles[i] in ru:
                if (len(ru)==1):
                    l+=1
                    ru.extend(loc)
                    ru.remove(obstacles[i])
                    ru.remove(obstacles[i])
                    if (obstacles[i-1]!=0):
                        ru.remove(obstacles[i-1])
                else:
                    ru.remove(obstacles[i])
        return l

java 解法, 执行用时: 30 ms, 内存消耗: 129 MB, 提交时间: 2022-11-28 14:35:53

// dp[j] 表示当前位置 j 表示停留在第 j 个道的最小次数。
class Solution {
  public int minSideJumps(int[] obstacles) {
    int n = obstacles.length;
    int[] dp = new int[3];
    dp[0] = dp[2] = 1;
    for (int i = 1; i < n; i++) {
      int obs = obstacles[i];
      //初始化dp，分两步
      int pre0 = dp[0];
      int pre1 = dp[1];
      int pre2 = dp[2];
      //1.最大值填充
      Arrays.fill(dp, (int)2e9);
      //2.实际障碍物情况：如果 j 位置无障碍物，先更新为刚刚保存的前一位置pre的次数
      if (obs != 1) dp[0] = pre0;
      if (obs != 2) dp[1] = pre1;
      if (obs != 3) dp[2] = pre2;
      //比较从非 j 的位置跳过来，是否次数更小
      if (obs != 1) dp[0] = Math.min(dp[0], Math.min(dp[1], dp[2]) + 1);
      if (obs != 2) dp[1] = Math.min(dp[1], Math.min(dp[0], dp[2]) + 1);
      if (obs != 3) dp[2] = Math.min(dp[2], Math.min(dp[0], dp[1]) + 1);
    }
    return Arrays.stream(dp).min().orElse(-1);
  }
}

上一题

下一题

详情