BAT手撕算法题·深度优先遍历

vlambda
2020-07-07

BAT手撕算法题·深度优先遍历

深度优先遍历（dfs，deep first search）的思想最早来源于图论，和宽度优先遍历组成了两大遍历算法，但他们有不同的应用场景。本文从lc中的几道经典面试常问深度优先遍历问题入手，教你一步搞定这类问题。

一.什么是深度优先遍历

这⾥的深度优先遍历与图论中的深度优先遍历思路⼀致，即从⼀个点中找到另⼀个点，并且在另⼀个点中再继续深⼊地去查找，⼀条搜索路径是深⼊到底的。

1.DFS和回溯的区别

回溯实质上是DFS的⼀种应⽤。对于DFS来讲，⼀般都会有⼀个visited数组来标示当前是否访问过某个点，然后下次遍历过程中不要重复地访问。两者都有可能需要将访问状态回溯。

2.DFS和BFS的区别

BFS是⼴度优先遍历，通常会借助队列来存储已经遍历到的节点，和树的层序遍历类似。宽度优先遍历的⼀次搜索路径是很宽并且短的，所以可⽤来实现⽆向图的最短路径搜索。

3.dfs应⽤场景

1.求连通分量

2.搜索类/标记类问题

3.求路径问题和连通问题

⼆.LeetCode题⽬

1.单词搜索

https://leetcode-cn.com/problems/word-search/

2.代码实现

class Solution { // 定义方向数组 private int[][] directed = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private boolean[][] visited; private char[][] board; private String word; private int rows; private int cols; 
 public boolean exist(char[][] board, String word) { if (board == null || word == null || board.length == 0 || word.trim().length() == 0) { return false; } // 初始化全局变量 rows = board.length; cols = board[0].length; visited = new boolean[rows][cols]; this.board = board; this.word = word; // 在每一个点开始深度优先遍历，直到找到为止，找不到返回false for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (dfs(i, j, 0)) { return true; } } } return false; } private boolean dfs(int i, int j, int cur) { // dfs搜索结束条件 if (cur == word.length() - 1) { return word.charAt(cur) == board[i][j]; } // 在符合条件的位置深度优先遍历 if (word.charAt(cur) == board[i][j]) { // 标示该节点被访问到 visited[i][j] = true; for (int k = 0; k < 4; k++) { int newI = i + directed[k][0]; int newJ = j + directed[k][1]; if (isArea(newI, newJ) && !visited[newI][newJ]) {  if (dfs(newI, newJ, cur + 1)) { return true; }  } } // 将该节点dfs搜索过的全部节点状态重置，以防干扰到下一轮的搜索 visited[i][j] = false; } return false; }
 private boolean isArea(int x, int y) { return x >= 0 && x < rows && y >= 0 && y < cols; }}

2.岛屿数量

https://leetcode-cn.com/problems/number-of-islands/

1.思路

和⽆向图求连通分量类似，先对节点进⾏dfs，count + 1，每次dfs到的即标记；

2.代码实现

class Solution { // . x, y + 1 // .x-1, y x, y x + 1, y // . x. y - 1 private int[][] directed = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; private char[][] grid; private boolean[][] visited; private int rows; private int cols; private int res;

 public int numIslands(char[][] grid) { // 求图的连通分量类似，先对节点进行dfs，count + 1，每次dfs到的即标记； if (grid == null || grid.length == 0) { return 0; } this.grid = grid; rows = grid.length; cols = grid[0].length; visited = new boolean[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { // 从第一个遍历到的没被标记过的陆地开始dfs搜索标记 if (grid[i][j] == '1' && !visited[i][j]) { dfs(i, j); res++; } } } return res; }

 private void dfs(int i, int j) { // 访问标记 visited[i][j] = true; // 上下左右进行搜索 for (int k = 0; k < 4; k++) { int newI = i + directed[k][0]; int newJ = j + directed[k][1]; // 是陆地且没被访问过才继续dfs boolean flag = newI >= 0 && newI < rows && newJ >= 0 && newJ < cols && !visited[newI][newJ] && grid[newI][newJ] == '1'; if (flag) { dfs(newI, newJ); } } }}

3.被围绕的区域

https://leetcode-cn.com/problems/surrounded-regions/

1.思路

通过dfs求出边界的且为O的连通分量，把它标记为！，之后再遍历⼀遍board，将O 置为X，将与边相连的连通分量设回O。

2.代码实现

class Solution {  private int[][] directed = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private char[][] board; private int rows; private int cols;
 public void solve(char[][] board) { // 通过dfs求出边界的且为O的连通分量，把它标记为！，之后再遍历一遍board， // 将O置为X，将与边相连的连通分量设回O if (board == null || board.length == 0) { return; } rows = board.length; cols = board[0].length; this.board = board; // 找到边界O节点进行深度优先遍历，将所有与边界O节点连通的O节点设为！ for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { boolean flag = board[i][j] == 'O' && (i == 0 || i == rows - 1 || j == 0 || j == cols - 1); if (flag) { dfs(i, j); } } } // 将O设置为X，将被标示为!的节点设置为O for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } else if (board[i][j] == '!') { board[i][j] = 'O'; } } } }
 private void dfs(int i, int j) { board[i][j] = '!'; // 继续dfs for (int k = 0; k < 4; k++) { int newI = i + directed[k][0]; int newJ = j + directed[k][1]; boolean isArea = newI >= 0 && newI < rows && newJ >= 0 && newJ < cols; if (isArea && board[newI][newJ] == 'O') { dfs(newI, newJ); } } }}

三.模板总结

从上面的3道问题中，我们发现dfs类的问题会有相对固定的答题模板，比如需要先声明一个方向数组用以构造搜索的方向，需要构造访问数组用以储存被遍历过的位置等，这里提取出如下的解题模板：

 // . x, y + 1 // .x-1, y x, y x + 1, y // . x. y - 1 private int[][] directed = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; private char[][] grid; private boolean[][] visited; private int res;

 public int numIslands(char[][] grid) { for (int i = 0; i < grid.length; i++) { dfs(i, j); } return res; }

 private void dfs(int row, int col) { // 访问 visited[row][col] = true; // 上下左右进行搜索 for (int i = 0; i < 4; i++) { int newRow = row + directed[i][0]; int newCol = col + directed[i][1]; // 剪枝 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && marked[newRow][newCol] == false && grid[newRow][newCol] == '1') { dfs(newRow, newCol, rows, cols); } } return; }