Skip to content

Latest commit

 

History

History
206 lines (162 loc) · 6.83 KB

README.md

File metadata and controls

206 lines (162 loc) · 6.83 KB

1824. 最少侧跳次数

English Version

题目描述

给你一个长度为 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 * 105
  • 0 <= obstacles[i] <= 3
  • obstacles[0] == obstacles[n] == 0

解法

方法一：动态规划

我们用 $f[i][j]$ 表示从起点跳到第 $i$ 个点，且当前在第 $j$ 条跑道的最少侧跳次数。注意到每个位置 $i$ 只依赖于 $i - 1$ 位置，因此我们可以使用滚动数组优化空间复杂度。

定义 $f[j]$ 表示从起点跳到第 $i$ 个点，且当前在第 $j$ 条跑道的最少侧跳次数。答案即为 $min(f[0], f[1], f[2])$。

我们可以枚举当前点的三条跑道，如果当前跑道没有障碍，那么 $f[j]$ 不变，否则 $f[j]$ 为其它两条跑道中的最小值加 $1$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 obstacles 的长度。

相似题目：

Python3

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        f = [1, 0, 1]
        for v in obstacles[1:]:
            g = [inf] * 3
            for j in range(3):
                if v != j + 1:
                    g[j] = f[j]
            if v != 1:
                g[0] = min(g[0], min(g[1], g[2]) + 1)
            if v != 2:
                g[1] = min(g[1], min(g[0], g[2]) + 1)
            if v != 3:
                g[2] = min(g[2], min(g[0], g[1]) + 1)
            f = g
        return min(f)

Java

class Solution {
    private int inf = 0x3f3f3f3f;

    public int minSideJumps(int[] obstacles) {
        int[] f = new int[] {1, 0, 1};
        for (int i = 1; i < obstacles.length; ++i) {
            int v = obstacles[i];
            int[] g = new int[] {inf, inf, inf};
            for (int j = 0; j < 3; ++j) {
                if (v != j + 1) {
                    g[j] = f[j];
                }
            }
            if (v != 1) {
                g[0] = Math.min(g[0], Math.min(g[1], g[2]) + 1);
            }
            if (v != 2) {
                g[1] = Math.min(g[1], Math.min(g[0], g[2]) + 1);
            }
            if (v != 3) {
                g[2] = Math.min(g[2], Math.min(g[0], g[1]) + 1);
            }
            f = g;
        }
        return Math.min(f[0], Math.min(f[1], f[2]));
    }
}

C++

class Solution {
public:
    const int inf = 0x3f3f3f3f;

    int minSideJumps(vector<int>& obstacles) {
        vector<int> f = {1, 0, 1};
        for (int i = 1; i < obstacles.size(); ++i) {
            int v = obstacles[i];
            vector<int> g(3, inf);
            for (int j = 0; j < 3; ++j) if (v != j + 1) g[j] = f[j];
            if (v != 1) g[0] = min(g[0], min(g[1], g[2]) + 1);
            if (v != 2) g[1] = min(g[1], min(g[0], g[2]) + 1);
            if (v != 3) g[2] = min(g[2], min(g[0], g[1]) + 1);
            f = move(g);
        }
        return *min_element(f.begin(), f.end());
    }
};

Go

func minSideJumps(obstacles []int) int {
	inf := 0x3f3f3f3f
	f := [3]int{1, 0, 1}
	for _, v := range obstacles[1:] {
		g := [3]int{inf, inf, inf}
		for j := 0; j < 3; j++ {
			if v != j+1 {
				g[j] = f[j]
			}
		}
		if v != 1 {
			g[0] = min(g[0], min(g[1], g[2])+1)
		}
		if v != 2 {
			g[1] = min(g[1], min(g[0], g[2])+1)
		}
		if v != 3 {
			g[2] = min(g[2], min(g[0], g[1])+1)
		}
		f = g
	}
	return min(f[0], min(f[1], f[2]))
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

...