闪电彬彬

2021-06-05 18:42 已编辑字节跳动_直播server_高级开发工程师

关注

AK F.*ing leetcode 流浪计划之DFS

字节员工，直播业务长期招人（北京，杭州，上海，深圳），hc巨多，社招，校招，实习都有。

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

广度优先搜索算法BFS（广搜）是图的一种遍历方式，类似于树的层次遍历。

深度优先搜索算法DFS(深搜)是图的一种遍历方式。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

由DFS衍生出来的相关应用算法比较多，主要可以分为图应用、回溯法（遍历所有解）、带剪枝的回溯法（求解最优解或判断是否有解）、记忆化搜索（动态规划递归版本实现）。

DFS和BFS也是一种暴力搜索的算法，通常情况下也很完备，对于整体状态的数量要事先估计。对于带剪枝的回溯算法要充分分析剪枝条件的正确性，以免剪掉一些可行解，导致答案不完备。

由于DFS是基于递归的一个过程，学习DFS算法对于理解递归过程非常有帮助，通过练习掌握递归的常规应用。

二、作用

图（树）应用

深度优先遍历结点
判断图中2点是否连通
查找图的连通块

回溯法应用，该算法大多是用于模拟求解。先把问题拆解成某一个基础操作，在每一层做一个基础操作，直到确定唯一解，然后再逐步回溯。

比如：

全排列生成，一开始有n个数字，从第1个位置到n位置，每个位置选择一个数字，直到数字选完产生一个排列，再继续回溯。
走迷宫，每次都选择一个方向走，直到走不动或离开迷宫，就是生成了一条路线，然后再回溯。
对一堆数字生成子集。对每个数字，进集合或者不进集合，当用完所有数字就形成一个子集，再回溯。
八皇后问题，每行选择一个可以放的位置，直到放完所有行，再回溯。

带剪枝的回溯法，该算法一般用于求解某个问题是否有解或问题的最优解。他与回溯法的区别就是递归的终止条件会更多（普通回溯法的终止条件就是元素都操作完了），使得递归次数大大减少。

比如

求解数组（都是非负数）中的某几个数字之和是否等于目标值，基本思想可以生成所有子集，然后判断子集之和是否等于目标值，可以增加终止条件：如果剩下的数字都加上也无法达到目标值就返回。

记忆化搜索求解动态规划问题

动态规划有2种实现方式，递推和递归求解。递推是自底向上，关键要找到这个底在哪里，有些动态规划问题不容易找到底，所以用递归求解更容易实现。递归求解会存在重复求解，需要引入一个map标记是否已求解过，故名记忆化搜索。

三、解题步骤

图遍历应用

解题步骤

定义数据

定义结点数据和孩子数据

具体操作

step 1 选择一个没有遍历过的点

step 2 判断该结点是否已经遍历，是则转6

Step 4 标记当前结点已遍历

step 5 遍历子结点

        1. 判断子结点是否合法
        2. 转step2

step 6 查看是否还有未遍历结点，有则转1，没有转7

step 7 结束

回溯法（剪枝）应用

适用条件：

整体递归层数不能太多，10多个可以接受。
总体状态数量要控制在百万级别，剪枝的话要看情况，可以扩大到千万甚至更高。

解题步骤

定义数据

定义每一层的状态
定义状态转移操作
定义基础结束条件
定义剪枝条件

具体操作

step 1 选择起状态

step 2 判断该状态是否结束，是则返回

Step 3 判断该状态是否剪枝，是则返回（非剪枝可以不要）

step 4 生成和遍历子状态

           1. 判断子状态是否合法
           2. 转step2

step 5 结束

记忆化搜索动态规划应用

适用条件：

所有动态规划问题

解题步骤

定义数据

定义状态
定义结束条件
定义转移方程

具体操作

step 1 选择起状态

step 2 判断该状态是否结束，是则返回结束值

Step 3 判断该状态是否计算过，是则返回

step 4 根据转移方程计算子状态

转到2
标记本状态计算完成，并保存计算结果

step 5 结束

四、代码框架

图遍历框架

// 图遍历框架
vis // 表示 某状态是否被访问过, 针对有环图的情况需要判断，无环图不用
func DFS(start State)  {
    if vis[start] {return}
    vis[start]&lt;-true
    // 对start 进行一些操作
    visit(start)

    // 遍历子结点
    for child &lt;- start.Children {
        DFS(child)
    }
}

回溯法（剪枝）框架

// 回溯法（剪枝）框架
func DFS(dep int, start State) {
     // 判断当前状态的基本条件
     if isEnd(start) {
             // 得到一个结果进行存储
      do sth ...
             return
     }

     // 剪枝条件判断(非剪枝这步可以不要)
     if isCut(start) {return}


     // 进行下一层选择
     for child&lt;-start.Children {
             DFS(dep+1, child)
     }
}

记忆化搜索框架

// 记忆化搜索框架
vis // 存储是否计算过
val // 计算结果值
func dp(start State)  {
     // 判断当前是否结束条件
     if isEnd(start) {return 结果 }

     // 判断是否计算过
     if vis[start] {val[start]}
     vis[start]=true

     // 进行子状态转移
     for child&lt;-start.Children {
         val = dp(child)
         // 对val进行一些操作
     }

     return val[start]
}

Dfs 应用很广，具体每种应该只能大致分成几个部分，没有固定的写法。具体需要做题来感受。

五、牛刀小试

练习1 图深度优先遍历应用省份数量

题目链接 https://leetcode-cn.com/problems/number-of-provinces/

题目大意

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j

题目解析

题目中给出图是矩阵表示法，先把图转化成链表表示法。

按照题意，一个省就是图中的一个连通块。

可以通过DFS算法去查询一个连通块。

AC代码

func getLinks(isConnected [][]int) [][]int {
    links := make([][]int, len(isConnected))
    for i, row := range isConnected {
        for j, v := range row {
            if i == j { // 排除自己
                continue
            }

            if v == 0 {
                continue
            }
            links[i] = append(links[i], j)
        }
    }
    return links
}

func findCircleNum(isConnected [][]int) int {
    links := getLinks(isConnected)

    sum := 0
    vis := make(map[int]bool)

    var dfs func (int) 
    dfs = func (i int)  {
        if vis[i] { // 已经访问过了，直接返回
            return 
        }
        vis[i]=true

        for _, child :=range links[i] {
            dfs(child)
        }
    }

    for i:=0;i<len(isconnected) ;i++ { if vis[i] 访问过了 continue } 没访问过 sum++ dfs(i) 把与i在同一省的城市都遍历 return sum="=target:" * [[1,1,0],[1,1,0],[0,0,1]] [[1,0,0],[0,1,0],[0,0,1]] [[1]] ~~~ ## 练习2 回溯法应用[全排列](https: leetcode-cn.com problems permutations ) 题目链接：https: ### 题目大意 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入：nums="[1]" 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 2： 输出：[[0,1],[1,0]] 3： 输出：[[1]] 提示： 1 <="10" -10 中的所有整数 互不相同 题目解析 可以通过回溯法解决。 按照朴素数学做法，以[1,2,3]为例 先选择第1位，1 再从剩下中选择第二位，形成[1，2]， [1，3] 再从剩下中选择第三位，形成[1, 2, 3], [1, 3, 2] 同理第1位选择2，最终产生出 [2，1，3]，[2，3，1] 第1位选择3省略。 根据以上模拟可以发现， 每次操作都是在某一位上选择一个没被用过的数字。 定义： 1. 定义每一层的状态，当前第几位数字待选 2. 定义状态转移操作，待选数字序号加1 3. 定义基础结束条件，所有集合数字已经用完 ac代码 ~~~go func permute(nums []int) [][]int res : vis 标记是否已经被选择 var dfs="func(i" func(int, int, arr []int){ i="=len(nums)" 选完所有数字产生一组排列 temp len(nums)) copy(temp, arr) 尝试第i位填一个数字 for _, v:="range" vis[v]="false" 数字已经被选走了忽略 标记已经被选走 dfs(i+1, append(arr, v)) 释放标记，归还到集合中 dfs(0, nil) 练习3 回溯法+剪枝应用 [组合总和 ii](https: combination-sum-ii 给定一个数组 candidates="[2,5,2,1,2]," 和一个目标数 target="5," ，找出 中所有可以使数字和为 的组合。 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 1: 输入: 所求解集为: [ 7], 5], [2, 6], 1, 6] ] 2: [1,2,2], [5] - 对于一个数字来讲就是选取或者不选取，穷举出所有可能依次判断即可 这里要解决的一个问题是相同的数字有可能被多选，举例[1, 1], 子集中会有2个[1] 这种情况是要去重。 注意剪枝 定义每一层的状态，当前层待选择的数字是否要选择 定义基础结束条件，所有选择的数字加="target" 或 所有数字都已经选择完。 4. 剪枝条件：1）所选择数字加和已经大于target, 2) 所选择数字加和加上后面未选择的数字加和小于target 子集去重思路与优化 基本思路 subset(dep, sum, selected, left) res.push(selected) dep>= len(candidates): return // 所有数字选择完
    if sum &gt; target: return // 剪枝条件1
    if sum+left<target: return 剪枝条件2 不选取当前数字 subset(dep+1, sum, selected, left-candidates[dep]) 选取当前数字 selected.push(candidates[dep]) sum+candidates[dep], selected.pop() 优化去重逻辑： 假设 [a,b,c]="[1,1,2]" 选取过程如下： [a], [a，b], [a，b，c], [a,c], [b], [b,c](这里已经重复了), [c] 从上面过程中可以看出，选b的时候前面有一个和b相同的元素还没有被选择过说明这个时候还轮不到b来选。 优化后 先对candidates排序 subuniqueset(dep, left) : if sum="=target:" res.push(selected) dep>= len(candidates): return // 所有数字选择完
    if sum &gt; target: return // 剪枝条件1
    if sum+left<target: return 剪枝条件2 不选取当前数字 subuniqueset(dep+1, sum, selected, left-candidates[dep]) 选取当前数字 判断是否前面有相同数字没有被选择 if dep>0 &amp;&amp; candidates[dep-1]==candidates[dep]: return
    curnum = candidates[dep]
    selected.push(curnum)
    candidates[dep]=-1 //标记被选中了
    subUniqueSet(dep+1, sum+curnum, selected, left-curnum)
    candidates[dep]=curnum //恢复值
    selected.pop()

    return

AC代码

先对candidates排序

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates) // 要先排序。
    res := [][]int{}
    left :=0
    for _, v:= range candidates {
        left += v
    }
    // 优化后 先对candidates排序
    var subUniqueSet func(int, int,  int,[]int)
    subUniqueSet = func(dep, sum, left int, selected []int) {
        if sum==target {
            temp := make([]int , len(selected))
            copy(temp, selected)
            res = append(res, temp)
            return // 后面加正数，肯定要大于target 直接返回
        }

        if dep &gt;= len(candidates){ return} // 所有数字选择完
        if sum &gt; target { return}    // 剪枝条件1
        if sum+left<target{ return } 剪枝条件2 不选取当前数字 subuniqueset(dep+1, sum,left-candidates[dep], selected) 选取当前数字 判断是否前面有相同数字没有被选择 if dep>0 &amp;&amp; candidates[dep-1]==candidates[dep] { return }
        curnum := candidates[dep]
        candidates[dep] = -1 //标记被选中了
        subUniqueSet(dep+1, sum+curnum, left-curnum, append(selected, curnum))
        candidates[dep]= curnum //恢复值
    }
    subUniqueSet(0, 0, left, nil)

    return res
}

练习4 记忆化搜索应用矩阵中的最长递增路径

题目链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

题目大意

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：

输入：matrix = [[1]]
输出：1

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

题目解析

此题类似于最长上升子序列。使用动态规划解决。

定义：

定义状态，dp[i][j] 表示是以matrix[i][j] 结尾的最长上升路径的长度。
终止条件：matrix[i][j] 四周没有比自己小的数字, 或i, j 越界了 (肯定有数字的四周是大于等自己的，所以最终肯定会停止)
转移方程：dp[i][j] = 1+ max(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]) (matrix[i][j] >matrix[i-1][j],matrix[i+1][j], matrix[i][j-1], matrix[i][j+1])

AC代码

func max(a, b int) int {
    if a &gt; b {
        return a
    }
    return b
}

var dir = [][]int{
    {0, -1}, {0, 1}, {1, 0}, {-1, 0},
}

func longestIncreasingPath(matrix [][]int) int {
    vis := make(map[int]bool)
    dp := make(map[int]int)
    n, m := len(matrix), len(matrix[0])

    var dfs func(int, int) int
    dfs = func(i, j int) int {
        if i &lt; 0 || i &gt;= n || j &lt; 0 || j &gt;= m { // 越界了，默认0
            return 0
        }
        ind := i*1000 + j // 对矩阵一维化编码
        if vis[ind] {
            return dp[ind]
        } // 已经计算过了，直接返回
        vis[ind] = true //标记已经计算
        dp[ind] = 0
        // 检查4个方法取最大值
        //dp[i][j] = 1+ max(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1])
        for _, d := range dir {
            newX, newY := i+d[0], j+d[1]
            if newX &lt; 0 || newX &gt;= n || newY &lt; 0 || newY &gt;= m { // 越界了
                continue
            }
            if matrix[i][j] &lt;= matrix[newX][newY] { // 不能接在自己后面
                continue
            }
            dp[ind] = max(dp[ind], dfs(newX, newY)) //更新最优值
        }

        // 加上自己
        dp[ind] = dp[ind] + 1

        return dp[ind]
    }

    best := 0
    // 检查 每个dp(i,j) 取最大值
    for i, row := range matrix {
        for j := range row {
            //fmt.Printf("%d, ", dfs(i, j))
            best = max(best, dfs(i, j))
        }
        //fmt.Println()
    }

    return best
}