超时了怎么优化
作者:
我不叫喂
,
2023-11-09 18:43:44
,
所有人可见
,
阅读 91
跳跃游戏
class Solution {
public static void main(String[] args) {
System.out.println(minJumps(new int[]{100,-23,-23,404,100,23,23,23,3,404}));
}
public static int minJumps(int[] arr) {
Queue<Integer> queue = new ArrayDeque<>();//层次遍历,每层可以去的位置下标
Map<Integer, Integer> map = new HashMap<>();
queue.offer(0);
map.put(0, 0);
while (!queue.isEmpty()) {
int t = queue.poll();
if (t == arr.length - 1) return map.get(t);
int res = arr[t];
if (t != 0 && !map.containsKey(t - 1)) {
queue.offer(t - 1);
map.put(t - 1, map.get(t) + 1);
}
if (t != queue.size() - 1 && !map.containsKey(t + 1)) {
queue.offer(t + 1);
map.put(t + 1, map.get(t) + 1);
}
for (int i = 0; i < arr.length; i++) {
if (res == arr[i] && !map.containsKey(i)) {
queue.offer(i);
map.put(i, map.get(t) + 1);
}
}
}
return arr.length;
}
}
DP