首页 > AK F.*ing leetcode 流浪计划之DFS
头像
闪电彬彬
编辑于 2021-06-05 18:42
+ 关注

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

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

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

一、简介

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

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

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

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

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

二、作用

图(树)应用

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

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

比如:

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

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

比如

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

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

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

三、解题步骤

图遍历应用

解题步骤

  • 定义数据
  1. 定义结点数据和孩子数据
  • 具体操作

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

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

Step 4 标记当前结点已遍历

step 5 遍历子结点

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

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

step 7 结束

回溯法(剪枝)应用

适用条件:

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

解题步骤

  • 定义数据
  1. 定义每一层的状态
  2. 定义状态转移操作
  3. 定义基础结束条件
  4. 定义剪枝条件
  • 具体操作

step 1 选择起状态

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

Step 3 判断该状态是否剪枝,是则返回(非剪枝可以不要)

step 4 生成和遍历子状态

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

step 5 结束

记忆化搜索动态规划应用

适用条件:

  1. 所有动态规划问题

解题步骤

  • 定义数据
  1. 定义状态
  2. 定义结束条件
  3. 定义转移方程
  • 具体操作

step 1 选择起状态

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

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

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

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

step 5 结束

四、代码框架

图遍历框架

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

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

回溯法(剪枝)框架

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

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


     // 进行下一层选择
     for child<-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<-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

题目解析

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

定义:

  1. 定义状态,dp[i][j] 表示是以matrix[i][j] 结尾的最长上升路径的长度。
  2. 终止条件:matrix[i][j] 四周没有比自己小的数字, 或i, j 越界了 (肯定有数字的四周是大于等自己的,所以最终肯定会停止)
  3. 转移方程: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
}

六、总结

主要内容:

  1. 深搜算法是一种暴力算法,适用于状态全集规模较小搜索问题。

  2. 作用:图应用主要有1)深度优先遍历结点,2)图连通块相关的一些计算,比如判2点是否连通,有几个连通块。

    回溯法(剪枝),记忆化搜索也是深搜算法的应用。

  3. 解题的基本框架比较固定,关键在于状态的定义,以及状态转移方法的构造。

笔者水平有限,有写得不对或者解释不清楚的地方还望大家指出,我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目(首先AK F.*ing leetcode),给大家准备了一些题目,供大家练习参考。干他F.*ing (Fighting?)。

七、实战训练

代码基础训练题

光说不练假把式,学完了怎么也要实操一下吧,快快动用把刚才那例题A了。

  1. 图深度优先遍历应用 题目链接 https://leetcode-cn.com/problems/number-of-provinces/
  2. 回溯法应用 题目链接 https://leetcode-cn.com/problems/permutations/
  3. 回溯法+剪枝应用 题目链接 https://leetcode-cn.com/problems/combination-sum-ii/
  4. 记忆化搜索应用 题目链接 https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

AK leetcode

leetcode相关题目都在下面了,拿起武器挨个点名呗。

https://leetcode-cn.com/tag/depth-first-search/problemset/ 深度优先遍历

https://leetcode-cn.com/tag/backtracking/problemset/ 回溯(剪枝)算法

https://leetcode-cn.com/tag/memoization/problemset/ 记忆化搜索


以上题目太多,大家适当选择就行,下面还有进阶题目。

大神进阶

hdu

  1. http://acm.hdu.edu.cn/showproblem.php?pid=1010
  2. http://acm.hdu.edu.cn/showproblem.php?pid=1015
  3. http://acm.hdu.edu.cn/showproblem.php?pid=1016
  4. http://acm.hdu.edu.cn/showproblem.php?pid=1045
  5. http://acm.hdu.edu.cn/showproblem.php?pid=1175
  6. http://acm.hdu.edu.cn/showproblem.php?pid=1181
  7. http://acm.hdu.edu.cn/showproblem.php?pid=1258
  8. http://acm.hdu.edu.cn/showproblem.php?pid=1312
  9. http://acm.hdu.edu.cn/showproblem.php?pid=1514
  10. http://acm.hdu.edu.cn/showproblem.php?pid=1515
  11. http://acm.hdu.edu.cn/showproblem.php?pid=1518
  12. http://acm.hdu.edu.cn/showproblem.php?pid=1548
  13. http://acm.hdu.edu.cn/showproblem.php?pid=1627
  14. http://acm.hdu.edu.cn/showproblem.php?pid=1978
  15. http://acm.hdu.edu.cn/showproblem.php?pid=2102
  16. http://acm.hdu.edu.cn/showproblem.php?pid=2181
  17. http://acm.hdu.edu.cn/showproblem.php?pid=2437
  18. http://acm.hdu.edu.cn/showproblem.php?pid=2510
  19. http://acm.hdu.edu.cn/showproblem.php?pid=2553
  20. http://acm.hdu.edu.cn/showproblem.php?pid=3111
  21. http://acm.hdu.edu.cn/showproblem.php?pid=3427
  22. http://acm.hdu.edu.cn/showproblem.php?pid=4607
  23. http://acm.hdu.edu.cn/showproblem.php?pid=4628
  24. http://acm.hdu.edu.cn/showproblem.php?pid=5001
  25. http://acm.hdu.edu.cn/showproblem.php?pid=5319
  26. http://acm.hdu.edu.cn/showproblem.php?pid=5547
  27. http://acm.hdu.edu.cn/showproblem.php?pid=5587
  28. http://acm.hdu.edu.cn/showproblem.php?pid=6468

poj

  1. http://poj.org/problem?id=1088
  2. http://poj.org/problem?id=1101
  3. http://poj.org/problem?id=1179
  4. http://poj.org/problem?id=1321
  5. http://poj.org/problem?id=1390
  6. http://poj.org/problem?id=1564
  7. http://poj.org/problem?id=1664
  8. http://poj.org/problem?id=1753
  9. http://poj.org/problem?id=1979
  10. http://poj.org/problem?id=2386
  11. http://poj.org/problem?id=2488
  12. http://poj.org/problem?id=2531
  13. http://poj.org/problem?id=2676
  14. http://poj.org/problem?id=2907
  15. http://poj.org/problem?id=2908
  16. http://poj.org/problem?id=2965
  17. http://poj.org/problem?id=3009
  18. http://poj.org/problem?id=3186

本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。
</target{></len(isconnected)>

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐