力扣 --- 45. 跳跃游戏II

45. 跳跃游戏II

2020.05.04 22:58

题目描述：

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一次位置。

示例：

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明：假设你总是可以到达数组得最后一个位置

贪心算法–尽可能地多(贪)

题解：

解法一：倒着来，往回跳

从最后一个位置往后找，谁离我最远并且能够跳到我这里，就定位到那个位置，然后从这个位置继续往后跳，
直到跳到idx == 0结束，然后这样记录步数。
每回跳一次，步数+1

class Solution{
    //思路一：倒着来
    public int jump1(int[] nums) {
        int len = nums.length;
        int idx = len - 1;
        int steps = 0;
        //当idx到0或者比0还小的时候说明OK了
        while(idx > 0){
            //从0开始找第一个能一步跳过来的，当然是离我最远的能到我这里的
            for(int i = 0; i < idx; i++){
                if( i + nums[i] >= idx){
                    idx = i;
                    break;
                }
            }
            steps++;
        }
        return steps;
    }
}

时间复杂度O(N^2) 空间O(1)

解法二：正着来

从第一个位置开始跳，在nums[0]的范围内，去看看哪个位置能够跳得更远，那就跳到那个位置，
然后继续从那个位置又这样找,直到跳到最后一个位置。
 每跳一次，步数+1

class Solution {
    //思路二：正着来
    public int jump2(int[] nums) {
        int len = nums.length;
        int end = 0;
        int steps = 0;
        //始终去维护一个边界，就是现在能跳得范围，在这个范围里面去找跳的最远的，也就是新的边界。
        //当到达这个边界时，就会更新这个边界
        int maxStep = 0;
        for(int i = 0; i < len - 1; i++){
            maxStep = Math.max(maxStep, i + nums[i]);//找新的end边界，一定是最远的那个
            if(i == end){//如果跑到了现在的边界
                //更新边界
                end =maxStep;
                steps++;
            }
        }
        return steps;
    }
}

时间复杂度O(N) 空间O(1)

解法三：bfs

看了群里甜姨的思路，用bfs进行求解。每一层遍历完进行一次step++操作，然后用vis[]注意是否访问过的

刚开始nums[0]入队，然后poll出来，把nums[0]能跳的位置都入队。
关于如何增加步数，每遍历完一层，step++。还要用一个vis[]记录是否已经遍历过

class Solution {
    //思路三：bfs
    public int jump(int[] nums) {
        int len = nums.length;
        if(len == 1){
            return 0;
        }
        Queue<Integer> queue = new LinkedList<>();
        boolean[] vis = new boolean[len];
        queue.add(0);//将第一个入队
        vis[0] = true;
        int steps = 0;
        while(!queue.isEmpty()){
            //将这一层的全部遍历完
            steps++;
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int idx = queue.poll();
                for(int j = nums[idx]; j > 0 ; j--){
                    if(j + idx >= len - 1){
                        return steps;
                    }
                    if(!vis[j + idx]){  
                        vis[j + idx] = true;
                        queue.add(j + idx); 
                    }
                }
            }   
        }
        return steps;
    }
}