45. 跳跃游戏 II(leetcode,最短路做法)

45. 跳跃游戏 II

class Solution {public int jump(int[] nums) {// 最短路做法:// 起始点为0,终点为n-1,边权重为0~nums[i]Deque<int[]> q=new ArrayDeque<>();boolean[] vis=new boolean[nums.length];q.add(new int[]{0,0}); // 顶点,步数vis[0]=true;while(!q.isEmpty()){int[] t=q.pop();if(t[0]==nums.length-1)return t[1];for(int i=1;i<=nums[t[0]];i++){if(t[0]+i>=nums.length || vis[t[0]+i]==true)continue;q.add(new int[]{t[0]+i,t[1]+1});vis[t[0]+i]=true;}}return -1;}
}