通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

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

275人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode  | 

作者:因情语写

链接:https://www.qingyu.blue/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
}
  1. 如代码所示,在每一轮中,队列中的结点是等待处理的结点。
  2. 在每个更外一层的 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
}

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

  1. 你完全确定没有循环,例如,在树遍历中;
  2. 你确实希望多次将结点添加到队列中。

    算法-墙与门

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

  1. -1 表示墙或是障碍物
  2. 0 表示一扇门
  3. 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

提示:

  1. 死亡列表 deadends 的长度范围为 [1, 500]。
  2. 目标数字 target 不会在 deadends 之中。
  3. 每个 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) 打赏

全部评论

还没有评论!