1345. 跳跃游戏 IV - 力扣（LeetCode）
1345. 跳跃游戏 IV - 给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。 每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ： * i + 1 需满足：i + 1 < arr.length * i - 1 需满足：i - 1 >= 0 * j 需满足：arr[i] == arr[j] 且 i != j 请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。 注意：任何时候你都不能跳到数组外面。 示例...
思路
还挺明显的BFS，每次尝试移到当前位置所能跳转的所有位置，并做记录以便剪枝。这样时间复杂度就是O(n)。
代码
推荐阅读
[问与答] 已有 OpenAI 账户，在苹果上已经订阅了美区的 GPT Plus 方案。如何安全切到土区的 Plus 订阅
推荐阅读
[问与答] 已有 OpenAI 账户，在苹果上已经订阅了美区的 GPT Plus 方案。如何安全切到土区的 Plus 订阅
class Solution {
public int minJumps(int[] arr) {
int n = arr.length;
if (n <= 2) {
return n - 1;
}
// 存储相同的值(可直接跳转)
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0});
boolean[] vis = new boolean[n];
vis[0] = true;
// bfs
while (!queue.isEmpty()) {
int[] idxStep = queue.poll();
int idx = idxStep[0], step = idxStep[1];
if (idx == arr.length - 1) {
return step;
}
step++;
// 直接跳转
List<Integer> sameValue = map.remove(arr[idx]);
if (sameValue != null) {
for (int i : sameValue) {
if (!vis[i]) {
vis[i] = true;
queue.offer(new int[]{i, step});
}
}
}
// 左移
if (idx - 1 >= 0 && !vis[idx - 1]) {
vis[idx - 1] = true;
queue.offer(new int[]{idx - 1, step});
}
// 右移
if (idx + 1 < arr.length && !vis[idx + 1]) {
vis[idx + 1] = true;
queue.offer(new int[]{idx + 1, step});
}
}
return -1;
}
}
1 个帖子 - 1 位参与者
来源: LinuxDo 最新话题查看原文