class Solution {
public:
int minJumps(vector<int>& arr) {
}
};
1345. 跳跃游戏 IV
给你一个整数数组 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原站题解
javascript 解法, 执行用时: 216 ms, 内存消耗: 72.3 MB, 提交时间: 2023-06-05 14:25:25
/**
* @param {number[]} arr
* @return {number}
*/
var minJumps = function(arr) {
const idxMap = new Map(), explored = new Set()
for(let i=0;i<arr.length;i++){
if(idxMap.has(arr[i]))
idxMap.get(arr[i]).push(i)
else
idxMap.set(arr[i], [i])
}
let nodes = [0], step = 0
explored.add(0)
while(nodes.length > 0){
const nxt = new Array()
for(const cur of nodes){
if(cur == arr.length - 1)
return step
if(idxMap.has(arr[cur])){
for(const other of idxMap.get(arr[cur])){
if(!explored.has(other)){
explored.add(other)
nxt.push(other)
}
}
idxMap.delete(arr[cur])
}
if(!explored.has(cur + 1)){
explored.add(cur + 1)
nxt.push(cur + 1)
}
if(cur > 0 && !explored.has(cur - 1)){
explored.add(cur - 1)
nxt.push(cur - 1)
}
}
nodes = nxt
step++
}
return arr.length - 1
};
golang 解法, 执行用时: 108 ms, 内存消耗: 11.1 MB, 提交时间: 2023-06-05 14:25:07
func minJumps(arr []int) int {
idxMap, steps := map[int][]int{}, make([]int, len(arr))
for i := 0; i < len(arr); i++ {
l := idxMap[arr[i]]
l = append(l, i)
idxMap[arr[i]] = l
steps[i] = len(arr) - 1
}
queue := []int{0}
steps[0] = 0
for len(queue) > 0 {
idx := queue[0]
if idx == len(arr) - 1{
break
}
nxtStep := steps[idx] + 1
queue = queue[1:]
l, ok := idxMap[arr[idx]]
if ok {
for _, other := range l {
if steps[other] > nxtStep {
steps[other] = nxtStep
queue = append(queue, other)
}
}
delete(idxMap, arr[idx])
}
if other := idx + 1; steps[other] > nxtStep {
steps[other] = nxtStep
queue = append(queue, other)
}
if idx > 0{
if other := idx - 1; steps[other] > nxtStep {
steps[other] = nxtStep
queue = append(queue, other)
}
}
}
return steps[len(arr) - 1]
}
golang 解法, 执行用时: 156 ms, 内存消耗: 17.4 MB, 提交时间: 2023-06-05 14:24:56
func minJumps(arr []int) int {
n := len(arr)
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{{}}
for {
p := q[0]
q = q[1:]
i, step := p.idx, p.step
if i == n-1 {
return step
}
for _, j := range idx[arr[i]] {
if !vis[j] {
vis[j] = true
q = append(q, pair{j, step + 1})
}
}
delete(idx, arr[i])
if !vis[i+1] {
vis[i+1] = true
q = append(q, pair{i + 1, step + 1})
}
if i > 0 && !vis[i-1] {
vis[i-1] = true
q = append(q, pair{i - 1, step + 1})
}
}
}
java 解法, 执行用时: 72 ms, 内存消耗: 60 MB, 提交时间: 2023-06-05 14:24:41
class Solution {
public int minJumps(int[] arr) {
Map<Integer, List<Integer>> idxSameValue = new HashMap<Integer, List<Integer>>();
for (int i = 0; i < arr.length; i++) {
idxSameValue.putIfAbsent(arr[i], new ArrayList<Integer>());
idxSameValue.get(arr[i]).add(i);
}
Set<Integer> visitedIndex = new HashSet<Integer>();
Queue<int[]> queue = new ArrayDeque<int[]>();
queue.offer(new int[]{0, 0});
visitedIndex.add(0);
while (!queue.isEmpty()) {
int[] idxStep = queue.poll();
int idx = idxStep[0], step = idxStep[1];
if (idx == arr.length - 1) {
return step;
}
int v = arr[idx];
step++;
if (idxSameValue.containsKey(v)) {
for (int i : idxSameValue.get(v)) {
if (visitedIndex.add(i)) {
queue.offer(new int[]{i, step});
}
}
idxSameValue.remove(v);
}
if (idx + 1 < arr.length && visitedIndex.add(idx + 1)) {
queue.offer(new int[]{idx + 1, step});
}
if (idx - 1 >= 0 && visitedIndex.add(idx - 1)) {
queue.offer(new int[]{idx - 1, step});
}
}
return -1;
}
}
java 解法, 执行用时: 107 ms, 内存消耗: 53.9 MB, 提交时间: 2023-06-05 14:24:23
class Solution {
public int minJumps(int[] arr) {
Map<Integer, List<Integer>> idxMap = new HashMap<>();
int[] steps = new int[arr.length];
for(int i=0;i<arr.length;i++){
List<Integer> list = idxMap.getOrDefault(arr[i], new ArrayList<>());
list.add(i);
idxMap.put(arr[i], list);
steps[i] = arr.length - 1;
}
Deque<Integer> queue = new ArrayDeque<>();
queue.addLast(0);
steps[0] = 0;
while(!queue.isEmpty()){
int idx = queue.pollFirst();
if(idx == arr.length - 1)
break;
int nxtStep = steps[idx] + 1;
List<Integer> list = idxMap.getOrDefault(arr[idx], new ArrayList<>());
list.add(idx + 1);
if(idx > 0)
list.add(idx - 1);
for(int other: list)
if(steps[other] > nxtStep){
steps[other] = nxtStep;
queue.addLast(other);
}
idxMap.remove(arr[idx]);
}
return steps[arr.length - 1];
}
}
python3 解法, 执行用时: 336 ms, 内存消耗: 31 MB, 提交时间: 2023-06-05 14:24:08
class Solution:
def minJumps(self, arr: List[int]) -> int:
idx_map, steps = defaultdict(list), [len(arr) - 1] * len(arr)
for i, num in enumerate(arr):
idx_map[num].append(i)
queue = deque([0])
steps[0] = 0
while queue:
idx = queue.popleft()
if idx == len(arr) - 1:
break
nxt_step = steps[idx] + 1
idx_map[arr[idx]] += [idx+1,idx-1] if idx else [idx+1]
while idx_map[arr[idx]]:
if steps[(other:=idx_map[arr[idx]].pop())] > nxt_step:
steps[other] = nxt_step
queue.append(other)
return steps[-1]
python3 解法, 执行用时: 360 ms, 内存消耗: 31.8 MB, 提交时间: 2023-06-05 14:23:58
class Solution:
def minJumps(self, arr: List[int]) -> int:
idxSameValue = defaultdict(list)
for i, a in enumerate(arr):
idxSameValue[a].append(i)
visitedIndex = set()
q = deque()
q.append([0, 0])
visitedIndex.add(0)
while q:
idx, step = q.popleft()
if idx == len(arr) - 1:
return step
v = arr[idx]
step += 1
for i in idxSameValue[v]:
if i not in visitedIndex:
visitedIndex.add(i)
q.append([i, step])
del idxSameValue[v]
if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:
visitedIndex.add(idx + 1)
q.append([idx+1, step])
if idx - 1 >= 0 and (idx - 1) not in visitedIndex:
visitedIndex.add(idx - 1)
q.append([idx-1, step])