各种搜索
# 解释
深度优先搜索和广度优先搜索是两种最常见的优先搜索方法，它们被广泛地运用在图和树等 结构中进行搜索。
# 深度优先搜索
深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍 历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言， 由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。 考虑如下一颗简单的树。我们从 1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点， 那么按照优先向着“深”的方向前进的策略，假如我们使用递归实现，我们的遍历过程为 1（起 始节点）->2（遍历更深一层的左子节点）->4（遍历更深一层的左子节点）->2（无子节点，返回 父结点）->1（子节点均已完成遍历，返回父结点）->3（遍历更深一层的右子节点）->1（无子节 点，返回父结点）-> 结束程序（子节点均已完成遍历）。如果我们使用栈实现，我们的栈顶元素 的变化过程为 1->2->4->3。
深度优先搜索也可以用来检测环路：记录每个遍历过的节点的父节点，若一个节点被再次遍 历且父节点不同，则说明有环。我们也可以用之后会讲到的拓扑排序判断是否有环路，若最后存 在入度不为零的点，则说明有环。 有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这 种做法叫做状态记录或记忆化（memoization）。
# 岛屿最大面积
695. 岛屿的最大面积 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
思路一：使用栈，因为这个题目其实就是要我们遍历整个二维数组，比如我们遇到一个点，那么我们就可以把这个点放入栈中，然后把这点置为空。然后我们对当前点进行上下左右判断，如果为1，就把值放入栈中，并把这个点置为0。我们一直遍历直到栈为空为止，这里我们用到了一个技巧，对于四个方向的遍历，我们可以创造一个数组[-1,0,1,0,-1]每相邻两个就是上下左右这四个方向
var direction = []int{-1, 0, 1, 0, -1}
// 使用栈的写法
func maxAreaOfIsland(grid [][]int) int {
m:=len(grid)
if m==0 {
return 0
}
n:= len(grid[0])
area, localArea :=0,0
var x,y int
// 遍历数组
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
// 如果当前节点为1，我们就可以进行遍历了
if grid[i][j] ==1 {
localArea = 1
grid[i][j] = 0
// 自己定义一个栈
island:=Stack{}
// 把当前值放入栈中
island.Push([]int{i,j})
// 遍历直到栈为空位置
for !island.Empty() {
// 获取当前栈顶的值
r,c:=island.Pop()
// 我们分别依次判断当前值的上下左右是否为空
for k := 0; k < 4; k++ {
// 这里我们使用了一个小技巧，每相邻两位即为上下左右四个方向之一
x =r+ direction[k];y = c+direction[k+1]
// 这里我们还需要判断一下x，y的范围是否在矩形内，以免越界
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
// 这里我们就把grid置为0，然后把这个点放入栈中
grid[x][y] = 0
localArea++
island.Push([]int{x,y})
}
}
}
if localArea > area {
area= localArea
}
}
}
}
return area
}
// 自己定义一个简单的栈
type Stack struct {
i int
data [][]int
}
func (s *Stack) Push(k []int) {
s.data = append(s.data, k)
s.i = len(s.data)-1
}
func (s *Stack) Pop() (x int,y int) {
x = s.data[s.i][0]
y = s.data[s.i][1]
s.i--
return
}
func (s *Stack) Empty() bool {
return s.i < 0
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
使用递归的方法也很简单，我简单看了一下别人的代码，然后把辅助函数写出来了哈哈
原理很简单，我们同样遍历整个矩阵，如果当前节点的值不为0，那么我们就可以对当前节点进行dfs操作，获取当前这个节点的区域值。然后dfs的代码也很简单，直接使用我们上个的栈的方法，我们同样对当前点的上下左右进行递归操作，最后就可以得出结果，关键部分在于理解dfs函数
var direction = []int{-1, 0, 1, 0, -1}
// 使用递归的写法
func maxAreaOfIsland(grid [][]int) int {
// 当grid大小为0时，我们就退出循环
if len(grid)==0 || len(grid[0])==0 {
return 0
}
// 当前最大区域为0
maxArea:=0
// 我们开始遍历整个grid数组
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[i]); j++ {
// 当当前这个点为1的时候，我们就获取一下当前的区域信息
if grid[i][j] == 1 {
// 使用dfs来获取当前的地域信息
area:=dfs(grid,i,j)
// 更新最大的区域
if area > maxArea {
maxArea = area
}
}
}
}
return maxArea
}
// 使用一个辅函数，这个就是我们的关键部分了
func dfs(grid [][]int,r int,c int) int {
// 因为是递归函数，所以我们需要设置一个递归的条件
if grid[r][c] == 0 {
return 0
}
// 如果r，c所在的值不为0，那么当前区域值就为1，同时把当前区域值置为0
area:= 1
var x,y int
grid[r][c] = 0
// 对当前位置进行遍历，判断上下左右四个方向
for k := 0; k < 4; k++ {
// 这里我们通过direction数组来实现获取当前位置的上下左右
x=direction[k]+r
y=direction[k+1]+c
// 确保这个值在矩阵的范围内
if x>=0 && y>=0 && x<len(grid) && y<len(grid[0]) {
// 注意这我们不需要判断当前位置是否为0，因为dfs会自己计算，如果为0就会返回0
area+=dfs(grid,x,y)
}
}
return area
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 省份的数量
547. 省份数量 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
思路：这个我一开始就想不到。。但是后面看了一遍代码，就大概知道其原理了。我们如何判断i城市和j城市是否相连呢？直接判断arr[i][j]是否为1即可，知道这点后我们做起来就方便多了
首先我们可以创建一个和城市大小一样的数组，然后我们可以通过设置一个标志位，如果当前城市访问了那么我们就不管，如果我们没访问，我们就遍历这个城市，把所有相连的城市全部连接起来
func findCircleNum(isConnected [][]int) int {
// 首先我们获取城市的数量
n:=len(isConnected)
// count表示省份的数量
count:=0
// 我们创建一个visited数组，这个用于表示当前城市是否访问过了
visited:=make([]bool,n)
// 我们遍历这些城市
for i:=0;i<n;i++{
// 选择一个没有访问过得城市，并进行深度优先搜索
if !visited[i] {
// 进行深度优先搜索，我们传入i的位置
dfs(isConnected,i,visited)
// 没有访问过得一定是一个城市
count++
}
}
return count
}
// 使用一个辅助函数，这个就是我们的关键部分了
func dfs(area [][]int,i int,visited []bool) {
// 表示当前城市已经被我们访问了
visited[i] = true
// 我们继续遍历，找到与i城市连接的点
for k:=0;k< len(area);k++ {
// 如果k城市与i城市是连接的那么就为1，同时我们还要确保当前城市没有被访问
if area[i][k] ==1 && !visited[k] {
// 这里我们获取与k城市相连的点
dfs(area,k,visited)
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 太平洋，大西洋流水问题
417. 太平洋大西洋水流问题 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
这个题目其实可以使用逆向的方法来做，我们可以大洋那边出发，水往上流，因为大洋是两条线的，所以我们需计算这两条线上得每一个点所能到达的区域，最后我们就可以得出两个数组（分别代表太平洋和大西洋能流经的位置）如果这两个点都可以满足的话，那么这个点就是我们的答案
var direction = []int{-1, 0, 1, 0, -1}
func pacificAtlantic(matrix [][]int) [][]int {
// 先判断题目是否有解
if len(matrix) ==0 || len(matrix[0]) ==0 {
return [][]int{}
}
var ans [][]int
// 获取矩阵的大小
m,n:=len(matrix),len(matrix[0])
// 因为有两个大洋，我们这里创建两个数组来分别表示两个大洋各自可以到达的位置
reachP:=make([][]bool,m)
reachA:=make([][]bool,m)
// 因为make只能初始化一维，我们这里还需要遍历来初始二维值
for i := 0; i < m; i++ {
reachP[i]=make([]bool,n)
reachA[i]=make([]bool,n)
}
// 下面我们就分别计算两个大洋可以到达的点
// 首先是y轴，也就是一维
for i := 0; i < m; i++ {
// 这里我们的reachP是左边的线，我们计算这条线上每个点能到达的位置
// 这个n-1其实就是右边的线了
// 因为我们左边是P右边为A
dfs(matrix,reachP,i,0)
dfs(matrix,reachA,i,n-1)
}
for i := 0; i < n; i++ {
// 同样我们这里计算上边的线和下边的线能到达的位置
dfs(matrix,reachP,0,i)
dfs(matrix,reachA,m-1,i)
}
// 最后我们遍历整个数组，来判断那个点P可以到达，A也可以到达
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if reachP[i][j] && reachA[i][j] {
ans = append(ans,[]int{i,j})
}
}
}
return ans
}
// 辅助函数，用于计算能到达的位置
func dfs(matrix [][]int,reach [][]bool,r int,c int) {
// 如果已经统计了，我们就直接退出
if reach[r][c] {
return
}
// reach设置为true
reach[r][c] = true
var x,y int
// 这里我们从四个方向开始遍历
for i := 0; i < 4; i++ {
x = r+direction[i]
y= c+direction[i+1]
// 只要这上下左右四个方向大于当前点，我们的大洋就可以逆流而上
if x >= 0 && y >= 0 && x < len(matrix) && y < len(matrix[0]) && matrix[r][c] <= matrix[x][y] {
// 可以到达的点再次计算
dfs(matrix,reach,x,y)
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# 回溯法
回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状 态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。 顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及 其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态 还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存 状态。在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节 点] 的步骤，只是多了回溯的步骤，变成了 [修改当前节点状态]→[递归子节点]→**[回改当前节点 状态]**。 没有接触过回溯法的读者可能会不明白我在讲什么，这也完全正常，希望以下几道题可以让 您理解回溯法。如果还是不明白，可以记住两个小诀窍，一是按引用传状态，二是所有的状态修改在递归完成后回改。 回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标 记，比如矩阵里搜字符串。
# 全排列
思路：我们如何输出所有的排列方式呢？对于每一个当前位置i，我们只需要对后面每一位和当前位进行替换，替换完后我们在处理i+1位。
这里回溯体现在 我们进行递归前，先替换，递归完后，我们再换回来，进行下一轮替换
func permute(nums []int) [][]int {
ans:=make([][]int,0)
// 直接调用辅助函数来获取值即可
backtracking(nums,0,&ans)
return ans
}
// 注意这里为了能传递值，我们必须使用指针
func backtracking(nums []int, level int, ans *[][]int) {
// 当我们的level为nums时，就说明已经到最后一位了
if level == len(nums) -1 {
// 因为nums是个指针，我们必须使用临时变量拷贝值，要不然会报错
tmp:=make([]int,len(nums))
copy(tmp,nums)
// 我们直接把nums添加到结果里就行了
*ans = append(*ans, tmp)
return
}
// 这里就是关键部代码了
for i := level; i < len(nums); i++ {
// 这里其实就是i和当前位置换一下值（这个i是不断递增的）
nums[i],nums[level] = nums[level],nums[i]
// 下面这里就是进行替换和判断
backtracking(nums,level+1,ans)
// 替换回去，进行下一轮交换
nums[i],nums[level] = nums[level],nums[i]
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 组合
77. 组合 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
这题目我一开始没思路，后面照着敲了一遍代码后，大概懂了，关键部分就是在于回溯部分，因为我们要计算k个数组合，所以我们可以使用count来表示组合的数的大小。这里拿最简单的两个数字来比较，首先第一个数我们会遍历从1到n（pos表示从哪里开始）。已知第一个数为i的情况下，我们会进行递归计算第二个数，第二个数会从i+1开始遍历到n。获取到数后，我们就把count置为0，继续开始下一个组合计算
func combine(n int, k int) [][]int {
// ans表示结果，comb表示当前的组合，count表示组合的位数
ans:=make([][]int,0)
comb:=make([]int,k)
count:=0
// 进行回溯获取结果，题目是从1到n所以我们的pos一开始为1
getOrder(&ans,comb,count,1,n,k)
return ans
}
func getOrder(ans *[][]int,comb []int,count int,pos int,n int,k int) {
// 当count等于k的时候，我们就可以把答案加到结果里去了
if count == k {
tmp:=make([]int,k)
copy(tmp,comb)
*ans = append(*ans,tmp)
return
}
// 因为题目是1到n，所以可以为n，然后我们从pos开始进行计算
for i:=pos;i<=n;i++{
// count表示当前组合的数量,我们把当前的位置放入数组中
comb[count] = i
count++
// 这里我们进行计算获取ans结果
// 这个地方可能难以理解，为什么我们这里可以实现所有组合呢
// 就拿最简单的两个来说，第一个位置我们可以取 pos -> n
// 第二个位置同样会执行这个递归 这里会取 pos+1 -> n
getOrder(ans,comb,count,i+1,n,k)
count-- // 回溯，返回上一次状态
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 单词搜索（待做）
79. 单词搜索 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# N皇后问题（待做）
51. N 皇后 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
# 广度优先搜索
广度优先搜索（breadth-first search，BFS）不同与深度优先搜索，它是一层层进行遍历的，因 此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时 按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。
考虑如下一颗简单的树。我们从 1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点， 那么按照优先向着“广”的方向前进的策略，队列顶端的元素变化过程为 [1]->[2->3]->[4]，其中 方括号代表每一层的元素。
这里要注意，深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否 能达到另一个节点。因为深度优先搜索可以利用递归快速实现，很多人会习惯使用深度优先搜索 刷此类题目。实际软件工程中，笔者很少见到递归的写法，因为一方面难以理解，另一方面可能 产生栈溢出的情况；而用栈实现的深度优先搜索和用队列实现的广度优先搜索在写法上并没有太 大差异，因此使用哪一种搜索方式需要根据实际的功能需求来判断。
# 最短的桥（待做）
934. 最短的桥 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
