LeetCode LCP09:最小跳跃次数——广度优先搜索的优雅写法

前言

看评论又学了一手：

以往在广度优先搜索的场景中，使用一个队列，如果想进行层次的遍历，我的做法是再new一个队列，把新出现的元素放到新队列中，完成后再将新队列赋给原先的指针。即

while(!queue.isEmpty()) {
	Queue<Integer> next = new LinkedList();
	int cur = queue.poll();
	while(!queue.isEmpty()) {
		//add some item to new queue
	}
	//finish one layer
	queue = next;
}

而实际上，这样就可以解决

while(!queue.isEmpty()) {
	int size = queue.size();
	while(size-- >0) {
		//add some item to new queue
	}
	//finish one layer
}

感觉自己的代码又优雅了=-=

题目

最小跳跃次数

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

示例 1：

输入：jump = [2, 5, 1, 1, 1, 1]

输出：3

解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。

分析

广度优先搜索，我们维护一个队列，内层循环每次遍历当前跳跃次数能到达的点，把下一步能到达的点加入队列。

下一步能到达的点有两种，一种是i+jump[i]即向右跳到达的点。一种是左边的所有点，我们用一个visited数组来标记左边的点是否被访问过，防止重复访问。

我们维护一个far索引，来表示左边被访问过的部分的有边界是哪里，每次我们从这个边界出发，到达当前位置，将所有的未访问过的点入队。

由于far索引的存在，所以这个入队的整体时间复杂度是O(n)。

代码

class Solution {
    public int minJump(int[] jump) {
        Queue<Integer> queue = new LinkedList();
        boolean[] visited = new boolean[jump.length];
        queue.offer(0);
        visited[0] = true;;

        int step = 1;
        int far = 0;

        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int cur = queue.poll();
                int next = cur + jump[cur];
                if(next >= jump.length) { 
                //如果这一步能跳出边界，直接返回
                    return step;
                }
                if(!visited[next]) {
                //右边的点未访问过则入队
                    queue.offer(next);
                    visited[next] = true;
                }
                for(int i = far; i < cur; i++) if(!visited[i]){
                //左边的点未访问过则入队
                //far记录着当前左边所有遍历过的点的右边界，每次可直接从far开始遍历
                    queue.offer(i);
                    visited[i] = true;
                }
                //更新far索引
                far = Math.max(far, cur-1);
            }
            step++;
        }
        return -1;
    }
}

本文地址：https://blog.csdn.net/GaleZhang/article/details/108583184