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

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

一、简介

广度优先搜索算法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 图深度优先遍历应用 省份数量

题目链接 力扣

题目大意

有 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
}
/*
[[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/

题目大意

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]
示例 3:

输入:nums = [1]
输出:[[1]]

提示:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

题目解析

可以通过回溯法解决。

按照朴素数学做法,以[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代码

func permute(nums []int) [][]int {
	res := [][]int{}
	vis := make(map[int]bool) // 标记是否已经被选择
	var dfs func(int, []int) 
	dfs = func(i int, arr []int){
		if i==len(nums) { // 选完所有数字产生一组排列
			temp := make([]int, len(nums))
			copy(temp, arr)
			res = append(res, arr)
			return
		}
		
		// 尝试第i位填一个数字
		for _, v:= range nums {
			if vis[v] { // 数字已经被选走了忽略
				continue
			}
			
			vis[v]=true  // 标记已经被选走
			dfs(i+1, append(arr, v))
			vis[v]=false // 释放标记,归还到集合中
		}
	}
	
	dfs(0, nil)
	return res
}

练习3 回溯法+剪枝应用 组合总和 II

题目链接:力扣

题目大意

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

题目解析

  • 对于一个数字来讲就是选取或者不选取,穷举出所有可能依次判断即可
  • 这里要解决的一个问题是相同的数字有可能被多选,举例[1, 1], 子集中会有2个[1] 这种情况是要去重。
  • 注意剪枝

定义:

  1. 定义每一层的状态,当前层待选择的数字是否要选择
  2. 定义状态转移操作,待选数字序号加1
  3. 定义基础结束条件,所有选择的数字加=target 或 所有数字都已经选择完。
  4. 剪枝条件:1)所选择数字加和已经大于target, 2) 所选择数字加和加上后面未选择的数字加和小于target

子集去重思路与优化

基本思路
subSet(dep, sum, selected, left) :
	if sum==target: 
		res.push(selected)
		return
	
	if dep >= len(candidates): return // 所有数字选择完
	if sum > target: return // 剪枝条件1
	if sum+left<target: return // 剪枝条件2
	
	// 不选取当前数字
	subSet(dep+1, sum, selected, left-candidates[dep])
	
	// 选取当前数字
	selected.push(candidates[dep])
	subSet(dep+1, sum+candidates[dep], selected, left-candidates[dep])
	selected.pop()
	return 


优化去重逻辑:
假设 [a,b,c] = [1,1,2]
选取过程如下:
[a], [a,b], [a,b,c], [a,c], [b], [b,c](这里已经重复了), [c]
从上面过程中可以看出,选b的时候前面有一个和b相同的元素还没有被选择过说明这个时候还轮不到b来选。

// 优化后 先对candidates排序
subUniqueSet(dep, sum, selected, left) :
	if sum==target: 
		res.push(selected)
		return
	
	if dep >= len(candidates): return // 所有数字选择完
	if sum > target: return // 剪枝条件1
	if sum+left<target: return // 剪枝条件2
	
	
	// 不选取当前数字
	subUniqueSet(dep+1, sum, selected, left-candidates[dep])
	
	// 选取当前数字
	// 判断是否前面有相同数字没有被选择
	if dep>0 && 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 >= len(candidates){ return} // 所有数字选择完
		if sum > target { return}    // 剪枝条件1
		if sum+left<target{ return }// 剪枝条件2


		// 不选取当前数字
		subUniqueSet(dep+1, sum,left-candidates[dep], selected)

		// 选取当前数字
		// 判断是否前面有相同数字没有被选择
		if dep>0 && 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 记忆化搜索应用 矩阵中的最长递增路径

题目链接:力扣

题目大意

给定一个 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 > 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 < 0 || i >= n || j < 0 || j >= 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 < 0 || newX >= n || newY < 0 || newY >= m { // 越界了
				continue
			}
			if matrix[i][j] <= 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. 图深度优先遍历应用 题目链接 力扣
  2. 回溯法应用 题目链接 力扣
  3. 回溯法+剪枝应用 题目链接 力扣
  4. 记忆化搜索应用 题目链接 力扣

AK leetcode

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

力扣 深度优先遍历

力扣 回溯(剪枝)算法

力扣 记忆化搜索


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

大神进阶

hdu

  1. Problem - 1010
  2. Problem - 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. Problem - 1181
  7. Problem - 1258
  8. Problem - 1312
  9. Problem - 1514
  10. Problem - 1515
  11. Problem - 1518
  12. Problem - 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. Problem - 2181
  17. Problem - 2437
  18. http://acm.hdu.edu.cn/showproblem.php?pid=2510
  19. Problem - 2553
  20. http://acm.hdu.edu.cn/showproblem.php?pid=3111
  21. Problem - 3427
  22. Problem - 4607
  23. Problem - 4628
  24. http://acm.hdu.edu.cn/showproblem.php?pid=5001
  25. Problem - 5319
  26. Problem - 5547
  27. http://acm.hdu.edu.cn/showproblem.php?pid=5587
  28. Problem - 6468

poj

  1. 1088 -- 滑雪
  2. 1101 -- The Game
  3. 1179 -- Polygon
  4. 1321 -- 棋盘问题
  5. 1390 -- Blocks
  6. 1564 -- Sum It Up
  7. 1664 -- 放苹果
  8. 1753 -- Flip Game
  9. 1979 -- Red and Black
  10. 2386 -- Lake Counting
  11. 2488 -- A Knight's Journey
  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

本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。

在这里插入图片描述