ShowDocs
搜索文章Ctrl K

外观

← 返回LeetCode列表
实践案例

LeetCode Go · 并查集（1） ​

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

128. 最长连续序列 ​

中等2 种解法

标签：并查集、数组、哈希表

题目、示例与约束

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

 

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

输入：nums = [1,0,1,2]
输出：3

 

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
方法一：哈希表 · Go 实现

思考

排序后扫连续段是 O ( n log ⁡ n ) ，题目要求 O ( n ) 。 n ≤ 10 5 。放入哈希集合后，从每个尚未删除的 x 向右延伸，直到断掉，并把这段长度记在起点上，供更早的起点拼接。每个数进出集合一次。

我们可以用一个哈希表 s 存储数组中所有的元素，用一个变量 ans 记录最长连续序列的长度，用一个哈希表 d 记录每个元素 x 所在的连续序列的长度。

接下来，我们遍历数组中每个元素 x ，用一个临时变量 y 记录当前连续序列的最大值，初始时 y = x 。然后，我们不断尝试匹配 y + 1 , y + 2 , y + 3 , … ，直到匹配不到为止，过程中将匹配到的元素从哈希表 s 中移除。那么，当前元素 x 所在的连续序列的长度即为 d [ x ] = d [ y ] + y − x ，然后更新答案 ans = max ( ans , d [ x ] ) 。

遍历结束后，返回答案 ans 即可。

时间复杂度 O ( n ) ，空间复杂度 O ( n ) 。其中 n 是数组 nums 的长度。

go
func longestConsecutive(nums []int) (ans int) {
	s := map[int]bool{}
	for _, x := range nums {
		s[x] = true
	}
	d := map[int]int{}
	for _, x := range nums {
		y := x
		for s[y] {
			delete(s, y)
			y++
		}
		d[x] = d[y] + y - x
		ans = max(ans, d[x])
	}
	return
}
方法二：哈希表（优化） · Go 实现

思考

方法一额外用哈希表记下每段长度以便拼接。若只从「 x − 1 不在集合中」的位置开始向右数，则 x 一定是某段起点，不必再保存 d 。实现更短，仍保证每个数被访问常数次。

与方法一类似，我们用一个哈希表 s 存储数组中所有的元素，用一个变量 ans 记录最长连续序列的长度。但是，我们不再使用哈希表 d 记录每个元素 x 所在的连续序列的长度，在遍历的过程中，跳过那些 x − 1 也在哈希表 s 中的元素，如果 x − 1 在哈希表 s 中，那么 x 一定不是连续序列的起点，因此我们可以直接跳过 x 。

时间复杂度 O ( n ) ，空间复杂度 O ( n ) 。其中 n 是数组 nums 的长度。

go
func longestConsecutive(nums []int) (ans int) {
	s := map[int]bool{}
	for _, x := range nums {
		s[x] = true
	}
	for x, _ := range s {
		if !s[x-1] {
			y := x + 1
			for s[y] {
				y++
			}
			ans = max(ans, y-x)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

130. 被围绕的区域 ​

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：

  • 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
  • 区域：连接所有 'O' 的单元格来形成一个区域。
  • 围绕：如果一个区域中的所有 'O' 单元格都不在棋盘的边缘，则该区域被包围。这样的区域 完全 被 'X' 单元格包围。

通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。

 

示例 1：

输入：board = [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]

输出：[['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]

解释：

在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。

示例 2：

输入：board = [['X']]

输出：[['X']]

 

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 'X' 或 'O'
方法一：DFS · Go 实现

思考

被包围的 'O' 要改成 'X'，与边界连通的 'O' 必须保留。 m , n ≤ 200 。从内部出发判断「是否被围住」要处理整片连通块，且边界情况容易漏。

与其找被围住的，不如标记与边界相连的：从四条边上的 'O' 做 DFS，能走到的都先改成占位，其余 'O' 一律变成 'X'，占位再改回 'O'。

我们可以从矩阵的边界开始，将矩阵边界上的每个 O 作为起始点，开始进行深度优先搜索。将搜索到的 O 全部替换成 .。

然后我们再遍历这个矩阵，对于每个位置：

  • 如果是 .，则替换成 O；
  • 否则如果是 O，则替换成 X。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别是矩阵的行数和列数。

go
func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j int)
	dfs = func(i, j int) {
		if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O' {
			return
		}
		board[i][j] = '.'
		for k := 0; k < 4; k++ {
			dfs(i+dirs[k], j+dirs[k+1])
		}
	}
	for i := 0; i < m; i++ {
		dfs(i, 0)
		dfs(i, n-1)
	}
	for j := 0; j < n; j++ {
		dfs(0, j)
		dfs(m-1, j)
	}
	for i, row := range board {
		for j, c := range row {
			if c == '.' {
				board[i][j] = 'O'
			} else if c == 'O' {
				board[i][j] = 'X'
			}
		}
	}
}
方法二：并查集 · Go 实现

思考

方法一用 DFS 染色区分「与边界连通」。并查集把相邻 'O' 连成块，并另设一个超级节点连上所有边界 'O'。最后不与超级节点同根的 'O' 即被包围。避免递归栈，连通关系更直观。

我们也可以使用并查集，将矩阵边界上的每个 O 与一个超级节点 m × n 相连，将矩阵中的每个 O 与其上下左右的 O 相连。

然后我们遍历这个矩阵，对于每个位置，如果是 O，并且其与超级节点不相连，则将其替换成 X。

时间复杂度 O ( m × n × α ( m × n ) ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别是矩阵的行数和列数， α 是阿克曼函数的反函数。

go
func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	p := make([]int, m*n+1)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'O' {
				if i == 0 || i == m-1 || j == 0 || j == n-1 {
					p[find(i*n+j)] = find(m * n)
				} else {
					for k := 0; k < 4; k++ {
						x, y := i+dirs[k], j+dirs[k+1]
						if board[x][y] == 'O' {
							p[find(x*n+y)] = find(i*n + j)
						}
					}
				}
			}
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'O' && find(i*n+j) != find(m*n) {
				board[i][j] = 'X'
			}
		}
	}
}

力扣原题 · Doocs 题解来源

200. 岛屿数量 ​

中等4 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

 

示例 1：

输入：grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
]
输出：1

示例 2：

输入：grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
输出：3

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'
方法一：DFS · Go 实现

思考

若将网格中每个值为 1 的格子单独计为一座岛，则四连通的陆地会被重复计数。 m , n ≤ 300 ，整图遍历可行，但须在同一次搜索中把同一连通块全部消掉。

注意到上下左右相邻的陆地构成一个连通分量，从任一尚未访问的陆地出发即可覆盖整座岛。为此扫描每个格子，遇到 1 便启动 DFS，沿途把陆地改写为 0 ，每启动一次搜索将答案加一。

我们可以使用深度优先搜索（DFS）来遍历每个岛屿。遍历网格中的每个单元格 ( i , j ) ，如果该单元格的值为 '1'，则说明我们找到了一个新的岛屿。我们可以从该单元格开始进行 DFS，将与之相连的所有陆地单元格的值都标记为 '0'，以避免重复计数。每次找到一个新的岛屿时，我们将岛屿数量加 1。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别为网格的行数和列数。

go
func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	var dfs func(i, j int)
	dfs = func(i, j int) {
		grid[i][j] = '0'
		dirs := []int{-1, 0, 1, 0, -1}
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
				dfs(x, y)
			}
		}
	}
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				dfs(i, j)
				ans++
			}
		}
	}
	return ans
}
方法二：BFS · Go 实现

思考

方法一已经用显式栈按连通分量抹掉陆地。同一四连通定义下，也可以用队列按层扩展邻接陆地，同样一次抹掉一座岛。

扫描顺序与方法一相同，空间仍由队列规模决定。

我们也可以使用广度优先搜索（BFS）来遍历每个岛屿。遍历网格中的每个单元格 ( i , j ) ，如果该单元格的值为 '1'，则说明我们找到了一个新的岛屿。我们可以从该单元格开始进行 BFS，将与之相连的所有陆地单元格的值都标记为 '0'，以避免重复计数。每次找到一个新的岛屿时，我们将岛屿数量加 1。

BFS 的具体过程如下：

  1. 将起始单元格 ( i , j ) 入队，并将其值标记为 '0'。
  2. 当队列不为空时，执行以下操作：
    • 出队一个单元格 p 。
    • 遍历 p 的四个相邻单元格 ( x , y ) ，如果 ( x , y ) 在网格范围内且值为 '1'，则将其入队并将其值标记为 '0'。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别为网格的行数和列数。

go
func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	bfs := func(i, j int) {
		grid[i][j] = '0'
		q := [][]int{[]int{i, j}}
		dirs := []int{-1, 0, 1, 0, -1}
		for len(q) > 0 {
			p := q[0]
			q = q[1:]
			for k := 0; k < 4; k++ {
				x, y := p[0]+dirs[k], p[1]+dirs[k+1]
				if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
					q = append(q, []int{x, y})
					grid[x][y] = '0'
				}
			}
		}
	}
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				bfs(i, j)
				ans++
			}
		}
	}
	return ans
}
方法三： 并查集 · Go 实现

思考

若希望把“相邻即同一座岛”显式建成集合，则可将每块陆地视作并查集结点，与四邻中的陆地合并。

扫描结束后，岛屿数等于连通分量个数。合并与查询均可在近似线性时间内完成，空间仍为网格规模。

我们可以使用并查集（Union-Find）来解决这个问题。遍历网格中的每个单元格 ( i , j ) ，如果该单元格的值为 '1'，则将其与相邻的陆地单元格进行合并。最后，我们统计并查集中不同根节点的数量，即为岛屿的数量。

时间复杂度 O ( m × n × log ⁡ ( m × n ) ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别为网格的行数和列数。

go
func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	p := make([]int, m*n)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	dirs := []int{1, 0, 1}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				for k := 0; k < 2; k++ {
					x, y := i+dirs[k], j+dirs[k+1]
					if x < m && y < n && grid[x][y] == '1' {
						p[find(x*n+y)] = find(i*n + j)
					}
				}
			}
		}
	}
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' && i*n+j == find(i*n+j) {
				ans++
			}
		}
	}
	return ans
}
方法四：显式栈 · Go 实现

思考

若将每个值为 1 的格子单独计为一座岛，四连通的陆地会被重复计数。 m , n ≤ 300 ，一次扫描即可，但同一连通块必须在一次搜索里全部改成 0 。

从一块陆地递归走向下一个邻居时，一条 1000 格的蛇形岛就会超出递归上限，而 300 × 300 的网格容得下这条蛇。

抹掉一座岛不需要递归返回值，只需要把四连通的 1 改成 0 。

因此遇到 1 就把它压入显式栈。弹出后把四个方向上仍为 1 的邻居标成 0 并入栈，每启动一次搜索将答案加一。

扫描每个格子，遇到 '1' 就用显式栈淹没整座岛，沿途把陆地改成 '0'，并将答案加 1 。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别为网格的行数和列数。

go
func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	dirs := []int{-1, 0, 1, 0, -1}
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] != '1' {
				continue
			}
			grid[i][j] = '0'
			stk := [][2]int{{i, j}}
			for len(stk) > 0 {
				cur := stk[len(stk)-1]
				stk = stk[:len(stk)-1]
				for k := 0; k < 4; k++ {
					x, y := cur[0]+dirs[k], cur[1]+dirs[k+1]
					if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
						grid[x][y] = '0'
						stk = append(stk, [2]int{x, y})
					}
				}
			}
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

261. 以图判树 🔒 ​

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、图

题目、示例与约束

给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。

如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。

 

示例 1：

输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
输出: true

示例 2:

输入: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
输出: false

 

提示：

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • 不存在自循环或重复的边
方法一：并查集 · Go 实现

思考

无向图是树当且仅当连通且无环，边数必为 n − 1 。并查集在加边时若两端已同属一个集合则成环。

每合并一次连通分量减一，全部边处理完后分量应为 1 。

判断是否是树，需要满足以下两个条件：

  1. 边的数量等于节点数减一；
  2. 不存在环。

我们可以使用并查集来判断是否存在环。遍历边，如果两个节点已经在同一个集合中，说明存在环。否则，我们将两个节点合并到同一个集合中。然后将连通分量的数量减一，最后判断连通分量的数量是否为 1 。

时间复杂度 O ( n × log ⁡ n ) ，空间复杂度 O ( n ) 。其中 n 是节点数。

go
func validTree(n int, edges [][]int) bool {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, e := range edges {
		pa, pb := find(e[0]), find(e[1])
		if pa == pb {
			return false
		}
		p[pa] = pb
		n--
	}
	return n == 1
}
方法二：DFS · Go 实现

思考

并查集按边检测环。也可先要求边数为 n − 1 ，再从 0 做 DFS，访问结点数等于 n 则连通且无额外边。

我们也可以使用深度优先搜索来判断是否存在环。我们可以使用一个数组 v i s 来记录访问过的节点，搜索时，我们先将节点标记为已访问，然后遍历与该节点相邻的节点，如果相邻节点已经访问过，则跳过，否则递归访问相邻节点。最后，我们判断是否所有节点都被访问过，如果有未访问过的节点，说明无法构成树，返回 false。

时间复杂度 O ( n ) ，空间复杂度 O ( n ) 。其中 n 是节点数。

go
func validTree(n int, edges [][]int) bool {
	if len(edges) != n-1 {
		return false
	}
	g := make([][]int, n)
	vis := make([]bool, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	var dfs func(int)
	dfs = func(i int) {
		vis[i] = true
		n--
		for _, j := range g[i] {
			if !vis[j] {
				dfs(j)
			}
		}
	}
	dfs(0)
	return n == 0
}

力扣原题 · Doocs 题解来源

305. 岛屿数量 II 🔒 ​

困难1 种解法

标签：并查集、数组、哈希表

题目、示例与约束

给你一个大小为 m x n 的二维二进制网格 grid 。网格表示一个地图，其中，0 表示水，1 表示陆地。最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。

可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。

返回一个整数数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后，地图中岛屿的数量。

岛屿 的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。

 

示例 1：

输入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
输出：[1,1,2,3]
解释：
起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」）
- 操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。此时存在 1 个岛屿。
- 操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。此时存在 1 个岛屿。
- 操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。此时存在 2 个岛屿。
- 操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。此时存在 3 个岛屿。

示例 2：

输入：m = 1, n = 1, positions = [[0,0]]
输出：[1]

 

提示：

  • 1 <= m, n, positions.length <= 104
  • 1 <= m * n <= 104
  • positions[i].length == 2
  • 0 <= ri < m
  • 0 <= ci < n

 

进阶：你可以设计一个时间复杂度 O(k log(mn)) 的算法解决此问题吗？（其中 k == positions.length）

方法一：并查集 · Go 实现

思考

陆地按时间逐格加入，每次需报告当前岛屿数。若每步对整图重新 DFS/BFS，总代价与操作次数、网格规模的乘积成正比。

新陆地先自成一岛，再与四邻已有陆地合并。并查集维护连通分量：仅当邻格已是陆地且分属不同集合时合并，同时将计数减一。重复加入同一格不改变图。因此每次操作近似常数，整体随 k 线性增长。

我们用一个二维数组 g r i d 来表示一个地图，其中 0 和 1 分别表示水和陆地。初始时 g r i d 中的所有单元格都是水单元格（即所有单元格都是 0 ），用一个变量 c n t 来记录岛屿的数量。而岛屿之间的连通关系可以用一个并查集 u f 来维护。

接下来，我们遍历数组 p o s i t i o n s 中的每个位置 ( i , j ) ，如果 g r i d [ i ] [ j ] 为 1 ，说明该位置已经是陆地，我们直接将 c n t 添加到答案中；否则，我们将 g r i d [ i ] [ j ] 的值改为 1 ，并且将 c n t 的值增加 1 。然后，我们遍历该位置的上下左右四个方向，如果某个方向的位置为 1 ，并且该位置与 ( i , j ) 不属于同一个连通分量，那么我们就将该位置与 ( i , j ) 进行合并，同时将 c n t 的值减少 1 。遍历完该位置的上下左右四个方向之后，我们将 c n t 添加到答案中。

时间复杂度 O ( k × α ( m × n ) ) 或 O ( k × log ⁡ ( m × n ) ) ，其中 k 是 p o s i t i o n s 的长度，而 α 是阿克曼函数的反函数，本题中 α ( m × n ) 可以认为是一个很小的常数。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func numIslands2(m int, n int, positions [][]int) (ans []int) {
	uf := newUnionFind(m * n)
	grid := make([][]int, m)
	for i := range grid {
		grid[i] = make([]int, n)
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	cnt := 0
	for _, p := range positions {
		i, j := p[0], p[1]
		if grid[i][j] == 1 {
			ans = append(ans, cnt)
			continue
		}
		grid[i][j] = 1
		cnt++
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && uf.union(i*n+j, x*n+y) {
				cnt--
			}
		}
		ans = append(ans, cnt)
	}
	return
}

力扣原题 · Doocs 题解来源

323. 无向图中连通分量的数目 🔒 ​

中等4 种解法

标签：深度优先搜索、广度优先搜索、并查集、图

题目、示例与约束

你有一个包含 n 个节点，下标从 0 到 n - 1 的图。给定一个整数 n 和一个数组 edges ，其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。

返回 图中已连接分量的数目 。

 

示例 1:

输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
输出: 2

示例 2:

输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
输出:  1

 

提示：

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i] = [ai, bi]
  • 0 <= ai <= bi < n
  • ai != bi
  • edges 中不会出现重复的边
方法一：DFS · Go 实现

思考

无向图的连通块个数。从每个未访问点出发走完其所在分量，每开始一次搜索计数加一。 n , m 规模允许 O ( n + m ) 。

建邻接表后 DFS：已访问返回 0 ，否则标记并递归邻居，返回 1 。对全部点求和即块数。

我们先根据给定的边构建一个邻接表 g ，其中 g [ i ] 表示节点 i 的所有邻居节点。

然后我们遍历所有节点，对于每个节点，我们使用 DFS 遍历所有与其相邻的节点，并将其标记为已访问，直到所有与其相邻的节点都被访问过，这样我们就找到了一个连通分量，答案加一。然后我们继续遍历下一个未访问的节点，直到所有节点都被访问过。

时间复杂度 O ( n + m ) ，空间复杂度 O ( n + m ) 。其中 n 和 m 分别是节点数和边数。

go
func countComponents(n int, edges [][]int) (ans int) {
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	vis := make([]bool, n)
	var dfs func(int) int
	dfs = func(i int) int {
		if vis[i] {
			return 0
		}
		vis[i] = true
		for _, j := range g[i] {
			dfs(j)
		}
		return 1
	}
	for i := range g {
		ans += dfs(i)
	}
	return
}
方法二：并查集 · Go 实现

思考

DFS 需要邻接表与递归栈。并查集按边合并：成功合并则块数减一，初始块数为 n 。无需显式建图，近似线性。

我们可以使用并查集来维护图中的连通分量。

我们首先初始化一个并查集，然后遍历所有的边，对于每条边 ( a , b ) ，我们将节点 a 和节点 b 合并到同一个连通分量中，如果连接成功，说明节点 a 和节点 b 之前不在同一个连通分量中，连通分量数目减一。

最后我们返回连通分量的数目。

时间复杂度 O ( n + m × α ( n ) ) ，空间复杂度 O ( n ) 。其中 n 和 m 分别是节点数和边数，而 α ( n ) 是 Ackermann 函数的反函数，可以看作是一个很小的常数。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func countComponents(n int, edges [][]int) int {
	uf := newUnionFind(n)
	for _, e := range edges {
		if uf.union(e[0], e[1]) {
			n--
		}
	}
	return n
}
方法三：BFS · Go 实现

思考

方法一用显式栈按深度优先扩展连通块。若改用队列，则按广度优先扩展同一块，每开始一次搜索计数同样加一。时间仍为 O ( n + m ) 。

我们也可以使用 BFS 来统计图中的连通分量。

与方法一类似，我们首先根据给定的边构建一个邻接表 g ，然后遍历所有节点，对于每个节点，如果它没有被访问过，我们就从该节点开始进行 BFS 遍历，将所有与其相邻的节点都标记为已访问，直到所有与其相邻的节点都被访问过，这样我们就找到了一个连通分量，答案加一。

遍历所有节点后，我们就得到了图中连通分量的数目。

时间复杂度 O ( n + m ) ，空间复杂度 O ( n + m ) 。其中 n 和 m 分别是节点数和边数。

go
func countComponents(n int, edges [][]int) (ans int) {
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	vis := make([]bool, n)
	for i := range g {
		if vis[i] {
			continue
		}
		vis[i] = true
		ans++
		q := []int{i}
		for len(q) > 0 {
			a := q[0]
			q = q[1:]
			for _, b := range g[a] {
				if !vis[b] {
					vis[b] = true
					q = append(q, b)
				}
			}
		}
	}
	return
}
方法四：显式栈 · Go 实现

思考

无向图的连通块个数等于从每个未访问点出发、走完其所在分量的次数。 n ≤ 2000 ，一次 O ( n + m ) 的遍历就够。沿一条链递归扩展邻居时，调用深度等于节点数，链长达到 1000 就会超出 Python 的递归上限。因此每个新连通块用栈扩展：入栈时立刻标记，弹出后把未访问的邻居压入。标记发生在入栈时，所以同一节点不会重复进入。每个新的起点使答案加一。

先根据给定的边构建邻接表 g ， g [ i ] 是节点 i 的全部邻居。

然后遍历所有节点。遇到未访问的节点 i ，答案加一，并把 i 压入栈、同时标记为已访问。栈不为空时弹出节点 u ，把它每个尚未访问的邻居标记后压入栈。这一轮结束后， i 所在的连通块都已访问。继续处理下一个未访问节点，直到所有节点都被访问过。邻居的入栈顺序不影响连通块的个数。

时间复杂度 O ( n + m ) ，空间复杂度 O ( n + m ) 。其中 n 和 m 分别是节点数和边数。

go
func countComponents(n int, edges [][]int) int {
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	vis := make([]bool, n)
	ans := 0
	for i := 0; i < n; i++ {
		if vis[i] {
			continue
		}
		ans++
		stk := []int{i}
		vis[i] = true
		for len(stk) > 0 {
			u := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			for _, v := range g[u] {
				if !vis[v] {
					vis[v] = true
					stk = append(stk, v)
				}
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

399. 除法求值 ​

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、图、数组、字符串、最短路、Floyd 算法、Bellman–Ford 算法

题目、示例与约束

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

 

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0

示例 2：

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

 

提示：

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj 由小写英文字母与数字组成
方法一 · Go 实现

思考

已知 a / b 的值，查询其他比值。建图后 BFS/DFS 求路径乘积即可，变量多时并查集带权更省。

w [ x ] 表示 x 相对根的比值。find 路径压缩时把权乘到根。合并 a / b = v 时按 w [ p a ] = w [ b ] ⋅ v / w [ a ] 接上。查询若不同根或不存在则 − 1 ，否则 w [ c ] / w [ d ] 。

go
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	p := make(map[string]string)
	w := make(map[string]float64)
	for _, e := range equations {
		a, b := e[0], e[1]
		p[a], p[b] = a, b
		w[a], w[b] = 1.0, 1.0
	}

	var find func(x string) string
	find = func(x string) string {
		if p[x] != x {
			origin := p[x]
			p[x] = find(p[x])
			w[x] *= w[origin]
		}
		return p[x]
	}

	for i, v := range values {
		a, b := equations[i][0], equations[i][1]
		pa, pb := find(a), find(b)
		if pa == pb {
			continue
		}
		p[pa] = pb
		w[pa] = w[b] * v / w[a]
	}
	var ans []float64
	for _, e := range queries {
		c, d := e[0], e[1]
		if p[c] == "" || p[d] == "" || find(c) != find(d) {
			ans = append(ans, -1.0)
		} else {
			ans = append(ans, w[c]/w[d])
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

547. 省份数量 ​

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、图

题目、示例与约束

有 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][i]
方法一：DFS · Go 实现

思考

省份是连通块。邻接矩阵给出城市之间是否直接相连，从每个未访问城市 DFS/BFS 即可染完一块。

扫一遍城市，遇到未访问的起点就开一次 DFS 并把答案加一。访问数组保证每个城市只进入一次。

我们创建一个数组 vis ，用于记录每个城市是否被访问过。

接下来，遍历每个城市 i ，如果该城市未被访问过，则从该城市开始深度优先搜索，通过矩阵 isConnected 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个省，然后对这些城市继续深度优先搜索，直到同一个省的所有城市都被访问到，即可得到一个省，将答案 ans 加 1 ，然后遍历下一个未被访问过的城市，直到遍历完所有的城市。

最后返回答案即可。

时间复杂度 O ( n 2 ) ，空间复杂度 O ( n ) 。其中 n 是城市的数量。

go
func findCircleNum(isConnected [][]int) (ans int) {
	n := len(isConnected)
	vis := make([]bool, n)
	var dfs func(int)
	dfs = func(i int) {
		vis[i] = true
		for j, x := range isConnected[i] {
			if !vis[j] && x == 1 {
				dfs(j)
			}
		}
	}
	for i, v := range vis {
		if !v {
			ans++
			dfs(i)
		}
	}
	return
}
方法二：并查集 · Go 实现

思考

DFS 依赖递归栈与访问数组。并查集按边合并：初始 n 个分量，每条互连且尚未同根的边把答案减一。

只枚举上三角避免重复边。路径压缩保证查找接近常数。最终答案即剩余根的个数。

我们也可以用并查集维护每个连通分量，初始时，每个城市都属于不同的连通分量，所以省份数量为 n 。

接下来，遍历矩阵 isConnected ，如果两个城市 ( i , j ) 之间有相连关系，并且处于两个不同的连通分量，则它们将被合并成为一个连通分量，然后将省份数量减去 1 。

最后返回省份数量即可。

时间复杂度 O ( n 2 × log ⁡ n ) ，空间复杂度 O ( n ) 。其中 n 是城市的数量，而 log ⁡ n 是并查集的路径压缩的时间复杂度。

go
func findCircleNum(isConnected [][]int) (ans int) {
	n := len(isConnected)
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	ans = n
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if isConnected[i][j] == 1 {
				pa, pb := find(i), find(j)
				if pa != pb {
					p[pa] = pb
					ans--
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

684. 冗余连接 ​

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、图

题目、示例与约束

树可以看成是一个连通且 无环 的 无向 图。

给定一个图，该图从一棵 n 个节点 (节点值 1～n) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

 

示例 1：

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

 

提示:

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai != bi
  • edges 中无重复元素
  • 给定的图是连通的 
方法一：并查集 · Go 实现

思考

无向图由树加一条边而成，要删掉使图重新成树的那条（输入中最后出现的）。DFS 找环再比边序偏繁。

按输入顺序并查集连边：两端已连通则这条边在环上，即为答案；否则合并。第一次冲突就是最后那条多余边。

根据题意，我们需要找到一条可以删去的边，删除后剩余部分是一个有着 n 个节点的树。我们可以遍历每一条边，判断这条边是否在同一个连通分量中。如果在同一个连通分量中，则说明这条边是多余的，可以删除，直接返回这条边即可。否则，我们将这条边所连接的两个节点合并到同一个连通分量中。

时间复杂度 O ( n log ⁡ n ) ，空间复杂度 O ( n ) 。其中 n 为边的数量。

go
func findRedundantConnection(edges [][]int) []int {
	n := len(edges)
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for i := 0; ; i++ {
		pa, pb := find(edges[i][0]-1), find(edges[i][1]-1)
		if pa == pb {
			return edges[i]
		}
		p[pa] = pb
	}
}
方法二：并查集（模板做法） · Go 实现

思考

方法一内嵌 find。抽出带按秩合并的 UnionFind，union 返回是否成功，主循环只判断失败即返回，逻辑相同、常数更好。

这里给出一个并查集的模板做法，供大家参考。

时间复杂度 O ( n α ( n ) ) ，空间复杂度 O ( n ) 。其中 n 为边的数量，而 α ( n ) 是阿克曼函数的反函数，可以认为是一个很小的常数。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func findRedundantConnection(edges [][]int) []int {
	uf := newUnionFind(len(edges))
	for i := 0; ; i++ {
		if !uf.union(edges[i][0]-1, edges[i][1]-1) {
			return edges[i]
		}
	}
}

力扣原题 · Doocs 题解来源

685. 冗余连接 II ​

困难2 种解法

标签：深度优先搜索、广度优先搜索、并查集、图

题目、示例与约束

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

 

示例 1：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]

 

提示：

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n
方法一：并查集 · Go 实现

思考

有向树多一条边后，可能出现入度为 2 的点，或指向根形成环，或二者兼有。无向并查集不能直接处理双入边。

先找入度为 2 的两条边。若存在，尝试丢掉较后的那条再并查：仍成环则应删较早的。若没有双入边，则按无向情形删掉成环的那条。

根据题目描述，对于一棵有根树，根节点的入度为 0 ，其余节点的入度为 1 。在向树中添加一条边之后，可能会出现以下三种情况：

  1. 添加的边指向了非根节点，该节点的入度变为 2 ，此时图中不存在有向环；

    plaintext
       1
  / \
 v   v
 2-->3

  2. 添加的边指向了非根节点，该节点的入度变为 2 ，此时图中存在有向环；

    plaintext
       1
   |
   v
   2 <--> 3

  3. 添加的边指向了根节点，根节点的入度变为 1 ，此时图中存在有向环，但不存在入度为 2 的节点。

    plaintext
        1
    /^
   v  \
   2-->3

因此，我们首先计算每个节点的入度，如果存在入度为 2 的节点，我们定位到该节点对应的两条边，分别记为 dup [ 0 ] 和 dup [ 1 ] 。如果在删除 dup [ 1 ] 之后，剩余的边无法形成树，则说明 dup [ 0 ] 是需要删除的边；否则 dup [ 1 ] 是需要删除的边。

如果不存在入度为 2 的节点，我们遍历数组 edges ，对于每条边 ( u , v ) ，我们使用并查集维护节点之间的连通性。如果 u 和 v 已经连通，说明图中存在有向环，此时当前边即为需要删除的边。

时间复杂度 O ( n log ⁡ n ) ，空间复杂度 O ( n ) 。其中 n 为边的数量。

go
func findRedundantDirectedConnection(edges [][]int) []int {
	n := len(edges)
	ind := make([]int, n)
	for _, e := range edges {
		ind[e[1]-1]++
	}
	dup := []int{}
	for i, e := range edges {
		if ind[e[1]-1] == 2 {
			dup = append(dup, i)
		}
	}
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	if len(dup) > 0 {
		for i, e := range edges {
			if i == dup[1] {
				continue
			}
			pu, pv := find(e[0]-1), find(e[1]-1)
			if pu == pv {
				return edges[dup[0]]
			}
			p[pu] = pv
		}
		return edges[dup[1]]
	}
	for _, e := range edges {
		pu, pv := find(e[0]-1), find(e[1]-1)
		if pu == pv {
			return e
		}
		p[pu] = pv
	}
	return nil
}
方法二：并查集（模板做法） · Go 实现

思考

判定逻辑与方法一相同，只是把路径压缩与按秩合并收进模板类，主函数只处理 dup 与 union 失败。

这里给出一个并查集的模板做法，供大家参考。

时间复杂度 O ( n α ( n ) ) ，空间复杂度 O ( n ) 。其中 n 为边的数量，而 α ( n ) 是阿克曼函数的反函数，可以认为是一个很小的常数。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func findRedundantDirectedConnection(edges [][]int) []int {
	n := len(edges)
	ind := make([]int, n)
	for _, e := range edges {
		ind[e[1]-1]++
	}
	dup := []int{}
	for i, e := range edges {
		if ind[e[1]-1] == 2 {
			dup = append(dup, i)
		}
	}
	uf := newUnionFind(n)
	if len(dup) > 0 {
		for i, e := range edges {
			if i == dup[1] {
				continue
			}
			if !uf.union(e[0]-1, e[1]-1) {
				return edges[dup[0]]
			}
		}
		return edges[dup[1]]
	}
	for _, e := range edges {
		if !uf.union(e[0]-1, e[1]-1) {
			return e
		}
	}
	return nil
}

力扣原题 · Doocs 题解来源

694. 不同岛屿的数量 🔒 ​

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、矩阵、排序、哈希函数

题目、示例与约束

给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。

请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。

 

示例 1：

输入: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
输出：1

示例 2：

输入: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
输出: 3

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 仅包含 0 或 1
方法一：哈希表 + DFS · Go 实现

思考

两座岛相同当且仅当平移后重合，旋转镜像不算。记录相对坐标要对齐起点。

DFS 把前进方向与回溯方向都写入路径串，形状不同则序列不同。哈希集合去重后计数。访问过的陆地改成 0 。

我们遍历网格中的每个位置 ( i , j ) ，如果该位置为 1 ，则以其为起始节点开始进行深度优先搜索，过程中将 1 修改为 0 ，并且将搜索的方向记录下来，等搜索结束后将方向序列加入哈希表中，最后返回哈希表中不同方向序列的数量即可。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别为网格的行数和列数。

go
func numDistinctIslands(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	paths := map[string]bool{}
	path := []byte{}
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j, k int)
	dfs = func(i, j, k int) {
		grid[i][j] = 0
		path = append(path, byte(k))
		for h := 1; h < 5; h++ {
			x, y := i+dirs[h-1], j+dirs[h]
			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
				dfs(x, y, h)
			}
		}
		path = append(path, byte(k))
	}
	for i, row := range grid {
		for j, x := range row {
			if x == 1 {
				dfs(i, j, 0)
				paths[string(path)] = true
				path = path[:0]
			}
		}
	}
	return len(paths)
}

力扣原题 · Doocs 题解来源

695. 岛屿的最大面积 ​

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

 

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 为 0 或 1
方法一：DFS · Go 实现

思考

岛屿面积是四连通陆地格数，求最大。每个格子至多访问一次。

遇到陆地就 DFS，把格子改成 0 并累加四向递归结果。对所有起点取最大。

我们可以遍历每一个格子 ( i , j ) ，从每个格子开始进行深度优先搜索，如果搜索到的格子是陆地，就将当前格子标记为已访问，并且继续搜索上、下、左、右四个方向的格子。搜索结束后，计算标记的陆地的数量，即为岛屿的面积。我们找出最大的岛屿面积即为答案。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别是二维数组的行数和列数。

go
func maxAreaOfIsland(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if grid[i][j] == 0 {
			return 0
		}
		ans := 1
		grid[i][j] = 0
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n {
				ans += dfs(x, y)
			}
		}
		return ans
	}
	for i := range grid {
		for j := range grid[i] {
			ans = max(ans, dfs(i, j))
		}
	}
	return
}

力扣原题 · Doocs 题解来源

711. 不同岛屿的数量 II 🔒 ​

困难1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、矩阵、排序、哈希函数

题目、示例与约束

给定一个 m x n 二进制数组表示的网格 grid ，一个岛屿由 四连通 （上、下、左、右四个方向）的 1 组成（代表陆地）。你可以认为网格的四周被海水包围。

如果两个岛屿的形状相同，或者通过旋转（顺时针旋转 90°，180°，270°）、翻转（左右翻转、上下翻转）后形状相同，那么就认为这两个岛屿是相同的。

返回 这个网格中形状 不同 的岛屿的数量 。

 

示例 1:

输入: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
输出: 1
解释: 这两个是相同的岛屿。因为我们通过 180° 旋转第一个岛屿，两个岛屿的形状相同。

示例 2:

输入: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
输出: 1

 

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 不是 0 就是 1.
方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

本站根据题意与 Doocs 参考思路整理为 Go，非上游原文。按 CC BY-SA 4.0 共享。

先遍历得到每个岛屿的坐标。生成交换横纵坐标及正负号构成的八种旋转、反射形式；每种排序后减去首个坐标消除平移，并选最小编码作为规范形。相同规范形只计一次。设网格有 M·N 格、岛屿大小为 k，时间 O(MN+Σk log k)，空间 O(MN)。实现会把已访问的陆地改为零。

go
import (
	"fmt"
	"sort"
	"strings"
)

type point struct{ x, y int }

func numDistinctIslands2(grid [][]int) int {
	if len(grid) == 0 {
		return 0
	}
	m, n := len(grid), len(grid[0])
	seen := map[string]bool{}
	dirs := []point{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] != 1 {
				continue
			}
			shape := []point{}
			stack := []point{{i, j}}
			grid[i][j] = 0
			for len(stack) > 0 {
				p := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				shape = append(shape, p)
				for _, d := range dirs {
					x, y := p.x+d.x, p.y+d.y
					if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
						grid[x][y] = 0
						stack = append(stack, point{x, y})
					}
				}
			}
			canonical := ""
			for variant := 0; variant < 8; variant++ {
				transformed := make([]point, len(shape))
				for k, p := range shape {
					x, y := p.x, p.y
					if variant&4 != 0 {
						x, y = y, x
					}
					if variant&1 != 0 {
						x = -x
					}
					if variant&2 != 0 {
						y = -y
					}
					transformed[k] = point{x, y}
				}
				sort.Slice(transformed, func(i, j int) bool {
					a, b := transformed[i], transformed[j]
					return a.x < b.x || (a.x == b.x && a.y < b.y)
				})
				origin := transformed[0]
				var key strings.Builder
				for _, p := range transformed {
					fmt.Fprintf(&key, "%d,%d;", p.x-origin.x, p.y-origin.y)
				}
				encoded := key.String()
				if variant == 0 || encoded < canonical {
					canonical = encoded
				}
			}
			seen[canonical] = true
		}
	}
	return len(seen)
}

力扣原题 · Doocs 题解来源

721. 账户合并 ​

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、字符串、排序

题目、示例与约束

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

 

示例 1：

输入：accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
输出：[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。 
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。

示例 2：

输入：accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
输出：[["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

 

提示：

  • 1 <= accounts.length <= 1000
  • 2 <= accounts[i].length <= 10
  • 1 <= accounts[i][j].length <= 30
  • accounts[i][0] 由英文字母组成
  • accounts[i][j] (for j > 0) 是有效的邮箱地址
方法一：并查集 + 哈希表 · Go 实现

思考

同一人的多个账户会通过共享邮箱连通，需要按人合并邮箱并排序。账户数约 1000 ，若两两比较邮箱集合，既慢也难维护姓名。

连通关系发生在「账户」这一层：两个账户只要出现同一个邮箱就应合并。并查集按账户下标连边，邮箱到首次出现账户的映射用来发现这条边。

合并后再按根下标把邮箱收入集合，姓名取该根账户的名字，最后对邮箱排序输出。查找带路径压缩，总代价接近线性对数。

根据题目描述，我们可以使用并查集，将具有相同邮箱地址的账户合并在一起。

我们首先遍历所有的账户，对于第 i 个账户，我们遍历其所有的邮箱地址，如果该邮箱地址在哈希表 d 中出现过，则使用并查集，将该账户的编号 i 与之前出现过的邮箱地址所属的账户编号进行合并；否则，将该邮箱地址与账户的编号 i 进行映射。

接下来，我们遍历所有的账户，对于第 i 个账户，我们使用并查集找到其根节点，然后将该账户的所有邮箱地址添加到哈希表 g 中，其中键为根节点，值为该账户的所有邮箱地址。

时间复杂度 O ( n × log ⁡ n ) ，空间复杂度 O ( n ) 。其中 n 为账户的数量。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func accountsMerge(accounts [][]string) (ans [][]string) {
	n := len(accounts)
	uf := newUnionFind(n)
	d := make(map[string]int)
	for i := 0; i < n; i++ {
		for _, email := range accounts[i][1:] {
			if j, ok := d[email]; ok {
				uf.union(i, j)
			} else {
				d[email] = i
			}
		}
	}
	g := make(map[int]map[string]struct{})
	for i := 0; i < n; i++ {
		root := uf.find(i)
		if _, ok := g[root]; !ok {
			g[root] = make(map[string]struct{})
		}
		for _, email := range accounts[i][1:] {
			g[root][email] = struct{}{}
		}
	}
	for root, s := range g {
		emails := []string{}
		for email := range s {
			emails = append(emails, email)
		}
		sort.Strings(emails)
		account := append([]string{accounts[root][0]}, emails...)
		ans = append(ans, account)
	}
	return
}

力扣原题 · Doocs 题解来源

737. 句子相似性 II 🔒 ​

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、字符串

题目、示例与约束

我们可以将一个句子表示为一个单词数组，例如，句子 I am happy with leetcode"可以表示为 arr = ["I","am",happy","with","leetcode"]

给定两个句子 sentence1 和 sentence2 分别表示为一个字符串数组，并给定一个字符串对 similarPairs ，其中 similarPairs[i] = [xi, yi] 表示两个单词 xi 和 yi 是相似的。

如果 sentence1 和 sentence2 相似则返回 true ，如果不相似则返回 false 。

两个句子是相似的，如果:

  • 它们具有 相同的长度 (即相同的词数)
  • sentence1[i] 和 sentence2[i] 是相似的

请注意，一个词总是与它自己相似，也请注意，相似关系是可传递的。例如，如果单词 a 和 b 是相似的，单词 b 和 c 也是相似的，那么 a 和 c 也是 相似 的。

 

示例 1:

输入: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
输出: true
解释: 这两个句子长度相同，每个单词都相似。

示例 2:

输入: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","onepiece"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
输出: true
解释: "leetcode" --> "platform" --> "anime" --> "manga" --> "onepiece".
因为“leetcode”和“onepiece”相似，而且前两个单词是相同的，所以这两句话是相似的。

示例 3:

输入: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","hunterXhunter"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
输出: false
解释: “leetcode”和“onepiece”不相似。

 

提示:

  • 1 <= sentence1.length, sentence2.length <= 1000
  • 1 <= sentence1[i].length, sentence2[i].length <= 20
  • sentence1[i] 和 sentence2[i] 只包含大小写英文字母
  • 0 <= similarPairs.length <= 2000
  • similarPairs[i].length == 2
  • 1 <= xi.length, yi.length <= 20
  • xi 和 yi 只含英文字母
方法一 · Go 实现

思考

与「句子相似性」不同，相似关系可传递。直接存边对不够，需要知道两词是否落在同一连通分量。词数由相似对规模限制，并查集合适。

先给出现过的词编号，相似对做一次合并。比较句子时，相同词通过；否则两者都必须出现在并查集中且根相同。

长度不同直接失败。查找带路径压缩，总时间与词数及句长近线性。

go
var p []int

func areSentencesSimilarTwo(sentence1 []string, sentence2 []string, similarPairs [][]string) bool {
	if len(sentence1) != len(sentence2) {
		return false
	}
	n := len(similarPairs)
	p = make([]int, (n<<1)+10)
	for i := 0; i < len(p); i++ {
		p[i] = i
	}
	words := make(map[string]int)
	idx := 1
	for _, e := range similarPairs {
		a, b := e[0], e[1]
		if words[a] == 0 {
			words[a] = idx
			idx++
		}
		if words[b] == 0 {
			words[b] = idx
			idx++
		}
		p[find(words[a])] = find(words[b])
	}
	for i := 0; i < len(sentence1); i++ {
		if sentence1[i] == sentence2[i] {
			continue
		}
		if words[sentence1[i]] == 0 || words[sentence2[i]] == 0 || find(words[sentence1[i]]) != find(words[sentence2[i]]) {
			return false
		}
	}
	return true
}

func find(x int) int {
	if p[x] != x {
		p[x] = find(p[x])
	}
	return p[x]
}

力扣原题 · Doocs 题解来源

765. 情侣牵手 ​

困难1 种解法

标签：贪心、深度优先搜索、广度优先搜索、并查集、图

题目、示例与约束

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n - 2, 2n - 1)。

返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

 

示例 1:

输入: row = [0,2,1,3]
输出: 1
解释: 只需要交换第二个人（row[1]）和第三个人（row[2]）的位置即可。

示例 2:

输入: row = [3,2,0,1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

 

提示:

  • 2n == row.length
  • 2 <= n <= 30
  • n 是偶数
  • 0 <= row[i] < 2n
  • row 中所有元素均 无重复
方法一：并查集 · Go 实现

思考

情侣两两相邻入座，求最少交换。 n 对情侣，模拟交换可行，但交换次数等于「错坐」连通块的结构。

把一对座位上的两个人映射成情侣编号后，若两对坐在一起则这两对进入同一置换。大小为 y 的环需要 y − 1 次交换。

并查集合并每对座位上的情侣编号，答案为对数减去连通块数。

我们可以给每一对情侣编号，编号 0 和 1 的人对应情侣 0 ，编号 2 和 3 的人对应情侣 1 ...即编号为 r o w [ i ] 对应的情侣编号为 ⌊ r o w [ i ] 2 ⌋ 。

如果有 k 对情侣相互之间坐错了位置，也即是说，有 k 对情侣处于一个置换环中，那么他们之间需要经过 k − 1 次交换才能都坐到正确的位置上。

为什么？不妨这样考虑，我们先调整一对情侣的位置，使其坐到正确的位置上，那么问题就从 k 对情侣的问题，转换成了 k − 1 对情侣的问题。依此类推，最终 k = 1 时，交换次数为 0 。所以，如果 k 对情侣相互之间坐错了位置，那么需要 k − 1 次交换。

因此，我们只需要遍历一遍数组，利用并查集找出有多少个置换环，假设有 x 个，每个环的大小（情侣的对数）为 y 1 , y 2 , ⋯ , y x ，那么需要交换的次数为 y 1 − 1 + y 2 − 1 + ⋯ + y x − 1 = y 1 + y 2 + ⋯ + y x − x = n − x 。

时间复杂度 O ( n × α ( n ) ) ，空间复杂度 O ( n ) 。其中 α ( n ) 为阿克曼函数的反函数，可以认为是一个很小的常数。

go
func minSwapsCouples(row []int) int {
	n := len(row) >> 1
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for i := 0; i < n<<1; i += 2 {
		a, b := row[i]>>1, row[i+1]>>1
		p[find(a)] = find(b)
	}
	ans := n
	for i := range p {
		if find(i) == i {
			ans--
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

778. 水位上升的泳池中游泳 ​

困难1 种解法

标签：深度优先搜索、广度优先搜索、并查集、极小化极大、数组、二分查找、矩阵、Dijkstra 算法、堆（优先队列）

题目、示例与约束

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

 

示例 1:

输入: grid = [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

示例 2:

输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
输出: 16
解释: 最终的路线用加粗进行了标记。
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

 

提示:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 50
  • 0 <= grid[i][j] < n2
  • grid[i][j] 中每个值 均无重复
方法一：并查集 · Go 实现

思考

水位随时间上涨，时刻 t 只能走高度 ≤ t 的格子，求从左上到右下的最早时刻。高度是 0. . n 2 − 1 的排列，可按高度从低到高加入格子。

加入高度为 t 的格并与已加入的四邻连通后，若起点与终点连通，则 t 就是答案。并查集维护连通。

先把高度映射到坐标，再按 t 递增合并。时间 O ( n 2 α ) 。

我们可以将每个位置 ( i , j ) 映射为一个编号 i d = i × n + j ，并使用并查集维护连通分量。

我们首先用一个一维数组 h i 记录每个高度对应的位置编号，即 h i [ h ] 表示高度为 h 的位置编号。

然后我们从高度 0 开始遍历到高度 n 2 − 1 ，对于每个高度 t ，我们将位置 h i [ t ] 与其四个相邻且高度不超过 t 的位置进行合并。如果合并后，位置 0 和位置 n 2 − 1 连通了，那么我们就找到了最小的时间 t ，返回 t 即可。

时间复杂度 O ( n 2 × log ⁡ n ) ，空间复杂度 O ( n 2 ) 。其中 n 是矩阵的边长。

go
func swimInWater(grid [][]int) int {
	n := len(grid)
	m := n * n
	p := make([]int, m)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	hi := make([]int, m)
	for i := range grid {
		for j, h := range grid[i] {
			hi[h] = i*n + j
		}
	}
	dirs := []int{-1, 0, 1, 0, -1}
	for t := 0; t < m; t++ {
		id := hi[t]
		x, y := id/n, id%n
		for k := 0; k < 4; k++ {
			nx, ny := x+dirs[k], y+dirs[k+1]
			if nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] <= t {
				a := find(x*n + y)
				b := find(nx*n + ny)
				p[a] = b
			}
		}
		if find(0) == find(m-1) {
			return t
		}
	}
	return 0
}

力扣原题 · Doocs 题解来源

785. 判断二分图 ​

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、图、图的着色、二分图

题目、示例与约束
存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
  • 不存在自环（graph[u] 不包含 u）。
  • 不存在平行边（graph[u] 不包含重复值）。
  • 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
  • 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

如果图是二分图，返回 true ；否则，返回 false 。

 

示例 1：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：

输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

 

提示：

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] 不会包含 u
  • graph[u] 的所有值 互不相同
  • 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u
方法一：染色法判定二分图 · Go 实现

思考

判断无向图是否二分。 n ≤ 100 ，从每个未染色点用两种颜色 DFS，邻点必须异色；若已染色且同色则失败。

图可能不连通，要对每个连通块都染一遍。

遍历所有节点进行染色，比如初始为白色，DFS 对节点相邻的点染上另外一种颜色。如果要染色某节点时，要染的目标颜色和该节点的已经染过的颜色不同，则说明不能构成二分图。

时间复杂度 O ( n ) ，空间复杂度 O ( n ) 。其中 n 为节点数。

go
func isBipartite(graph [][]int) bool {
	n := len(graph)
	color := make([]int, n)
	var dfs func(int, int) bool
	dfs = func(a, c int) bool {
		color[a] = c
		for _, b := range graph[a] {
			if color[b] == c || (color[b] == 0 && !dfs(b, -c)) {
				return false
			}
		}
		return true
	}
	for i := range graph {
		if color[i] == 0 && !dfs(i, 1) {
			return false
		}
	}
	return true
}
方法二：并查集 · Go 实现

思考

染色可用并查集改写：一个点的所有邻居应在同一部，且不与该点同部。

若某点与邻居已在同一集合则不是二分图；否则把该点的邻居互相合并。

对于本题，如果是二分图，那么图中每个顶点的所有邻接点都应该属于同一集合，且不与顶点处于同一集合，因此我们可以使用并查集。遍历图中每个顶点，如果发现存在当前顶点与对应的邻接点处于同一个集合，说明不是二分图。否则将当前节点的邻接点相互进行合并。

时间复杂度 O ( n × log ⁡ n ) ，空间复杂度 O ( n ) 。其中 n 为节点数。

go
func isBipartite(graph [][]int) bool {
	n := len(graph)
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for a, bs := range graph {
		for _, b := range bs {
			pa, pb := find(a), find(b)
			if pa == pb {
				return false
			}
			p[pb] = find(bs[0])
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

803. 打砖块 ​

困难1 种解法

标签：并查集、数组、矩阵

题目、示例与约束

有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

  • 一块砖直接连接到网格的顶部，或者
  • 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时

给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 掉落 。一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

 

示例 1：

输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：网格开始为：
[[1,0,0,0]，
 [1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
 [0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
 [0,0,0,0]]
因此，结果为 [2] 。

示例 2：

输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：网格开始为：
[[1,0,0,0],
 [1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
 [1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0], 
 [1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
 [0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • grid[i][j] 为 0 或 1
  • 1 <= hits.length <= 4 * 104
  • hits[i].length == 2
  • 0 <= xi <= m - 1
  • 0 <= yi <= n - 1
  • 所有 (xi, yi) 互不相同
方法一 · Go 实现

思考

每次打击后正向洪水填充统计掉落， h i t s 达 4 ⋅ 10 4 、 m , n ≤ 200 ，重复搜索过慢。掉落的本质是「与顶行的连通被切断」。

为此先打掉全部打击位置，用并查集把剩余砖块连到一个虚拟屋顶，再按相反顺序补回砖块。补回后屋顶连通块的增量减一，即该次打击实际掉落的砖数；原先就是空格的打击贡献为零。

go
func hitBricks(grid [][]int, hits [][]int) []int {
	m, n := len(grid), len(grid[0])
	p := make([]int, m*n+1)
	size := make([]int, len(p))
	for i := range p {
		p[i] = i
		size[i] = 1
	}

	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	union := func(a, b int) {
		pa, pb := find(a), find(b)
		if pa != pb {
			size[pb] += size[pa]
			p[pa] = pb
		}
	}

	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
		for j := range g[i] {
			g[i][j] = grid[i][j]
		}
	}
	for _, h := range hits {
		g[h[0]][h[1]] = 0
	}
	for j, v := range g[0] {
		if v == 1 {
			union(j, m*n)
		}
	}
	for i := 1; i < m; i++ {
		for j := 0; j < n; j++ {
			if g[i][j] == 0 {
				continue
			}
			if g[i-1][j] == 1 {
				union(i*n+j, (i-1)*n+j)
			}
			if j > 0 && g[i][j-1] == 1 {
				union(i*n+j, i*n+j-1)
			}
		}
	}
	ans := make([]int, len(hits))
	dirs := []int{-1, 0, 1, 0, -1}
	for k := len(hits) - 1; k >= 0; k-- {
		i, j := hits[k][0], hits[k][1]
		if grid[i][j] == 0 {
			continue
		}
		g[i][j] = 1
		prev := size[find(m*n)]
		if i == 0 {
			union(j, m*n)
		}
		for l := 0; l < 4; l++ {
			x, y := i+dirs[l], j+dirs[l+1]
			if x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1 {
				union(i*n+j, x*n+y)
			}
		}
		curr := size[find(m*n)]
		ans[k] = max(0, curr-prev-1)
	}
	return ans
}

力扣原题 · Doocs 题解来源

827. 最大人工岛 ​

困难1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

 

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

 

提示：

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 500
  • grid[i][j] 为 0 或 1
方法一：DFS · Go 实现

思考

最多把一个 0 改成 1 ，求最大连通块。 n ≤ 500 ，对每个 0 做一次洪水填充会重复访问同一岛屿。

先 DFS 给每座岛编号并记下面积。再枚举每个 0 ，把其四邻不同岛的面积相加再加一。若全是 1 ，答案即最大岛面积。

我们可以给每个连通块一个唯一的标识，用数组 p 记录每个位置所属的连通块，即 p [ i ] [ j ] 表示 ( i , j ) 所属的连通块编号。用数组 c n t 记录每个连通块的大小，即 c n t [ r o o t ] 表示连通块 r o o t 的大小。

首先，我们遍历整个矩阵，对于每个 g r i d [ i ] [ j ] = 1 且 p [ i ] [ j ] = 0 的位置，我们对其进行深度优先搜索，将其所属的连通块标记为 r o o t ，并统计连通块的大小。

接着，我们遍历整个矩阵，对于每个 g r i d [ i ] [ j ] = 0 的位置，我们找到其上、下、左、右四个位置所属的连通块，将这些连通块的大小相加，再加上当前位置的 1 ，即可得到将当前位置变为 1 后的最大岛屿面积。

时间复杂度 O ( n 2 ) ，空间复杂度 O ( n 2 ) 。其中 n 为矩阵的边长。

go
func largestIsland(grid [][]int) int {
	n := len(grid)
	p := make([][]int, n)
	for i := range p {
		p[i] = make([]int, n)
	}
	cnt := make([]int, n*n+1)
	dirs := []int{-1, 0, 1, 0, -1}
	root := 0
	ans := 0

	var dfs func(int, int) int
	dfs = func(i, j int) int {
		p[i][j] = root
		cnt[root]++
		for k := 0; k < 4; k++ {
			x := i + dirs[k]
			y := j + dirs[k+1]
			if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1 && p[x][y] == 0 {
				dfs(x, y)
			}
		}
		return cnt[root]
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 && p[i][j] == 0 {
				root++
				ans = max(ans, dfs(i, j))
			}
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 {
				s := make(map[int]struct{})
				for k := 0; k < 4; k++ {
					x := i + dirs[k]
					y := j + dirs[k+1]
					if x >= 0 && x < n && y >= 0 && y < n {
						s[p[x][y]] = struct{}{}
					}
				}
				t := 1
				for x := range s {
					t += cnt[x]
				}
				ans = max(ans, t)
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

839. 相似字符串组 ​

困难1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、字符串

题目、示例与约束

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

 

示例 1：

输入：strs = ["tars","rats","arts","star"]
输出：2

示例 2：

输入：strs = ["omv","ovm"]
输出：1

 

提示：

  • 1 <= strs.length <= 300
  • 1 <= strs[i].length <= 300
  • strs[i] 只包含小写字母。
  • strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。
方法一：并查集 · Go 实现

思考

相似（至多两个位置不同）具有传递性，组数即连通块个数。 n ≤ 300 ，两两比较并查集合并即可。

题目保证互为异位词，故只需数不同位置：不超过 2 则连边。每次成功合并使块数减一，最后剩下的块数即答案。

我们可以枚举字符串列表中的任意两个字符串 s 和 t ，由于 s 和 t 是字母异位词，因此如果 s 和 t 的对应位置字符不同的数量不超过 2 ，那么 s 和 t 是相似的，我们就可以使用并查集将 s 和 t 合并，如果合并成功，那么相似字符串组的数量减少 1 。

最终相似字符串组的数量就是并查集中连通分量的数量。

时间复杂度 O ( n 2 × ( m + α ( n ) ) ) ，空间复杂度 O ( n ) 。其中 n 和 m 分别是字符串列表的长度和字符串的长度，而 α ( n ) 是 Ackermann 函数的反函数，可以看成是一个很小的常数。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func numSimilarGroups(strs []string) int {
	n := len(strs)
	uf := newUnionFind(n)
	for i, s := range strs {
		for j, t := range strs[:i] {
			diff := 0
			for k := range s {
				if s[k] != t[k] {
					diff++
				}
			}
			if diff <= 2 && uf.union(i, j) {
				n--
			}
		}
	}
	return n
}

力扣原题 · Doocs 题解来源

886. 可能的二分法 ​

中等3 种解法

标签：深度优先搜索、广度优先搜索、并查集、图、图的着色、二分图

题目、示例与约束

给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

 

示例 1：

输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

示例 2：

输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

示例 3：

输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false

 

提示：

  • 1 <= n <= 2000
  • 0 <= dislikes.length <= 104
  • dislikes[i].length == 2
  • 1 <= dislikes[i][j] <= n
  • ai < bi
  • dislikes 中每一组都 不同

 

方法一：染色法 · Go 实现

思考

互讨厌的人不能同组，即嫌恶图是否二分。 n ≤ 2000 ，染色 DFS 即可：相邻必须异色，遇同色则失败。

对每个未染色点染成 1 ，沿边染成 3 − c 。全部连通块都成功则可以划分。

我们用两种颜色对图进行染色，如果可以完成染色，那么就说明可以将所有人分进两组。

具体的染色方法如下：

  • 初始化所有人的颜色为 0 ，表示还没有染色。
  • 遍历所有人，如果当前人没有染色，那么就用颜色 1 对其进行染色，然后将其所有不喜欢的人用颜色 2 进行染色。如果染色过程中出现了冲突，那么就说明无法将所有人分进两组，返回 false。
  • 如果所有人都染色成功，那么就说明可以将所有人分进两组，返回 true。

时间复杂度 O ( n + m ) ，其中 n , m 分别是人数和不喜欢的关系数。

go
func possibleBipartition(n int, dislikes [][]int) bool {
	g := make([][]int, n)
	for _, e := range dislikes {
		a, b := e[0]-1, e[1]-1
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	color := make([]int, n)
	var dfs func(int, int) bool
	dfs = func(i, c int) bool {
		color[i] = c
		for _, j := range g[i] {
			if color[j] == c {
				return false
			}
			if color[j] == 0 && !dfs(j, 3-c) {
				return false
			}
		}
		return true
	}
	for i, c := range color {
		if c == 0 && !dfs(i, 1) {
			return false
		}
	}
	return true
}
方法二：并查集 · Go 实现

思考

方法一已经用显式栈完成染色。并查集不保存颜色，而是把必须同组的人合并：一个人讨厌的所有对象应当彼此同组，并且不能和这个人自己同组。若发现自己与某个讨厌对象已经在同一集合则失败，否则把这些讨厌对象合并到同一代表下。

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。 它支持两种操作：

  1. 查找（Find）：确定某个元素处于哪个子集，单次操作时间复杂度 O ( α ( n ) )
  2. 合并（Union）：将两个子集合并成一个集合，单次操作时间复杂度 O ( α ( n ) )

其中 α 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

以下是并查集的常用模板，需要熟练掌握。其中：

  • n 表示节点数
  • p 存储每个点的父节点，初始时每个点的父节点都是自己
  • size 只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量
  • find(x) 函数用于查找 x 所在集合的祖宗节点
  • union(a, b) 函数用于合并 a 和 b 所在的集合
python
p = list(range(n))
size = [1] * n


def find(x):
    if p[x] != x:
        # 路径压缩
        p[x] = find(p[x])
    return p[x]


def union(a, b):
    pa, pb = find(a), find(b)
    if pa == pb:
        return
    p[pa] = pb
    size[pb] += size[pa]

对于本题，我们遍历每一个人，他与他不喜欢的人不应该在同一个集合中，如果在同一个集合中，就产生了冲突，直接返回 false。如果没有冲突，那么就将他所有不喜欢的人合并到同一个集合中。

遍历结束，说明没有冲突，返回 true。

时间复杂度 O ( n + m × α ( n ) ) 。

go
func possibleBipartition(n int, dislikes [][]int) bool {
	p := make([]int, n)
	g := make([][]int, n)
	for i := range p {
		p[i] = i
	}
	for _, e := range dislikes {
		a, b := e[0]-1, e[1]-1
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for i := 0; i < n; i++ {
		for _, j := range g[i] {
			if find(i) == find(j) {
				return false
			}
			p[find(j)] = find(g[i][0])
		}
	}
	return true
}
方法三：显式栈染色 · Go 实现

思考

互不喜欢的人不能同组，嫌恶关系构成无向图，问它是否二分。 n ≤ 2000 ，沿一条嫌恶链递归时，调用深度等于人数，链长达到 1000 就会超出 Python 的递归上限。二分图等价于能用两种颜色染色且每条边两端异色。因此用栈扩展连通块：未染色的人染成 1 后入栈，弹出时若邻居已是同色则失败，若尚未染色就染成 3 减去当前颜色再入栈。每个连通块都染完则可以分组。

用颜色 0 、 1 、 2 表示未染色和两组。输入编号先减 1 ，图按下标 0 存放。对每个颜色仍为 0 的人，染成 1 并压入栈。弹出 i 时检查每个邻居 j ：若 j 与 i 同色，返回 false；若 j 还没染色，染成 3 减去 i 的颜色并压入栈。所有人都处理完则返回 true。

时间复杂度 O ( n + m ) ，空间复杂度 O ( n + m ) ，其中 n 和 m 分别是人数和不喜欢的关系数。

go
func possibleBipartition(n int, dislikes [][]int) bool {
	g := make([][]int, n)
	for _, e := range dislikes {
		a, b := e[0]-1, e[1]-1
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	color := make([]int, n)
	for start := 0; start < n; start++ {
		if color[start] != 0 {
			continue
		}
		color[start] = 1
		stk := []int{start}
		for len(stk) > 0 {
			i := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			for _, j := range g[i] {
				if color[j] == color[i] {
					return false
				}
				if color[j] == 0 {
					color[j] = 3 - color[i]
					stk = append(stk, j)
				}
			}
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

924. 尽量减少恶意软件的传播 ​

困难1 种解法

标签：深度优先搜索、广度优先搜索、并查集、图、数组、哈希表

题目、示例与约束

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。 

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

 

示例 1：

输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0

示例 2：

输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出：0

示例 3：

输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：1

 

提示：

  • n == graph.length
  • n == graph[i].length
  • 2 <= n <= 300
  • graph[i][j] == 0 或 1.
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1 <= initial.length <= n
  • 0 <= initial[i] <= n - 1
  • initial 中所有整数均不重复
方法一：并查集 · Go 实现

思考

删掉一个初始感染点，使最终感染最少。感染沿连通块传播：一块里若有两个及以上初始点，删一个仍会被另一点感染；只有恰好一个初始点的块，删掉它能拯救整块。

并查集求出分量大小与各块初始点数，在 c n t [ r o o t ] = 1 的点中选能拯救最多（并列取编号最小）者；若没有这种块，返回 i n i t i a l 的最小值。

根据题目描述，如果初始时有若干个节点属于同一个连通分量，那么一共可以分为三种情况：

  1. 这些节点中没有一个节点被感染
  2. 这些节点中只有一个节点被感染
  3. 这些节点中有多个节点被感染

我们要考虑的是，移除某个感染节点后，剩下的节点中被感染的节点数最少。

情况一没有被感染的节点，不需要考虑；情况二只有一个节点被感染，那么移除这个节点后，该连通分量中的其他节点都不会被感染；情况三有多个节点被感染，那么移除任意一个感染节点后，该连通分量中的其他节点还是会被感染，所以我们只需要考虑情况二。

我们利用并查集 u f 维护节点的连通关系，用一个变量 a n s 记录答案，用一个变量 m x 记录当前能减少感染的最大节点数，初始时 a n s = n , m x = 0 。

然后遍历数组 i n i t i a l ，用一个哈希表或者一个长度为 n 的数组 c n t 统计每个连通分量中被感染节点的个数。

接下来，我们再遍历数组 i n i t i a l ，对于每个节点 x ，我们找到其所在的连通分量的根节点 r o o t ，如果该连通分量中只有一个被感染节点，即 c n t [ r o o t ] = 1 ，我们就更新答案，更新的条件是该连通分量中的节点数 s z 大于 m x 或者 s z 等于 m x 且 x 的值小于 a n s 。

最后，如果 a n s 没有被更新，说明所有的连通分量中都有多个被感染节点，那么我们返回 i n i t i a l 中的最小值，否则返回 a n s 。

时间复杂度 O ( n 2 × α ( n ) ) ，空间复杂度 O ( n ) 。其中 n 是节点的个数，而 α ( n ) 是 Ackermann 函数的反函数。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func (uf *unionFind) getSize(root int) int {
	return uf.size[root]
}

func minMalwareSpread(graph [][]int, initial []int) int {
	n := len(graph)
	uf := newUnionFind(n)
	for i := range graph {
		for j := i + 1; j < n; j++ {
			if graph[i][j] == 1 {
				uf.union(i, j)
			}
		}
	}
	cnt := make([]int, n)
	ans, mx := n, 0
	for _, x := range initial {
		cnt[uf.find(x)]++
	}
	for _, x := range initial {
		root := uf.find(x)
		if cnt[root] == 1 {
			sz := uf.getSize(root)
			if sz > mx || sz == mx && x < ans {
				ans, mx = x, sz
			}
		}
	}
	if ans == n {
		return slices.Min(initial)
	}
	return ans
}

力扣原题 · Doocs 题解来源

928. 尽量减少恶意软件的传播 II ​

困难1 种解法

标签：深度优先搜索、广度优先搜索、并查集、图、数组、哈希表

题目、示例与约束

给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从 initial 中 删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

 

示例 1：

输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0

示例 2：

输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
输出：1

示例 3：

输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：1

 

提示：

  • n == graph.length
  • n == graph[i].length
  • 2 <= n <= 300
  • graph[i][j] 是 0 或 1.
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1 <= initial.length < n
  • 0 <= initial[i] <= n - 1
  •  initial 中每个整数都不同
方法一：并查集 · Go 实现

思考

与上一题不同，被删节点不再传播，且其余初始点仍会感染邻居。先把所有干净节点按边合并成连通块，再看每个初始点触及哪些干净块。

一块若只被一个初始点碰到，删掉该点即可拯救整块。对每个初始点累加其独占块的大小，取拯救最多（并列取编号最小）的点。

我们可以使用并查集，将所有不在 i n i t i a l 中的节点，并且满足 g r a p h [ i ] [ j ] = 1 的节点 ( i , j ) 进行合并。

接下来，我们创建一个哈希表 g ，其中 g [ i ] 表示所有与节点 i 相连的连通分量的根节点。我们还需要一个计数器 c n t ，用来统计每个根节点被多少个初始节点感染。

对于每个初始时被感染的节点 i ，我们遍历所有与节点 i 相连的节点 j ，如果节点 j 不在 i n i t i a l 中，我们将节点 j 的根节点加入到集合 g [ i ] 中。同时，我们统计每个根节点被多少个初始节点感染，将结果保存到计数器 c n t 中。

然后，我们用一个变量 a n s 记录答案，用 m x 记录最多可以减少的被感染节点的数量。初始时 a n s = 0 , m x = − 1 。

遍历所有初始时被感染的节点，对于每个节点 i ，我们遍历 g [ i ] 中的所有根节点，如果根节点只被一个初始节点感染，我们累加这个根节点所在的连通分量的大小到 t 中。如果 t > m x 或者 t = m x 且 i < a n s ，我们更新 a n s = i , m x = t 。

最后返回 a n s 即可。

时间复杂度 O ( n 2 × α ( n ) ) ，空间复杂度 O ( n 2 ) 。其中 n 是节点的数量，而 α ( n ) 是 Ackermann 函数的反函数。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func (uf *unionFind) getSize(root int) int {
	return uf.size[root]
}

func minMalwareSpread(graph [][]int, initial []int) int {
	n := len(graph)
	s := make([]bool, n)
	for _, i := range initial {
		s[i] = true
	}
	uf := newUnionFind(n)
	for i := range graph {
		if !s[i] {
			for j := i + 1; j < n; j++ {
				if graph[i][j] == 1 && !s[j] {
					uf.union(i, j)
				}
			}
		}
	}
	g := make([]map[int]bool, n)
	for _, i := range initial {
		g[i] = map[int]bool{}
	}
	cnt := make([]int, n)
	for _, i := range initial {
		for j := 0; j < n; j++ {
			if !s[j] && graph[i][j] == 1 {
				g[i][uf.find(j)] = true
			}
		}
		for root := range g[i] {
			cnt[root]++
		}
	}
	ans, mx := 0, -1
	for _, i := range initial {
		t := 0
		for root := range g[i] {
			if cnt[root] == 1 {
				t += uf.getSize(root)
			}
		}
		if t > mx || t == mx && i < ans {
			ans, mx = i, t
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

947. 移除最多的同行或同列石头 ​

中等2 种解法

标签：深度优先搜索、并查集、图、哈希表、二分图

题目、示例与约束

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

 

示例 1：

输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。

示例 2：

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。

示例 3：

输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。

 

提示：

  • 1 <= stones.length <= 1000
  • 0 <= xi, yi <= 104
  • 不会有两块石头放在同一个坐标点上
方法一：并查集 · Go 实现

思考

同行或同列的石头可互相到达，一个连通块最后只能留一块，故答案为 n 减去连通块数。两两检查是否同行同列并入并查集，成功合并的次数即为可移除数。

我们可以用并查集维护石头之间的关系。如果两块石头在同一行或同一列，我们就认为它们之间有关系，可以通过并查集将它们连接起来。最后，我们统计并查集中有多少个连通分量，这个数值就是可以剩余的石头的数量，那么总共可以移除的石头数量就是石头总数减去剩余的石头数量。我们也可以在合并的时候，记录成功合并的次数，这个次数就是可以移除的石头的数量。

时间复杂度 O ( n 2 × α ( n ) ) ，空间复杂度 O ( n ) 。其中 n 为石头的数量。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func removeStones(stones [][]int) (ans int) {
	n := len(stones)
	uf := newUnionFind(n)
	for i, s1 := range stones {
		for j, s2 := range stones[:i] {
			if s1[0] == s2[0] || s1[1] == s2[1] {
				if uf.union(i, j) {
					ans++
				}
			}
		}
	}
	return
}
方法二：并查集（优化） · Go 实现

思考

方法一对石头两两连边，为平方级。行与列本身可作为并查集元素：把列加上偏移后与行合并，同一行或同一列自动连通。剩余块数等于不同行根的个数。

我们可以将石头的纵坐标加上一个偏移量，这样就可以将横坐标和纵坐标统一起来，然后用并查集维护横坐标和纵坐标之间的关系。

我们遍历每一块石头，将横坐标与纵坐标进行合并。

最后，我们再遍历所有石头，将每块石头的横坐标的根节点放到一个集合中，那么这个集合的数量就是可以剩余的石头的数量，总共可以移除的石头数量就是石头总数减去剩余的石头数量。

时间复杂度 O ( n × α ( m ) ) ，空间复杂度 O ( m ) 。其中 n 和 m 分别为石头的数量和横纵坐标的最大值。

go
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func removeStones(stones [][]int) (ans int) {
	m := 10001
	uf := newUnionFind(m << 1)
	for _, st := range stones {
		uf.union(st[0], st[1]+m)
	}
	s := map[int]bool{}
	for _, st := range stones {
		s[uf.find(st[0])] = true
	}
	return len(stones) - len(s)
}

力扣原题 · Doocs 题解来源

952. 按公因数计算最大组件大小 ​

困难1 种解法

标签：并查集、数组、哈希表、数学、数论、质因数分解

题目、示例与约束

给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：

  • 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
  • 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。

返回 图中最大连通组件的大小 。

 

示例 1：

输入：nums = [4,6,15,35]
输出：4

示例 2：

输入：nums = [20,50,9,63]
输出：2

示例 3：

输入：nums = [2,3,6,7,4,12,21,39]
输出：8

 

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 105
  • nums 中所有值都 不同
方法一：数学 + 并查集 · Go 实现

思考

有公因数大于 1 的数相连，求最大连通块。两两求 gcd 为平方级， n ≤ 2 × 10 4 不可行。把每个数与其所有因数在并查集中合并，同一因数的数自然连通。最后统计各数根结点的频数最大值。

利用“试除法”，对 n u m s 中的每个数 v 分解因数，然后将每个因数 i 与 v 合并， v / i 与 v 合并。此过程用并查集来维护连通分量。

最后，遍历 n u m s 中每个数 v ，找出所在的连通分量，出现次数最多的连通分量就是所求的答案。

go
func largestComponentSize(nums []int) int {
	m := slices.Max(nums)
	p := make([]int, m+1)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	union := func(a, b int) {
		pa, pb := find(a), find(b)
		if pa != pb {
			p[pa] = pb
		}
	}
	for _, v := range nums {
		i := 2
		for i <= v/i {
			if v%i == 0 {
				union(v, i)
				union(v, v/i)
			}
			i++
		}
	}
	cnt := make([]int, m+1)
	for _, v := range nums {
		t := find(v)
		cnt[t]++
	}
	return slices.Max(cnt)
}

力扣原题 · Doocs 题解来源

959. 由斜杠划分区域 ​

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、矩阵、平面图

题目、示例与约束

在由 1 x 1 方格组成的 n x n 网格 grid 中，每个 1 x 1 方块由 '/'、'\' 或空格构成。这些字符会将方块划分为一些共边的区域。

给定网格 grid 表示为一个字符串数组，返回 区域的数量 。

请注意，反斜杠字符是转义的，因此 '\' 用 '\\' 表示。

 

示例 1：

输入：grid = [" /","/ "]
输出：2

示例 2：

输入：grid = [" /","  "]
输出：1

示例 3：

输入：grid = ["/\\","\\/"]
输出：5
解释：回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。

 

提示：

  • n == grid.length == grid[i].length
  • 1 <= n <= 30
  • grid[i][j] 是 '/'、'\'、或 ' '
方法一 · Go 实现

思考

斜线把格子切成若干区域， n ≤ 30 。把每个格子分成上下左右四块三角形，相邻块在无墙处合并：格子内部按 '/'、'\\' 或空格连边，格子之间沿共享边相连。并查集维护块数，初始 4 n 2 ，每次成功合并减一。

go
func regionsBySlashes(grid []string) int {
	n := len(grid)
	size := n * n * 4
	p := make([]int, size)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	union := func(a, b int) {
		pa, pb := find(a), find(b)
		if pa == pb {
			return
		}
		p[pa] = pb
		size--
	}
	for i, row := range grid {
		for j, v := range row {
			k := i*n + j
			if i < n-1 {
				union(4*k+2, (k+n)*4)
			}
			if j < n-1 {
				union(4*k+1, (k+1)*4+3)
			}
			if v == '/' {
				union(4*k, 4*k+3)
				union(4*k+1, 4*k+2)
			} else if v == '\\' {
				union(4*k, 4*k+1)
				union(4*k+2, 4*k+3)
			} else {
				union(4*k, 4*k+1)
				union(4*k+1, 4*k+2)
				union(4*k+2, 4*k+3)
			}
		}
	}
	return size
}

力扣原题 · Doocs 题解来源

990. 等式方程的可满足性 ​

中等1 种解法

标签：并查集、图、数组、字符串

题目、示例与约束

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 

 

示例 1：

输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2：

输入：["b==a","a==b"]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

示例 3：

输入：["a==b","b==c","a==c"]
输出：true

示例 4：

输入：["a==b","b!=c","c==a"]
输出：false

示例 5：

输入：["c==c","b==d","x!=z"]
输出：true

 

提示：

  1. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3] 是小写字母
  4. equations[i][1] 要么是 '='，要么是 '!'
  5. equations[i][2] 是 '='
方法一 · Go 实现

思考

若干形如 a == b / a ! = b 的方程，判断能否同时成立。相等具有传递性，应先全部合并。并查集处理所有 ==，再检查每条 != 的两端是否已在同一连通块；若是则矛盾。

go
func equationsPossible(equations []string) bool {
	p := make([]int, 26)
	for i := 1; i < 26; i++ {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, e := range equations {
		a, b := int(e[0]-'a'), int(e[3]-'a')
		if e[1] == '=' {
			p[find(a)] = find(b)
		}
	}
	for _, e := range equations {
		a, b := int(e[0]-'a'), int(e[3]-'a')
		if e[1] == '!' && find(a) == find(b) {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

1020. 飞地的数量 ​

中等3 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

 

示例 1：

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid[i][j] 的值为 0 或 1
方法一：DFS · Go 实现

思考

对每一块陆地判断是否能走到边界，最坏要对整张图反复搜索， m , n ≤ 500 时常数不佳。飞地是无法走到边界的陆地，其补集恰为「与边界连通的陆地」。

从四条边界上的 1 出发淹没所有能走到的陆地，剩下的 1 便无法离岛。

深度优先搜索即可完成淹没，最后统计网格中剩余 1 的个数。

我们可以从边界上的陆地开始进行深度优先搜索，将所有与边界相连的陆地都标记为 0 。最后，统计剩余的 1 的个数，即为答案。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别为矩阵的行数和列数。

go
func numEnclaves(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j int)
	dfs = func(i, j int) {
		grid[i][j] = 0
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
				dfs(x, y)
			}
		}
	}
	for j := 0; j < n; j++ {
		for _, i := range [2]int{0, m - 1} {
			if grid[i][j] == 1 {
				dfs(i, j)
			}
		}
	}
	for i := 0; i < m; i++ {
		for _, j := range [2]int{0, n - 1} {
			if grid[i][j] == 1 {
				dfs(i, j)
			}
		}
	}
	for _, row := range grid {
		for _, x := range row {
			ans += x
		}
	}
	return
}
方法二：BFS · Go 实现

思考

方法一已经用显式栈从边界淹没陆地。连通性不依赖搜索顺序，也可以把边界陆地放入队列按层扩展。

队列弹出后同样把四个方向上的 1 标成 0 。四条边界处理完后，剩下的 1 仍是飞地。

我们也可以使用广度优先搜索的方法，将边界上的陆地入队，然后进行广度优先搜索，将所有与边界相连的陆地都标记为 0 。最后，统计剩余的 1 的个数，即为答案。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别为矩阵的行数和列数。

go
func numEnclaves(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	q := [][2]int{}
	for j := 0; j < n; j++ {
		for _, i := range []int{0, m - 1} {
			if grid[i][j] == 1 {
				q = append(q, [2]int{i, j})
				grid[i][j] = 0
			}
		}
	}
	for i := 0; i < m; i++ {
		for _, j := range []int{0, n - 1} {
			if grid[i][j] == 1 {
				q = append(q, [2]int{i, j})
				grid[i][j] = 0
			}
		}
	}
	for len(q) > 0 {
		i, j := q[0][0], q[0][1]
		q = q[1:]
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
				q = append(q, [2]int{x, y})
				grid[x][y] = 0
			}
		}
	}
	for _, row := range grid {
		for _, x := range row {
			ans += x
		}
	}
	return
}
方法三：显式栈 · Go 实现

思考

飞地是到不了边界的陆地。对每一块陆地单独判断能否离岛，会在同一张图上反复搜索。 m , n ≤ 500 ，补集是「与边界连通的陆地」。

从边界上的 1 递归淹没时，一条贴着边界蜿蜒的陆地链会长到上千格，调用栈会先被用尽。

淹没只要求把能走到的格子标成 0 ，不依赖递归返回值。

因此用显式栈保存待淹没的格子。弹出后把四个方向上仍为 1 的邻居标 0 并入栈。四条边界都处理完后，网格里剩下的 1 就是飞地。

从四条边界上的陆地出发，用显式栈淹没所有能走到的陆地，将其标为 0 。最后统计网格中剩余 1 的个数。

时间复杂度 O ( m × n ) ，空间复杂度 O ( m × n ) 。其中 m 和 n 分别为矩阵的行数和列数。

go
func numEnclaves(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	flood := func(i, j int) {
		grid[i][j] = 0
		stk := [][2]int{{i, j}}
		for len(stk) > 0 {
			cur := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			for k := 0; k < 4; k++ {
				x, y := cur[0]+dirs[k], cur[1]+dirs[k+1]
				if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
					grid[x][y] = 0
					stk = append(stk, [2]int{x, y})
				}
			}
		}
	}
	for j := 0; j < n; j++ {
		for _, i := range [2]int{0, m - 1} {
			if grid[i][j] == 1 {
				flood(i, j)
			}
		}
	}
	for i := 0; i < m; i++ {
		for _, j := range [2]int{0, n - 1} {
			if grid[i][j] == 1 {
				flood(i, j)
			}
		}
	}
	for _, row := range grid {
		for _, x := range row {
			ans += x
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1061. 按字典序排列最小的等效字符串 ​

中等1 种解法

标签：并查集、字符串

题目、示例与约束

给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。

其中  s1[i] 和 s2[i]  是一组等价字符。

  • 举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。

等价字符遵循任何等价关系的一般规则：

  •  自反性 ：'a' == 'a'
  •  对称性 ：'a' == 'b' 则必定有 'b' == 'a'
  •  传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'

例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串

利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。

 

示例 1：

输入：s1 = "parker", s2 = "morris", baseStr = "parser"
输出："makkek"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。

示例 2：

输入：s1 = "hello", s2 = "world", baseStr = "hold"
输出："hdld"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd'，最后答案为 "hdld"。

示例 3：

输入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
输出："aauaaaaada"
解释：我们可以把 A 和 B 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 组，因此 S 中除了 'u' 和 'd' 之外的所有字母都转化成了 'a'，最后答案为 "aauaaaaada"。

 

提示：

  • 1 <= s1.length, s2.length, baseStr <= 1000
  • s1.length == s2.length
  • 字符串s1, s2, and baseStr 仅由从 'a' 到 'z' 的小写英文字母组成。
方法一：并查集 · Go 实现

思考

等价关系可传递，要把 b a s e S t r 每个字符换成其所在等价类的最小字母。 26 个字母用并查集维护连通分量即可。

合并 s 1 [ i ] 与 s 2 [ i ] 时，总是把较大的根挂到较小的根上，使代表元即字典序最小字符。

最后对 b a s e S t r 每个字符输出其根对应的字母。

我们可以使用并查集来处理等价字符的关系。每个字符可以看作一个节点，等价关系可以看作是连接这些节点的边。通过并查集，我们可以将所有等价的字符归为一类，并且在查询时能够快速找到每个字符的代表元素。我们在进行合并操作时，始终将代表元素设置为字典序最小的字符，这样可以确保最终得到的字符串是按字典序排列的最小等价字符串。

时间复杂度 O ( ( n + m ) × log ⁡ | Σ | ) ，空间复杂度 O ( | Σ | ) 。其中 n 是字符串 s 1 和 s 2 的长度，而 m 是字符串 b a s e S t r 的长度，而 | Σ | 是字符集的大小，本题中 | Σ | = 26 。

go
func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
	p := make([]int, 26)
	for i := 0; i < 26; i++ {
		p[i] = i
	}

	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}

	for i := 0; i < len(s1); i++ {
		x := int(s1[i] - 'a')
		y := int(s2[i] - 'a')
		px := find(x)
		py := find(y)
		if px < py {
			p[py] = px
		} else {
			p[px] = py
		}
	}

	var s []byte
	for i := 0; i < len(baseStr); i++ {
		s = append(s, byte('a'+find(int(baseStr[i]-'a'))))
	}

	return string(s)
}

力扣原题 · Doocs 题解来源

继续阅读