leetcode探索之队列 & 栈学习队列和广度优先搜索

通知

此博客运行在jpress系统上，如果你喜欢此博客模板，请加QQ群：1061691290（whimurmur模板/jpress插件），免费下载使用

leetcode探索之队列 & 栈学习队列和广度优先搜索

676人浏览 / 0人评论 | 作者：whisper | 分类：设计模式与算法 | 标签：设计模式与算法 / leetcode |

作者：whisper

链接：http://proprogrammar.com:443/article/593

声明：请尊重原作者的劳动，如需转载请注明出处

先决条件：树的层序遍历

广度优先搜索（BFS）是一种遍历或搜索数据结构（如树或图）的算法。

如前所述，我们可以使用 BFS 在树中执行层序遍历。

我们也可以使用 BFS 遍历图。例如，我们可以使用 BFS 找到从起始结点到目标结点的路径，特别是最短路径。

我们可以在更抽象的情景中使用 BFS 遍历所有可能的状态。在这种情况下，我们可以把状态看作是图中的结点，而以合法的过渡路径作为图中的边。

本章节中，我们将简要介绍 BFS 是如何工作的，并着重关注队列如何帮助我们实现 BFS 算法。我们还将提供一些练习，供你自行设计和实现 BFS 算法。

队列和 BFS

广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。在本文中，我们提供了一个示例来解释在 BFS 算法中是如何逐步应用队列的。

示例

这里我们提供一个示例来说明如何使用 BFS 来找出根结点 A 和目标结点 G 之间的最短路径。

洞悉

观看上面的动画后，让我们回答以下问题：

1. 结点的处理顺序是什么？

在第一轮中，我们处理根结点。在第二轮中，我们处理根结点旁边的结点；在第三轮中，我们处理距根结点两步的结点；等等等等。

与树的层序遍历类似，越是接近根结点的结点将越早地遍历。

如果在第 k 轮中将结点 X 添加到队列中，则根结点与 X 之间的最短路径的长度恰好是 k。也就是说，第一次找到目标结点时，你已经处于最短路径中。

2. 队列的入队和出队顺序是什么？

如上面的动画所示，我们首先将根结点排入队列。然后在每一轮中，我们逐个处理已经在队列中的结点，并将所有邻居添加到队列中。值得注意的是，新添加的节点不会立即遍历，而是在下一轮中处理。

结点的处理顺序与它们添加到队列的顺序是完全相同的顺序，即先进先出（FIFO）。这就是我们在 BFS 中使用队列的原因。

广度优先搜索 - 模板

之前，我们已经介绍了使用 BFS 的两个主要方案：遍历或找出最短路径。通常，这发生在树或图中。正如我们在章节描述中提到的，BFS 也可以用于更抽象的场景中。

在本文中，我们将为你提供一个模板。然后，我们在本文后提供一些习题供你练习。

在特定问题中执行 BFS 之前确定结点和边缘非常重要。通常，结点将是实际结点或是状态，而边缘将是实际边缘或可能的转换。

模板 I

在这里，我们为你提供伪代码作为模板：

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

如代码所示，在每一轮中，队列中的结点是等待处理的结点。
在每个更外一层的 while 循环之后，我们距离根结点更远一步。变量 step 指示从根结点到我们正在访问的当前结点的距离。

模板 II

有时，确保我们永远不会访问一个结点两次很重要。否则，我们可能陷入无限循环。如果是这样，我们可以在上面的代码中添加一个哈希集来解决这个问题。这是修改后的伪代码：

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> used;     // store all the used nodes
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

有两种情况你不需要使用哈希集：

你完全确定没有循环，例如，在树遍历中；

你确实希望多次将结点添加到队列中。

算法-墙与门

你被给定一个 m × n 的二维网格，网格中有以下三种可能的初始化值：

-1 表示墙或是障碍物

0 表示一扇门

INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。

你要给每个空房间位上填上该房间到最近门的距离，如果无法到达门，则填 INF 即可。

示例：

给定二维网格：
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF
运行完你的函数后，该网格应该变成：
  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

class Solution {
    // 找门，从门bfs，如果到房间距离比原来的值小，则更新并处理下一层
    public void wallsAndGates(int[][] rooms) {
        Queue<int[]> queue = new LinkedList<>();
        int size, layer;
        int[] cur;
        
        for(int i = 0; i < rooms.length; i++){
            for(int j = 0; j < rooms[0].length; j++){
                // 如果是门，广搜一下
                if(rooms[i][j] == 0){
                    layer = 0;
                    queue.offer(new int[]{i, j});
                    
                    while(!queue.isEmpty()){
                        size = queue.size();
                        layer++;
                        for(int k = 0; k < size; k++){
                            cur = queue.poll();
                            if(cur[0] > 0 && rooms[cur[0] - 1][cur[1]] > layer){
                                rooms[cur[0] - 1][cur[1]] = layer;
                                queue.offer(new int[]{cur[0] - 1, cur[1]});
                            }
                            if(cur[0] < rooms.length - 1 && rooms[cur[0] + 1][cur[1]] > layer){
                                rooms[cur[0] + 1][cur[1]] = layer;
                                queue.offer(new int[]{cur[0] + 1, cur[1]});
                            }
                            if(cur[1] > 0 && rooms[cur[0]][cur[1] - 1] > layer){
                                rooms[cur[0]][cur[1] - 1] = layer;
                                queue.offer(new int[]{cur[0], cur[1] - 1});
                            }
                            if(cur[1] < rooms[0].length - 1 && rooms[cur[0]][cur[1] + 1] > layer){
                                rooms[cur[0]][cur[1] + 1] = layer;
                                queue.offer(new int[]{cur[0], cur[1] + 1});
                            }
                        }
                    }
                }
            }
        }
    }
}

中规中矩的广度优先，以门为起点，距门越远房间值越大，核心就是如果房间值大于距离当前门的距离，那么更新房间值并将房间加入队列（说明要处理该房间相邻房间）

下面看一下另一种较快的算法

class Solution {
    public void wallsAndGates(int[][] room) {
        if (room == null || room.length == 0) {
            return;
        }
        int m = room.length;
        int n = room[0].length;
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (room[row][col] == 0) {
                    bfs(room, 0, row, col);
                }
            }
        }
    }

    private void bfs(int[][] room, int count, int row, int col) {
        if (row < 0 || col < 0 || row >= room.length || col >= room[0].length || room[row][col] < count) {
            return;
        }
        room[row][col] = count;
        bfs(room, count + 1, row - 1, col);
        bfs(room, count + 1, row + 1, col);
        bfs(room, count + 1, row, col - 1);
        bfs(room, count + 1, row, col + 1);
    }
}

核心思想一样，但没有用栈，而是用了递归的广度优先搜索

算法-岛屿数量

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:
输入:
11110
11010
11000
00000

输出: 1
示例 2:
输入:
11000
11000
00100
00011

输出: 3

class Solution {
    // 想法，每出现陆地，结果加1，将相邻陆地置'0'，还有另一种解法：https://blog.csdn.net/weixin_40550726/article/details/82943658
    public int numIslands(char[][] grid) {
        int result = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    result++;
                    maskIsland(i, j, grid);
                }
            }
        }
        
        return result;
    }
    
    private void maskIsland(int i, int j, char[][] grid){        
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'){
            return;
        }
        
        grid[i][j] = '0';
        
        maskIsland(i+1, j, grid);
        maskIsland(i, j-1, grid);
        maskIsland(i-1, j, grid);
        maskIsland(i, j+1, grid);
    }
}

算法思想在代码注释里

算法-打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1
提示：

死亡列表 deadends 的长度范围为 [1, 500]。

目标数字 target 不会在 deadends 之中。

每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

class Solution {
    // 想法：双端逼近：从初始值和目标值两端逼近，等到两端出现同一个数时即得到结果,
    // 参考：https://blog.csdn.net/u013062192/article/details/83588358
    public int openLock(String[] deadends, String target) {
        Set<String> initSet = new HashSet<>();
        Set<String> targetSet = new HashSet<>();
        Set<String> temp;
        Set<String> visited = new HashSet<>();
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        int result = 0;
        List<String> next;
        
        if(dead.contains(target) || dead.contains("0000")){
            return -1;
        }else if("0000".equals(target)){
            return 0;
        }
        
        initSet.add("0000");
        targetSet.add(target);
        
        while(!initSet.isEmpty() && !targetSet.isEmpty()){
            if(initSet.size() > targetSet.size()){
                temp = targetSet;
                targetSet = initSet;
                initSet = temp;
            }
            
            temp = new HashSet<>();
            for(String s: initSet){
                if(targetSet.contains(s)){
                    return result;
                }else if(!dead.contains(s) && !visited.contains(s)){
                    visited.add(s);
                    next = findNext(s);
                    temp.addAll(next);
                }
            }
            
            initSet = temp;
            result++;
        }
        
        return -1;
    }
           
    private List<String> findNext(String cur){
        List<String> result = new ArrayList<>();
        char[] curChar = cur.toCharArray(), temp;
        
        for(int i = 0; i < 4; i++){
            temp = Arrays.copyOf(curChar, 4);
            if(temp[i] == '9'){
                temp[i] = '0';
            }else{
                temp[i] += 1;
            }
            
            result.add(String.valueOf(temp));
            
            temp = Arrays.copyOf(curChar, 4);
            if(temp[i] == '0'){
                temp[i] = '9';
            }else{
                temp[i] -= 1;
            }
            
            result.add(String.valueOf(temp));
        }
        
        return result;
    }
}

每一轮查看初始集合与目标集合是否出现相等，没有的话将较小的集合拨动一次（这是一个技巧），取所有情况作为下个集合值，注意去掉已处理过的元素

算法-完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

class Solution {
    // 想法：动态规划，找1，2...的最少完全平方数，n的完全平方数等于n-i*i的完全平方数加1
    public int numSquares(int n) {
        int[] arr = new int[n+1];
        Arrays.fill(arr, 10000);
        int j;
        arr[0] = 0;
        arr[1] = 1;
        
        for(int i =2; i <= n; i++){
            j = 1;
            while(i >= j * j){
                arr[i] = Math.min(arr[i - j * j] + 1, arr[i]);
                j++;
            }
        }
        
        return arr[n];
    }
}

动态规划解法，思想在代码注释中，注意开始令dp[i]为一个很大的值

下面给出一种数学上的解法

class Solution {

    public int numSquares(int n) {
        while(n%4 == 0)
        {
        	n = n/4;
        }
        if(n%8 == 7)
        {
        	return 4;
        }
        int io = (int)Math.sqrt(n);
        if(io*io == n)
        {
        	return 1;
        }
        
        for(int i = 1; i*i<n; i++)
        {
        	int oi = (int)Math.sqrt(n-i*i);
        	if(oi*oi+i*i == n)
        	{
        		return 2;
        	}
        }
        return 3;
    }

}

算法思想：

Lagrange 四平方定理：任何一个正整数都可以表示成不超过四个整数的平方之和。

那么我们这个问题的解法就变得很简单了，我们的结果只有1,2,3,4，四种可能。

另外还有一个非常重要的推论

满足四数平方和定理的数n（这里要满足由四个数构成，小于四个不行），必定满足 n = 4^a*(8b + 7)

根据这个重要的推论，我们可以非常迅速的写出这样的代码。

我们首先将输入的n迅速缩小。然后我们再判断，这个缩小后的数是否可以通过两个平方数的和或一个平方数组成，不能的话我们返回3，能的话我们返回平方数的个数。

注：这里可以缩小是因为缩小了4^a倍，而4^a = (2a)^2，如果n缩小后可以组成两个或一个数的平方，只要将这两个或一个数乘2a，那么乘2a后的这两个数或一个数就是n的平方和。

亲爱的读者：有时间可以点赞评论一下

我慒慒懂懂过了一年，这一年似乎没有改变，守着一个人的世界，空空如也

点赞(0) 打赏

全部评论

还没有评论！

注册登陆

搜索

泽被生民，一路走好

月份	原创文章数
202212	3
202103	10
202102	14
202010	3
202009	3
202008	8
202007	7
202006	10
202005	11
202004	22
202003	52
202002	44
202001	83
201912	52
201911	29
201910	41
201909	99
201908	35
201907	73
201906	121
201811	1
201810	2
201804	1
201803	1
201802	1
201707	1

月份	转载文章数
202212	4
202103	2
202102	3
202009	5
202008	3
202007	17
202005	17
202004	23
202003	11
202002	2
201912	13
201909	1