搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 非典型开发者 > BAT手撕算法题·深度优先遍历

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

非典型开发者 2020-07-07


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




一.什么是深度优先遍历

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

1.DFS和回溯的区别

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

2.DFSBFS的区别

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.思路
和⽆向图求连通分量类似,先对节点进⾏dfscount + 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,将置为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; }

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《BAT手撕算法题·深度优先遍历》的版权归原作者「非典型开发者」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注非典型开发者微信公众号

非典型开发者微信公众号:DO-JAVA

非典型开发者

手机扫描上方二维码即可关注非典型开发者微信公众号

非典型开发者最新文章

精品公众号随机推荐