最少侧跳次数
难度:
标签:
题目描述
给你一个长度为 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
代码结果
运行时间: 191 ms, 内存: 37.2 MB
/*
* 思路：
* 1. 初始化一个dp数组表示到达每个点每条跑道的最少侧跳次数。
* 2. 使用Java Stream API简化代码。
* 3. 遍历每个点，根据障碍物更新当前点的dp值。
* 4. 使用Stream API检查并更新可能的侧跳。
* 5. 最后，返回到达终点的三个跑道中最小的侧跳次数。
*/
import java.util.stream.IntStream;
public int minSideJumps(int[] obstacles) {
int n = obstacles.length - 1;
int[] dp = new int[]{1, 0, 1}; // 初始侧跳次数
for (int i = 1; i <= n; i++) {
int[] newDp = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
IntStream.range(0, 3).forEach(j -> {
if (obstacles[i] != j + 1) {
newDp[j] = dp[j]; // 直接跳到下一个点
}
});
IntStream.range(0, 3).forEach(j -> {
if (obstacles[i] != j + 1) {
IntStream.range(0, 3).forEach(k -> {
if (j != k && obstacles[i] != k + 1) {
newDp[j] = Math.min(newDp[j], dp[k] + 1); // 在当前点侧跳
}
});
}
});
dp = newDp;
}
return IntStream.of(dp).min().getAsInt();
}解释
方法:
题解采用了贪心和模拟的策略。青蛙从第二条跑道开始，使用变量 w 来表示当前所在的跑道。变量 l 用来表示当前位置，而 r 代表可以前进到的最远位置。策略是在每一步尝试前进，当遇到障碍时进行侧跳。青蛙前进到下一个位置时，如果该位置有障碍，那么需要进行侧跳。侧跳的选择是基于当前跑道和障碍的位置，使用公式 '6 - (w + obstacles[l])' 来确定最优的跳跃目标跑道。在没有障碍的情况下，尽量在当前跑道上前进直到遇到障碍或到达终点。这个过程通过 while 循环进行模拟。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中，使用了'6 - (w + obstacles[l])'公式来确定侧跳的目标跑道。这个公式如何确保总是选到一个没有障碍的跑道？
▷🦆
题解中提到，当在当前位置(l)有障碍时，会尝试侧跳。为什么在l位置有障碍时仍然使用obstacles[l]来计算新跑道？是否应该使用l+1处的障碍情况？
▷🦆
题解采用的贪心策略中，在遇到障碍时侧跳，但是如果当前位置和下一个位置都有障碍，这种情况下如何处理？
▷