| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
困难 |
1809 |
第 19 场双周赛 Q4 |
|
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
i + 1需满足：i + 1 < arr.lengthi - 1需满足：i - 1 >= 0j需满足：arr[i] == arr[j]且i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404] 输出：3 解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
示例 2：
输入：arr = [7] 输出：0 解释：一开始就在最后一个元素处，所以你不需要跳跃。
示例 3：
输入：arr = [7,6,9,6,9,6,9,7] 输出：1 解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
提示：
1 <= arr.length <= 5 * 104-108 <= arr[i] <= 108
class Solution:
def minJumps(self, arr: List[int]) -> int:
idx = defaultdict(list)
for i, v in enumerate(arr):
idx[v].append(i)
q = deque([(0, 0)])
vis = {0}
while q:
i, step = q.popleft()
if i == len(arr) - 1:
return step
v = arr[i]
step += 1
for j in idx[v]:
if j not in vis:
vis.add(j)
q.append((j, step))
del idx[v]
if i + 1 < len(arr) and (i + 1) not in vis:
vis.add(i + 1)
q.append((i + 1, step))
if i - 1 >= 0 and (i - 1) not in vis:
vis.add(i - 1)
q.append((i - 1, step))class Solution {
public int minJumps(int[] arr) {
Map<Integer, List<Integer>> idx = new HashMap<>();
int n = arr.length;
for (int i = 0; i < n; ++i) {
idx.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
Deque<int[]> q = new LinkedList<>();
Set<Integer> vis = new HashSet<>();
vis.add(0);
q.offer(new int[] {0, 0});
while (!q.isEmpty()) {
int[] e = q.pollFirst();
int i = e[0], step = e[1];
if (i == n - 1) {
return step;
}
int v = arr[i];
++step;
for (int j : idx.getOrDefault(v, new ArrayList<>())) {
if (!vis.contains(j)) {
vis.add(j);
q.offer(new int[] {j, step});
}
}
idx.remove(v);
if (i + 1 < n && !vis.contains(i + 1)) {
vis.add(i + 1);
q.offer(new int[] {i + 1, step});
}
if (i - 1 >= 0 && !vis.contains(i - 1)) {
vis.add(i - 1);
q.offer(new int[] {i - 1, step});
}
}
return -1;
}
}class Solution {
public:
int minJumps(vector<int>& arr) {
unordered_map<int, vector<int>> idx;
int n = arr.size();
for (int i = 0; i < n; ++i) idx[arr[i]].push_back(i);
queue<pair<int, int>> q;
q.emplace(0, 0);
unordered_set<int> vis;
vis.insert(0);
while (!q.empty()) {
auto e = q.front();
q.pop();
int i = e.first, step = e.second;
if (i == n - 1) return step;
int v = arr[i];
++step;
if (idx.count(v)) {
for (int j : idx[v]) {
if (!vis.count(j)) {
vis.insert(j);
q.emplace(j, step);
}
}
idx.erase(v);
}
if (i + 1 < n && !vis.count(i + 1)) {
vis.insert(i + 1);
q.emplace(i + 1, step);
}
if (i - 1 >= 0 && !vis.count(i - 1)) {
vis.insert(i - 1);
q.emplace(i - 1, step);
}
}
return -1;
}
};func minJumps(arr []int) int {
idx := map[int][]int{}
for i, v := range arr {
idx[v] = append(idx[v], i)
}
vis := map[int]bool{0: true}
type pair struct{ idx, step int }
q := []pair{{0, 0}}
for len(q) > 0 {
e := q[0]
q = q[1:]
i, step := e.idx, e.step
if i == len(arr)-1 {
return step
}
step++
for _, j := range idx[arr[i]] {
if !vis[j] {
vis[j] = true
q = append(q, pair{j, step})
}
}
delete(idx, arr[i])
if i+1 < len(arr) && !vis[i+1] {
vis[i+1] = true
q = append(q, pair{i + 1, step})
}
if i-1 >= 0 && !vis[i-1] {
vis[i-1] = true
q = append(q, pair{i - 1, step})
}
}
return -1
}