java算法刷题02——深度优先搜索与广度优先搜索

Dear 丶 2023-10-01 09:56 2阅读 0赞

先通过一道特别经典的题目来回顾下DFS算法。

##### T1 无向图的遍历 #####

对下图的各个节点遍历，且不重复

![alt][]  
解法如下。

import java.util.Iterator;
    import java.util.LinkedList;
    
    /**
     *
     * 定义无向图
     */
    public class DFSGraph {
        
        // 顶点数
        private int vector;
        // 图的邻接表
        private LinkedList<Integer>[] adj;
    
        // 初始化无向图
        public DFSGraph(int v) {
        
            // 有v个顶点
            this.vector = v;
            // 一个长为v的数组，负责给每个顶点存放邻边
            adj = new LinkedList[v];
            // 邻边用LinkedList类型存放:易增删，进行初始化
            for (int i = 0; i < adj.length; i++) {
        
                adj[i] = new LinkedList();
            }
        }
    
        // 向图中某个顶点v添加邻边w
        public void addEdge(int v, int w) {
        
            adj[v].add(w);
        }
    
        // DFS算法设计
        public void DFS(int v) {
        
            // 用于记录每个节点是否被访问过
            boolean[] visited = new boolean[this.vector];
            // 回溯
            DFSUtil(v, visited);
        }
    
        // 回溯算法
        private void DFSUtil(int v, boolean[] visited) {
        
            // 访问节点v，标记当前节点被访问，输出该节点
            visited[v] = true;
            System.out.print(v + " ");
    
            // 遍历节点v的邻接矩阵，访问节点v的所有邻接节点
            Iterator<Integer> iterator = adj[v].listIterator();
            while (iterator.hasNext()) {
        
                int n = iterator.next();
                if(!visited[n]) {
        
                    DFSUtil(n, visited);
                }
            }
        }
    
        public static void main(String[] args) {
        
            DFSGraph g = new DFSGraph(4);
    
            g.addEdge(0, 1);
            g.addEdge(0, 2);
            g.addEdge(1, 2);
            g.addEdge(2, 0);
            g.addEdge(2, 3);
            g.addEdge(3, 3);
    
            System.out.println("下面是DFS搜索结果 " + "(从2号结点开始)");
    
            g.DFS(2);
    
        }
    }

##### T2 岛屿个数 #####

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。  
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。  
例如：  
输入  
\[  
\[1,1,0,0,0\],  
\[0,1,0,1,1\],  
\[0,0,0,1,1\],  
\[0,0,0,0,0\],  
\[0,0,1,1,1\]  
\]  
对应的输出为3  
示例1  
输入：

\[\[1,1,0,0,0\],\[0,1,0,1,1\],\[0,0,0,1,1\],\[0,0,0,0,0\],\[0,0,1,1,1\]\]

返回值：

示例2  
输入：

\[\[0\]\]

返回值：

示例3  
输入：

\[\[1,1\],\[1,1\]\]

返回值：

备注：

01矩阵范围<=200\*200

思路:  
(1)遍历数组找1，找到1则说明这是大陆，count++.同时通过置0标记已经侦测过，避免重复记录  
(2)从刚才侦测过的大陆上、下、左、右遍历，查找又没有连接的土地，把他们都置0，因为他们属于同一块陆地。  
代码如下:

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 判断岛屿数量
         * @param grid char字符型二维数组 
         * @return int整型
         */
       public int solve(char[][] grid) {
        
          if(grid == null || grid.length == 0) {
        
              return 0;
          }
          int count = 0;
          for (int i = 0; i < grid.length; i++) {
        
              for (int j = 0; j < grid[0].length; j++) {
        
                  if(grid[i][j] == '1') {
        
                      count ++;
                      dfs(grid, i, j);
                  }
              }
          }
           return count;
      }
    
        private void dfs(char[][] grid, int i, int j) {
        
          if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
        
              return;
          }
          grid[i][j] = '0';
          dfs(grid,i-1, j);
          dfs(grid,i+1, j);
          dfs(grid,i, j+1);
          dfs(grid,i, j-1);
    
        }
    }

到这里您是不是若有所思，原来dfs就是使用递归来实现阿。访问过则标记,避免重复访问。接着来看题。

##### T3.判断平衡二叉树 #####

描述  
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。  
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树  
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。  
注：我们约定空树是平衡二叉树。

数据范围：n \\le 100n≤100,树上节点的val值满足 0 \\le n \\le 10000≤n≤1000  
要求：空间复杂度O(1)O(1)，时间复杂度 O(n)O(n)  
输入描述：  
输入一棵二叉树的根节点  
返回值描述：  
输出一个布尔类型的值  
示例1  
输入：  
\{1,2,3,4,5,6,7\}  
复制  
返回值：  
true  
复制  
示例2  
输入：  
\{\}  
复制  
返回值：  
true

解答如下。

public class Solution {
        
        // 定义变量记录是否是平衡二叉树,默认为true，后面不符合条件则置false
        private boolean isBlanceTree = true;
        public boolean IsBalanced_Solution(TreeNode root) {
        
            // 判断该树是否为平衡二叉树:其实就是求左、右子树的的深度
            calDepth(root);
            return isBlanceTree;
        }
        
        public int calDepth(TreeNode root){
        
            // 递归出口
            if(root == null) return 0;
            // 递归求解左右子树的深度
            int l = calDepth(root.left);
            if(l == -1) return -1;
            int r = calDepth(root.right);
            if(r == -1) return -1;
            int depth = Math.max(l, r) + 1;
            if(Math.abs(l-r)>1){
         // 求左、右子树的深度差，如果有任一个左右子树不符合平衡树的条件，返回-1
                  isBlanceTree = false;
                   return -1;
            }
            return depth;
        }
    }

发现没有。使用递归时需要思考清楚:  
1.递归的退出条件是什么？如本题中，我们递归求解左、右子树的深度，如果一个节点没有左、右子树了，其深度仍然可以求：为1，仍属于递归求解范围，因此递归跳出条件是一个节点为null。  
2.递归返回类型是什么？因为下一次递归依赖上一次递归的返回结果，因此递归的返回结果一定是需要在多次递归中需要被传递的值。比如该题中我们返回的不是这个树是否是平衡二叉树，而是树的深度。  
3.递归的核心计算是什么？  
比如本题中，核心计算就是求树的深度，怎么做到呢？左、右子树最大深度加1.  
如果可以用这样的逻辑去思考递归算法，后续做题就更加简单了。

除了深度优先搜索遍历，广度优先搜索也常常应用于树和图的算法问题。先来实现两个简单的题目。

##### T4.二叉树的层次遍历（从根节点开始） #####

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：  
二叉树：\[3,9,20,null,null,15,7\],

返回其层序遍历结果：

\[  
\[3\],  
\[9,20\],  
\[15,7\]  
\]  
分析:不妨使用广度优先搜索，借助队列先进先出的特点实现。

//  二叉树的层次遍历(顺序)
    public class TreeLevel_1 {
        
        public static void main(String[] args) {
        
    
        }
    
        /**
         *
         * 层次遍历
         * @return 一个List集合，集合里有各个层级，每个层级也是一个List，里面放的是Integer类型
         */
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            // 返回结果
            List<List<Integer>> ret = new LinkedList<>();
            // 递归跳出条件
            if (root == null) {
        
                return ret;
            }
            // 队列
            Queue<TreeNode> queue = new LinkedList<>();
            // 根节点入队
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                // 遍历队列
                int currentLevelSize = queue.size();
                List<Integer> currentLevel = new LinkedList<>();
                for (int i = 0; i < currentLevelSize; i++) {
        
                    // 队列第一个节点出队
                    TreeNode node = queue.poll();
                    currentLevel.add(node.val);
                    // 出队节点的左、右节点入队
                    if(node.left != null) {
        
                        queue.offer(node.left);
                    }
                    if(node.right != null) {
        
                        queue.offer(node.right);
                    }
                }
                ret.add(currentLevel);
            }
            return ret;
        }
    }

##### T5.二叉树的层次遍历(自底向上) #####

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：  
给定二叉树 \[3,9,20,null,null,15,7\],

返回其自底向上的层序遍历为：

\[  
\[15,7\],  
\[9,20\],  
\[3\]  
\]  
解法:

public List<List<Integer>> levelOrder(TreeNode root) {
        
            // 返回结果
            List<List<Integer>> ret = new LinkedList<>();
            // 递归跳出条件
            if (root == null) {
        
                return ret;
            }
            // 队列
            Queue<TreeNode> queue = new LinkedList<>();
            // 根节点入队
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                // 遍历队列
                int currentLevelSize = queue.size();
                List<Integer> currentLevel = new LinkedList<>();
                for (int i = 0; i < currentLevelSize; i++) {
        
                    // 队列第一个节点出队
                    TreeNode node = queue.poll();
                    currentLevel.add(node.val);
                    // 出队节点的左、右节点入队
                    if(node.left != null) {
        
                        queue.offer(node.left);
                    }
                    if(node.right != null) {
        
                        queue.offer(node.right);
                    }
                }
                ret.add(0,currentLevel);
            }
            return ret;
        }

##### T6.被围绕的区域 #####

再看一道矩阵的应用题型。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2K5penNTE4_size_20_color_FFFFFF_t_70_g_se_x_16]  
分析:要想找出所有被`x`包围的`o`很难，但是我们可以逆向思维:找到所有在四边或者与四边相连的`o`，是则暂时改为为`A`，最后将所有`A`恢复成`O`,将所有剩下的`O`改`X`。那么问题就被简化了，因为我们可以通过深度优先搜索或者广度优先搜索来找到与四周相连接的`o`。对应到数组中，我们就是要找二维数组`board[0][j]`,`board[borad.length-1][j]`,`borad[i][0]`,`board[i][board[]0].length-1`及它们所连接的`o`了。如何进行遍历搜索呢?可以利用`i`,`j`的增减实现，具体的实现过程参考下面代码。  
解法:

public class AroundArea {
        
            int n, m;
    
            public void solve(char[][] board) {
        
    //          二维数组的长度
                n = board.length;
    //            如果长度为0，则返回，与节点为空的返回条件有异曲同工之妙
                if (n == 0) {
        
                    return;
                }
    //          二维数组的第二维长度
                m = board[0].length;
    //            遍历首、尾两列
                for (int i = 0; i < n; i++) {
        
    //                以列数为0和m-1的数组元素为起始点进行dfs递归
                    dfs(board, i, 0);
                    dfs(board, i, m - 1);
                }
    //            遍历收尾两行，同时首位两行第一个与最后一个元素已经被dfs递归过，无需重复递归
                for (int i = 1; i < m - 1; i++) {
        
                    dfs(board, 0, i);
                    dfs(board, n - 1, i);
                }
    //       遍历所有数组元素改值     
                for (int i = 0; i < n; i++) {
        
                    for (int j = 0; j < m; j++) {
        
                        if (board[i][j] == 'A') {
        
                            board[i][j] = 'O';
                        } else if (board[i][j] == 'O') {
        
                            board[i][j] = 'X';
                        }
                    }
                }
            }
            
            public void dfs(char[][] board, int x, int y) {
        
    //            递归跳出条件:1.越界,2.非O
                if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
        
                    return;
                }
    //            对符合条件的边界o或者与边界o相连接的o改值
                board[x][y] = 'A';
    //            递归调用自己，即深度扩展
                dfs(board, x + 1, y);
                dfs(board, x - 1, y);
                dfs(board, x, y + 1);
                dfs(board, x, y - 1);
            }
    
    }

总结下:  
代码主要分为两块逻辑:  
1.遍历元素，选择需要进行dfs的元素调用dfs算法  
2.dfs算法  
而dfs算法也很简单，分为四个个组成:  
1.退出条件:越界(二叉树中是节点为null)或者不符合判断条件(非`o`)  
2.核心操作，可能是输出，可能是改值，本题中就是改值  
3.递归进行dfs(本题等数组的递归条件是上下左右移动，而二叉树一般是结点的左右孩子节点的递归)。  
4.递归返回(有时候操作需要返回值给下一次递归，比如求二叉树的深度)

##### T7.省份数量 #####

怎么样？您是不是已经跃跃欲试了，下面我们套用上面的思考逻辑解决一道问题试试看。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2K5penNTE4_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
您是不是觉得似曾相识，怎么那么像岛屿数量那道题,不过，这可与岛屿那道题不同，这是一个图的类型题，我们需要构建一个图。那么要怎么求解呢?

public int findCircleNum(int[][] isConnected) {
        
            int provinces = isConnected.length;
            boolean[] visited = new boolean[provinces];
            int circles = 0;
            for (int i = 0; i < provinces; i++) {
        
                if (!visited[i]) {
        
                    dfs(isConnected, visited, provinces, i);
                    circles++;
                }
            }
            return circles;
        }
    
        public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
        
            for (int j = 0; j < provinces; j++) {
        
                if (isConnected[i][j] == 1 && !visited[j]) {
        
                    visited[j] = true;
                    dfs(isConnected, visited, provinces, j);
                }
            }
        }

这道题其实也是图的一种，但是题目使用的是数组，而不是LinkedList来存储数据。可以好好对比学习。

##### T8.岛屿面积 #####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2K5penNTE4_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
这个题目与岛屿数量雷同，需要注意定义`maxArea`与中间量`area`。

import java.util.*;
    class Solution {
        
        private int area;
            /**
             * 判断岛屿面积
             * @param grid int二维数组 
             * @return int整型
             */
            public int maxAreaOfIsland(int[][] grid) {
        
                if(grid == null || grid.length == 0) {
        
                    return 0;
                }
                int maxArea = 0;
                for (int i = 0; i < grid.length; i++) {
        
                    for (int j = 0; j < grid[0].length; j++) {
        
                        if(grid[i][j] == 1) {
        
                            area = 0;
                            dfs(grid, i, j);
                            if(area>maxArea) {
        
                                maxArea = area;
                            }
                        }
                    }
                }
                return maxArea;
            }
    
            private int dfs(int[][] grid, int i, int j) {
        
                if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
        
                    return 0;
                }
                grid[i][j] = 0;
                dfs(grid,i-1, j);
                dfs(grid,i+1, j);
                dfs(grid,i, j+1);
                dfs(grid,i, j-1);
                return area++;
            }
    
    }

[alt]: https://img-blog.csdnimg.cn/img_convert/7cb8ec227dd7be3115deba5d36f2cf6f.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2K5penNTE4_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/59b5c71e6b0748d8892d77f45af38951.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y2K5penNTE4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2K5penNTE4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/8fc13899b69f43bfa6030d0ef36b54f7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y2K5penNTE4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y2K5penNTE4_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/e7c9197e628b4bc9a71c5e47ce86441b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y2K5penNTE4,size_20,color_FFFFFF,t_70,g_se,x_16