LeetCode Go · 回溯与搜索（4）

来源与许可

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

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

1718. 构建字典序最大的可行序列

中等1 种解法

标签：数组、回溯

题目、示例与约束

给你一个整数 n ，请你找到满足下面条件的一个序列：

整数 1 在序列中只出现一次。
2 到 n 之间每个整数都恰好出现两次。
对于每个 2 到 n 之间的整数 i ，两个 i 之间出现的距离恰好为 i 。

序列里面两个数 a[i] 和 a[j] 之间的距离，我们定义为它们下标绝对值之差 |j - i| 。

请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下，一定存在解。

一个序列 a 被认为比序列 b （两者长度相同）字典序更大的条件是： a 和 b 中第一个不一样的数字处，a 序列的数字比 b 序列的数字大。比方说，[0,1,9,0] 比 [0,1,5,6] 字典序更大，因为第一个不同的位置是第三个数字，且 9 比 5 大。

示例 1：

输入：n = 3
输出：[3,1,2,3,2]
解释：[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。

示例 2：

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

提示：

1 <= n <= 20

方法一 · Go 实现

思考

长度为 $2 n - 1$ 的序列中， $1$ 出现一次， $2. . n$ 各出现两次且间距恰为该数。 $n$ 较小，可回溯搜索。

字典序最大要求优先放置较大的数。从左到右填空位，对每个空位从 $n$ 试到 $2$ ，再试 $1$ 。

$path$ 记录已填值， $cnt$ 记录剩余次数。数 $i$ 占用 $u$ 与 $u + i$ ；一旦填满 $2 n - 1$ 个位置即得到题目保证存在的解。

func constructDistancedSequence(n int) []int {
	path := make([]int, n*2)
	cnt := make([]int, n*2)
	for i := range cnt {
		cnt[i] = 2
	}
	cnt[1] = 1
	var dfs func(u int) bool
	dfs = func(u int) bool {
		if u == n*2 {
			return true
		}
		if path[u] > 0 {
			return dfs(u + 1)
		}
		for i := n; i > 1; i-- {
			if cnt[i] > 0 && u+i < n*2 && path[u+i] == 0 {
				cnt[i] = 0
				path[u], path[u+i] = i, i
				if dfs(u + 1) {
					return true
				}
				cnt[i] = 2
				path[u], path[u+i] = 0, 0
			}
		}
		if cnt[1] > 0 {
			cnt[1] = 0
			path[u] = 1
			if dfs(u + 1) {
				return true
			}
			cnt[1] = 1
			path[u] = 0
		}
		return false
	}
	dfs(1)
	return path[1:]
}

力扣原题 · Doocs 题解来源

1730. 获取食物的最短路径 🔒

中等1 种解法

标签：广度优先搜索、数组、矩阵

题目、示例与约束

你现在很饿，想要尽快找东西吃。你需要找到最短的路径到达一个食物所在的格子。

给定一个 m x n 的字符矩阵 grid ，包含下列不同类型的格子：

'*' 是你的位置。矩阵中有且只有一个 '*' 格子。
'#' 是食物。矩阵中可能存在多个食物。
'O' 是空地，你可以穿过这些格子。
'X' 是障碍，你不可以穿过这些格子。

返回你到任意食物的最短路径的长度。如果不存在你到任意食物的路径，返回 -1。

示例 1:

输入： grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]
输出： 3
解释： 要拿到食物，你需要走 3 步。

Example 2:

输入： grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]
输出： -1
解释： 你不可能拿到食物。

示例 3:

输入: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]]
输出: 6
解释: 这里有多个食物。拿到下边的食物仅需走 6 步。

示例 4：

输入：grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["O","O","O","O","O","O","O","O"]]
输出：5

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[row][col] 是 '*'、 'X'、 'O' 或 '#' 。
grid 中有且只有一个 '*' 。

方法一：BFS · Go 实现

思考

网格中从唯一的 $*$ 走到最近的 $#$ ，障碍不可穿越。最短格路适合 BFS。

先定位 $*$ 入队，按层扩展四邻：遇到 $#$ 返回当前层数，空地标为障碍以免重复入队。队列空则不可达。

根据题意，我们需要从 * 出发，找到最近的 #，返回最短路径长度。

首先，我们遍历整个二维数组，找到 * 的位置，将其作为 BFS 的起点，放入队列中。

然后，我们开始 BFS，遍历队列中的元素，每次遍历到一个元素，我们将其上下左右四个方向的元素加入队列中，直到遇到 #，返回当前层数。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (1)$ 。其中 $m$ 和 $n$ 分别为二维数组的行数和列数。

func getFood(grid [][]byte) (ans int) {
	m, n := len(grid), len(grid[0])
	dirs := []int{-1, 0, 1, 0, -1}
	type pair struct{ i, j int }
	q := []pair{}
	for i, x := 0, 1; i < m && x == 1; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '*' {
				q = append(q, pair{i, j})
				x = 0
				break
			}
		}
	}
	for len(q) > 0 {
		ans++
		for t := len(q); t > 0; t-- {
			p := q[0]
			q = q[1:]
			for k := 0; k < 4; k++ {
				x, y := p.i+dirs[k], p.j+dirs[k+1]
				if x >= 0 && x < m && y >= 0 && y < n {
					if grid[x][y] == '#' {
						return ans
					}
					if grid[x][y] == 'O' {
						grid[x][y] = 'X'
						q = append(q, pair{x, y})
					}
				}
			}
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1743. 从相邻元素对还原数组

中等2 种解法

标签：深度优先搜索、数组、哈希表

题目、示例与约束

存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。

给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [u_i, v_i] 表示元素 u_i 和 v_i 在 nums 中相邻。

题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。

返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。

示例 1：

输入：adjacentPairs = [[2,1],[3,4],[3,2]]
输出：[1,2,3,4]
解释：数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。

示例 2：

输入：adjacentPairs = [[4,-2],[1,4],[-3,1]]
输出：[-2,4,1,-3]
解释：数组中可能存在负数。
另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。

示例 3：

输入：adjacentPairs = [[100000,-100000]]
输出：[100000,-100000]

提示：

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 10⁵
-10⁵ <= nums[i], u_i, v_i <= 10⁵
题目数据保证存在一些以 adjacentPairs 作为元素对的数组 nums

方法一：哈希表 · Go 实现

思考

相邻对构成一条路径图，两端度数为 $1$ 。从任一端点沿邻接顺序走即可还原。

建无向邻接表，找到度为 $1$ 的点作为 $a n s [0]$ ，其唯一邻居为 $a n s [1]$ 。之后每个位置取邻居中不等于再前一个的那个。

从度为一的点开始遍历图，可以用 DFS，也可以直接遍历。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。

func restoreArray(adjacentPairs [][]int) []int {
	n := len(adjacentPairs) + 1
	g := map[int][]int{}
	for _, e := range adjacentPairs {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	ans := make([]int, n)
	for k, v := range g {
		if len(v) == 1 {
			ans[0] = k
			ans[1] = v[0]
			break
		}
	}
	for i := 2; i < n; i++ {
		v := g[ans[i-1]]
		ans[i] = v[0]
		if v[0] == ans[i-2] {
			ans[i] = v[1]
		}
	}
	return ans
}

方法二：DFS · Go 实现

思考

方法一按线性邻接递推。也可用 DFS 从度为 $1$ 的端点沿边深入，访问顺序即为还原数组，适合写成递归。

从度为 $1$ 的端点出发，沿邻接表深度优先遍历还原数组。

func restoreArray(adjacentPairs [][]int) []int {
	g := map[int][]int{}
	for _, e := range adjacentPairs {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	ans := []int{}
	var dfs func(i, fa int)
	dfs = func(i, fa int) {
		ans = append(ans, i)
		for _, j := range g[i] {
			if j != fa {
				dfs(j, i)
			}
		}
	}
	for i, v := range g {
		if len(v) == 1 {
			dfs(i, 1000000)
			break
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1765. 地图中的最高点

中等2 种解法

标签：广度优先搜索、数组、矩阵

题目、示例与约束

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由陆地和水域单元格组成的地图。

如果 isWater[i][j] == 0 ，格子 (i, j) 是一个陆地格子。
如果 isWater[i][j] == 1 ，格子 (i, j) 是一个水域格子。

你需要按照如下规则给每个单元格安排高度：

每个格子的高度都必须是非负的。
如果一个格子是水域，那么它的高度必须为 0 。
任意相邻的格子高度差至多为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）

找到一种安排高度的方案，使得矩阵中的最高高度值最大。

请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

示例 1：

输入：isWater = [[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。

示例 2：

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。

提示：

m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] 要么是 0 ，要么是 1 。
至少有 1 个水域格子。

注意：本题与 542 题相同。

方法一：BFS · Go 实现

思考

水域高度必须为 $0$ ，相邻高度差至多为 $1$ ，且希望陆地点尽量高。高度实际上是到最近水域的距离。

多源 BFS：所有水域入队并置 $0$ ，弹出时把未访问邻格设为当前高度加一。距离场即为所求高度图。

根据题目描述，水域的高度必须是 $0$ ，而任意相邻格子的高度差至多为 $1$ 。因此，我们可以从所有水域格子出发，用 BFS 搜索相邻且未访问过的格子，将其高度置为当前格子的高度再加一。

最后返回结果矩阵即可。

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

func highestPeak(isWater [][]int) [][]int {
	m, n := len(isWater), len(isWater[0])
	ans := make([][]int, m)
	type pair struct{ i, j int }
	q := []pair{}
	for i, row := range isWater {
		ans[i] = make([]int, n)
		for j, v := range row {
			ans[i][j] = v - 1
			if v == 1 {
				q = append(q, pair{i, j})
			}
		}
	}
	dirs := []int{-1, 0, 1, 0, -1}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		i, j := p.i, p.j
		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[x][y] == -1 {
				ans[x][y] = ans[i][j] + 1
				q = append(q, pair{x, y})
			}
		}
	}
	return ans
}

方法二 · Go 实现

思考

方法二仍是多源 BFS，只是按层用 $for$ 弹出当前队列长度，写法与方法一等价，复杂度不变。

func highestPeak(isWater [][]int) [][]int {
	m, n := len(isWater), len(isWater[0])
	ans := make([][]int, m)
	type pair struct{ i, j int }
	q := []pair{}
	for i, row := range isWater {
		ans[i] = make([]int, n)
		for j, v := range row {
			ans[i][j] = v - 1
			if v == 1 {
				q = append(q, pair{i, j})
			}
		}
	}
	dirs := []int{-1, 0, 1, 0, -1}
	for len(q) > 0 {
		for t := len(q); t > 0; t-- {
			p := q[0]
			q = q[1:]
			i, j := p.i, p.j
			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[x][y] == -1 {
					ans[x][y] = ans[i][j] + 1
					q = append(q, pair{x, y})
				}
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1778. 未知网格中的最短路径 🔒

中等1 种解法

标签：深度优先搜索、广度优先搜索、数组、交互、矩阵

题目、示例与约束

这是一个交互式的问题。

一个未知的网格里有一个机器人，你需要让机器人从起点走到终点。这个网格的大小是 m x n，网格中的每个位置只会是可通行和不可通行两种状态。题目保证机器人的起点和终点不同，且都是可通行的。

你需要找到起点到终点的最短路径，然而你不知道网格的大小、起点和终点。你只能向 GridMaster 对象查询。

GridMaster有这些方法：

boolean canMove(char direction) 当机器人能向对应方向移动时，返回 true，否则返回 false。
void move(char direction) 把机器人向这个方向移动。如果移动方向上是不可通行的或是网格的边界，则这次移动会被忽略，机器人会待在原地。
boolean isTarget() 如果机器人当前位于终点，返回 true，否则返回 false。

注意上述方法中的direction应该是 {'U','D','L','R'} 中的一个，分别代表上下左右四个方向。

返回机器人的初始位置到终点的最短距离。如果在起点和终点间没有路径联通，返回 -1。

自定义测试用例

测试用例是一个 m x n 的二维矩阵 grid，其中：

grid[i][j] == -1 表明机器人一开始位于位置 (i, j) （即起点）。
grid[i][j] == 0 表明位置 (i, j) 不可通行。
grid[i][j] == 1 表明位置 (i, j) 可以通行.
grid[i][j] == 2 表明位置 (i, j) 是终点.

grid 里恰有一个-1 和一个 2。记住在你的代码中，你对这些信息将一无所知。

示例1：

输入: grid = [[1,2],[-1,0]]
输出: 2
解释: 一种可能的交互过程如下：
The robot is initially standing on cell (1, 0), denoted by the -1.
- master.canMove('U') 返回 true.
- master.canMove('D') 返回false.
- master.canMove('L') 返回 false.
- master.canMove('R') 返回 false.
- master.move('U') 把机器人移动到 (0, 0).
- master.isTarget() 返回 false.
- master.canMove('U') 返回 false.
- master.canMove('D') 返回 true.
- master.canMove('L') 返回 false.
- master.canMove('R') 返回 true.
- master.move('R') 把机器人移动到 (0, 1).
- master.isTarget() 返回 true. 
我们现在知道终点是点 (0, 1)，而且最短的路径是2.

示例2:

输入: grid = [[0,0,-1],[1,1,1],[2,0,0]]
输出: 4
解释: 机器人和终点的最短路径长是4.

示例3:

输入: grid = [[-1,0],[0,2]]
输出: -1
解释: 机器人和终点间没有可通行的路径.

提示：

1 <= n, m <= 500
m == grid.length
n == grid[i].length
grid[i][j] 只可能是 -1, 0, 1 或 2
grid 中 有且只有一个 -1
grid 中 有且只有一个 2

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 探索建图后 BFS 的参考改写。先用显式 DFS 栈驱动机器人，给可达格记录相对坐标；每次退栈执行反向移动，保证机器人返回父格，探索结束回到起点。再在已知可达图上 BFS 求最少步数。V 为可达格数，时间与空间均 O(V)，显式栈可覆盖长通道。平台 GridMaster 的 Go 方法为 CanMove(byte) bool、Move(byte)、IsTarget() bool，方向 U/R/D/L；入口接收 *GridMaster，测试提供完全离线的类型与方法。

出处：Doocs 原题与题解，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；题意、参考及本 Go 改写采用 CC BY-SA 4.0。

// 题意与参考：Doocs LeetCode，CC BY-SA 4.0。
// https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1700-1799/1778.Shortest%20Path%20in%20a%20Hidden%20Grid/README.md
// Go 实现与测试沿用 CC BY-SA 4.0；来源性质见配套说明。
func findShortestPath(master *GridMaster) int {
	type point struct{ x, y int }
	type frame struct {
		p    point
		next int
		back byte
	}
	dirs := []byte{'U', 'R', 'D', 'L'}
	dx := []int{-1, 0, 1, 0}
	dy := []int{0, 1, 0, -1}
	start := point{}
	seen := map[point]bool{start: true}
	stack := []frame{{p: start}}
	target := point{}
	found := master.IsTarget()
	for len(stack) > 0 {
		f := &stack[len(stack)-1]
		if f.next == 4 {
			back := f.back
			stack = stack[:len(stack)-1]
			if back != 0 {
				master.Move(back)
			}
			continue
		}
		d := f.next
		f.next++
		next := point{f.p.x + dx[d], f.p.y + dy[d]}
		if seen[next] || !master.CanMove(dirs[d]) {
			continue
		}
		master.Move(dirs[d])
		seen[next] = true
		if master.IsTarget() {
			target = next
			found = true
		}
		stack = append(stack, frame{p: next, back: dirs[(d+2)%4]})
	}
	if !found {
		return -1
	}
	queue := []point{start}
	dist := map[point]int{start: 0}
	for head := 0; head < len(queue); head++ {
		p := queue[head]
		if p == target {
			return dist[p]
		}
		for d := 0; d < 4; d++ {
			q := point{p.x + dx[d], p.y + dy[d]}
			if _, ok := dist[q]; seen[q] && !ok {
				dist[q] = dist[p] + 1
				queue = append(queue, q)
			}
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1849. 将字符串拆分为递减的连续值

中等1 种解法

标签：字符串、回溯、枚举

题目、示例与约束

给你一个仅由数字组成的字符串 s 。

请你判断能否将 s 拆分成两个或者多个 非空子字符串 ，使子字符串的数值按降序排列，且每两个 相邻子字符串 的数值之差等于 1 。

例如，字符串 s = "0090089" 可以拆分成 ["0090", "089"] ，数值为 [90,89] 。这些数值满足按降序排列，且相邻值相差 1 ，这种拆分方法可行。
另一个例子中，字符串 s = "001" 可以拆分成 ["0", "01"]、["00", "1"] 或 ["0", "0", "1"] 。然而，所有这些拆分方法都不可行，因为对应数值分别是 [0,1]、[0,1] 和 [0,0,1] ，都不满足按降序排列的要求。

如果可以按要求拆分 s ，返回 true ；否则，返回 false 。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：s = "1234"
输出：false
解释：不存在拆分 s 的可行方法。

示例 2：

输入：s = "050043"
输出：true
解释：s 可以拆分为 ["05", "004", "3"] ，对应数值为 [5,4,3] 。
满足按降序排列，且相邻值相差 1 。

示例 3：

输入：s = "9080701"
输出：false
解释：不存在拆分 s 的可行方法。

示例 4：

输入：s = "10009998"
输出：true
解释：s 可以拆分为 ["100", "099", "98"] ，对应数值为 [100,99,98] 。
满足按降序排列，且相邻值相差 1 。

提示：

1 <= s.length <= 20
s 仅由数字组成

方法一：DFS · Go 实现

思考

要把数字串拆成至少两段，对应整数严格递减且相邻差为 $1$ 。前导零合法但数值按去零理解。段的切法是指数级的，但 $n \leq 20$ ，搜索可行。

从左往右枚举当前段的结束位置，累加得到数值 $y$ 。首段任意，其后要求恰好比上一段小 $1$ 。第一段不能吞掉整个串，否则无法拆成两段。DFS 搜到末尾即成功。

我们可以从字符串的第一个字符开始，尝试将其拆分成一个或多个子字符串，然后递归处理剩余的部分。

具体地，我们设计一个函数 $dfs (i, x)$ ，其中 $i$ 表示当前处理到的位置，而 $x$ 表示上一个拆分出的数值。初始时 $x = - 1$ ，表示我们还没有拆分出任何数值。

在 $dfs (i, x)$ 中，我们首先计算当前拆分出的数值 $y$ ，如果 $x = - 1$ ，或者 $x - y = 1$ ，那么我们可以尝试将 $y$ 作为下一个数值，继续递归处理剩余的部分。如果递归的结果为 $true$ ，我们就找到了一种拆分方法，返回 $true$ 。

遍历完所有的拆分方法后，如果没有找到合适的拆分方法，我们返回 $false$ 。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n)$ ，其中 $n$ 是字符串的长度。

func splitString(s string) bool {
	var dfs func(i, x int) bool
	dfs = func(i, x int) bool {
		if i >= len(s) {
			return true
		}
		y := 0
		r := len(s)
		if x < 0 {
			r--
		}
		for j := i; j < r; j++ {
			y = y*10 + int(s[j]-'0')
			if (x < 0 || x-y == 1) && dfs(j+1, y) {
				return true
			}
		}
		return false
	}
	return dfs(0, -1)
}

力扣原题 · Doocs 题解来源

1863. 找出所有子集的异或总和再求和

简单2 种解法

标签：位运算、数组、数学、回溯、组合数学、枚举

题目、示例与约束

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为空，则异或总和为 0 。

例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。

给你一个数组 nums ，请你求出 nums 中每个子集的 异或总和 ，计算并返回这些值相加之和。

注意：在本题中，元素相同的不同子集应多次计数。

数组 a 是数组 b 的一个子集的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

示例 1：

输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2：

输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。

提示：

1 <= nums.length <= 12
1 <= nums[i] <= 20

方法一：二进制枚举 · Go 实现

思考

求所有子集异或和的总和。 $n \leq 12$ ，子集只有 $2^{n}$ 个，枚举可以通过。

用掩码 $i \in [0, 2^{n})$ 表示子集，按位把选中元素异或起来并累加。实现无需递归。

我们可以用二进制枚举的方法，枚举出所有的子集，然后计算每个子集的异或总和。

具体地，我们在 $[0, 2^{n})$ 的范围内枚举 $i$ ，其中 $n$ 是数组 $n u m s$ 的长度。如果 $i$ 的二进制表示的第 $j$ 位为 $1$ ，那么代表着 $n u m s$ 的第 $j$ 个元素在当前枚举的子集中；如果第 $j$ 位为 $0$ ，那么代表着 $n u m s$ 的第 $j$ 个元素不在当前枚举的子集中。我们可以根据 $i$ 的二进制表示，得到当前子集对应的异或总和，将其加到答案中即可。

时间复杂度 $O (n \times 2^{n})$ ，其中 $n$ 是数组 $n u m s$ 的长度。空间复杂度 $O (1)$ 。

func subsetXORSum(nums []int) (ans int) {
	n := len(nums)
	for i := 0; i < 1<<n; i++ {
		s := 0
		for j, x := range nums {
			if i>>j&1 == 1 {
				s ^= x
			}
		}
		ans += s
	}
	return
}

方法二：DFS · Go 实现

思考

方法一用整数掩码，需要再开一层循环检查每一位。也可以 DFS：对第 $i$ 个元素选择「不选」或「异或进去」，到达末尾把当前异或和加入答案。时间同阶，写成选或不选更直观。

我们也可以使用深度优先搜索的方法，枚举出所有的子集，然后计算每个子集的异或总和。

我们设计一个函数 $d f s (i, s)$ ，其中 $i$ 表示当前搜索到数组 $n u m s$ 的第 $i$ 个元素， $s$ 表示当前子集的异或总和。初始时， $i = 0$ , $s = 0$ 。在搜索的过程中，每次我们都有两种选择：

将 $n u m s$ 的第 $i$ 个元素加入当前子集，即 $d f s (i + 1, s \oplus n u m s [i])$ ；
将 $n u m s$ 的第 $i$ 个元素不加入当前子集，即 $d f s (i + 1, s)$ 。

当我们搜索完数组 $n u m s$ 的所有元素时，即 $i = n$ 时，当前子集的异或总和为 $s$ ，将其加到答案中即可。

时间复杂度 $O (2^{n})$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $n u m s$ 的长度。

func subsetXORSum(nums []int) (ans int) {
	n := len(nums)
	var dfs func(int, int)
	dfs = func(i, s int) {
		if i >= n {
			ans += s
			return
		}
		dfs(i+1, s)
		dfs(i+1, s^nums[i])
	}
	dfs(0, 0)
	return
}

力扣原题 · Doocs 题解来源

1926. 迷宫中离入口最近的出口

中等1 种解法

标签：广度优先搜索、数组、矩阵

题目、示例与约束

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrance_row, entrance_col] 表示你一开始所在格子的行和列。

每一步操作，你可以往上，下，左或者右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是 maze 边界上的 空格子。entrance 格子不算出口。

请你返回从 entrance 到最近出口的最短路径的步数，如果不存在这样的路径，请你返回 -1 。

示例 1：

输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。

示例 2：

输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。

示例 3：

输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。

提示：

maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] 要么是 '.' ，要么是 '+' 。
entrance.length == 2
0 <= entrance_row < m
0 <= entrance_col < n
entrance 一定是空格子。

方法一：BFS · Go 实现

思考

最近出口是无权网格最短路。DFS 或按路径长度排序都不如按层扩展稳定。入口本身若在边界上也不算出口。

从入口 BFS，把走过的空格改为墙以免再入队。首次走到边界空格时的层数即为答案；队列空则不可达。

层内先弹出再扩四邻，保证步数按距离递增。

我们可以从入口开始，进行广度优先搜索，每次搜索到一个新的空格子，就将其标记为已访问，并将其加入队列，直到找到一个边界上的空格子，返回步数。

具体地，我们定义一个队列 $q$ ，初始时我们将 $entrance$ 加入队列。定义一个变量 $ans$ 记录步数，初始为 $1$ 。然后我们开始进行广度优先搜索，每一轮我们取出队列中的所有元素，遍历这些元素，对于每个元素，我们尝试向四个方向移动，如果移动后的位置是一个空格子，我们将其加入队列，并将其标记为已访问。如果移动后的位置是边界上的空格子，我们返回 $ans$ 。如果队列为空，我们返回 $- 1$ 。这一轮搜索结束后，我们将 $ans$ 加一，继续进行下一轮搜索。

遍历结束后，如果我们没有找到边界上的空格子，我们返回 $- 1$ 。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是迷宫的行数和列数。

func nearestExit(maze [][]byte, entrance []int) int {
	m, n := len(maze), len(maze[0])
	q := [][2]int{{entrance[0], entrance[1]}}
	maze[entrance[0]][entrance[1]] = '+'
	dirs := []int{-1, 0, 1, 0, -1}
	for ans := 1; len(q) > 0; ans++ {
		for k := len(q); k > 0; k-- {
			p := q[0]
			q = q[1:]
			for l := 0; l < 4; l++ {
				x, y := p[0]+dirs[l], p[1]+dirs[l+1]
				if x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' {
					if x == 0 || x == m-1 || y == 0 || y == n-1 {
						return ans
					}
					q = append(q, [2]int{x, y})
					maze[x][y] = '+'
				}
			}
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1980. 找出不同的二进制字符串

中等2 种解法

标签：数组、哈希表、字符串、回溯

题目、示例与约束

给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且 没有出现 在 nums 中的二进制字符串。如果存在多种答案，只需返回 任意一个 即可。

示例 1：

输入：nums = ["01","10"]
输出："11"
解释："11" 没有出现在 nums 中。"00" 也是正确答案。

示例 2：

输入：nums = ["00","01"]
输出："11"
解释："11" 没有出现在 nums 中。"10" 也是正确答案。

示例 3：

输入：nums = ["111","011","001"]
输出："101"
解释："101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。

提示：

n == nums.length
1 <= n <= 16
nums[i].length == n
nums[i] 为 '0' 或 '1'
nums 中的所有字符串 互不相同

方法一：计数 + 枚举 · Go 实现

思考

$n$ 个长为 $n$ 的串，全集有 $2^{n}$ 个，必存在未出现者。按 Hamming 重量分类： $0$ 到 $n$ 共 $n + 1$ 种重量，而串只有 $n$ 个，必缺一种重量。

用掩码记下已出现的 $1$ 的个数，再构造该个数个 $1$ 后补 $0$ 。

由于 '1' 在长度为 $n$ 的二进制字符串中出现的次数可以为 $0, 1, 2, \dots, n$ （共有 $n + 1$ 种可能），因此我们一定可以找出一个新的二进制字符串，满足 '1' 在字符串中出现次数与 $nums$ 中每个字符串不同。

我们可以用一个整数 $mask$ 记录所有字符串中 '1' 出现次数的情况，即 $mask$ 的第 $i$ 位为 $1$ 表示长度为 $n$ 的二进制字符串中 '1' 出现次数为 $i$ 的字符串存在，否则不存在。

然后我们从 $0$ 开始枚举长度为 $n$ 的二进制字符串中 '1' 出现的次数 $i$ ，如果 $mask$ 的第 $i$ 位为 $0$ ，则说明长度为 $n$ 的二进制字符串中 '1' 出现次数为 $i$ 的字符串不存在，我们可以将这个字符串作为答案返回。

时间复杂度 $O (L)$ ，其中 $L$ 为 $nums$ 中字符串的总长度。空间复杂度 $O (1)$ 。

func findDifferentBinaryString(nums []string) string {
	mask := 0
	for _, x := range nums {
		mask |= 1 << strings.Count(x, "1")
	}
	for i := 0; ; i++ {
		if mask>>i&1 == 0 {
			return strings.Repeat("1", i) + strings.Repeat("0", len(nums)-i)
		}
	}
}

方法二：构造 · Go 实现

思考

计数法需扫描全部比特。康托对角线更短：第 $i$ 位取与 $nums [i] [i]$ 相反的值，所得串与每一个输入至少差一位。

我们可以构造一个长度为 $n$ 的二进制字符串 $ans$ ，其中 $ans$ 的第 $i$ 位与 $nums [i]$ 的第 $i$ 位不同。由于 $nums$ 中的字符串互不相同，因此 $ans$ 不会出现在 $nums$ 中。

时间复杂度 $O (n)$ ，其中 $n$ 是 $nums$ 中字符串的长度。忽略答案字符串的空间复杂度，空间复杂度 $O (1)$ 。

func findDifferentBinaryString(nums []string) string {
	ans := make([]byte, len(nums))
	for i, s := range nums {
		if s[i] == '0' {
			ans[i] = '1'
		} else {
			ans[i] = '0'
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1992. 找到所有的农场组

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始，大小为 m x n 的二进制矩阵 land ，其中 0 表示一单位的森林土地，1 表示一单位的农场土地。

为了让农场保持有序，农场土地之间以矩形的 农场组 的形式存在。每一个农场组都仅包含农场土地。且题目保证不会有两个农场组相邻，也就是说一个农场组中的任何一块土地都不会与另一个农场组的任何一块土地在四个方向上相邻。

land 可以用坐标系统表示，其中 land 左上角坐标为 (0, 0) ，右下角坐标为 (m-1, n-1) 。请你找到所有 农场组 最左上角和最右下角的坐标。一个左上角坐标为 (r₁, c₁) 且右下角坐标为 (r₂, c₂) 的 农场组 用长度为 4 的数组 [r₁, c₁, r₂, c₂] 表示。

请你返回一个二维数组，它包含若干个长度为 4 的子数组，每个子数组表示 land 中的一个 农场组 。如果没有任何农场组，请你返回一个空数组。可以以 任意顺序 返回所有农场组。

示例 1：

输入：land = [[1,0,0],[0,1,1],[0,1,1]]
输出：[[0,0,0,0],[1,1,2,2]]
解释：
第一个农场组的左上角为 land[0][0] ，右下角为 land[0][0] 。
第二个农场组的左上角为 land[1][1] ，右下角为 land[2][2] 。

示例 2：

输入：land = [[1,1],[1,1]]
输出：[[0,0,1,1]]
解释：
第一个农场组左上角为 land[0][0] ，右下角为 land[1][1] 。

示例 3：

输入：land = [[0]]
输出：[]
解释：
没有任何农场组。

提示：

m == land.length
n == land[i].length
1 <= m, n <= 300
land 只包含 0 和 1 。
农场组都是矩形的形状。

方法一 · Go 实现

思考

农田是矩形连通块。连通搜索可以圈出整块，矩形结构则允许直接根据边界读出四角。

只在「上方与左方都不是农田」的格子当作左上角，再向下、向右延伸到矩形右下角。每个矩形报告一次。

func findFarmland(land [][]int) [][]int {
	m, n := len(land), len(land[0])
	var ans [][]int
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if land[i][j] == 0 || (j > 0 && land[i][j-1] == 1) || (i > 0 && land[i-1][j] == 1) {
				continue
			}
			x, y := i, j
			for ; x+1 < m && land[x+1][j] == 1; x++ {
			}
			for ; y+1 < n && land[x][y+1] == 1; y++ {
			}
			ans = append(ans, []int{i, j, x, y})
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2014. 重复 K 次的最长子序列

困难1 种解法

标签：哈希表、双指针、字符串、回溯、计数、枚举

题目、示例与约束

给你一个长度为 n 的字符串 s ，和一个整数 k 。请你找出字符串 s 中重复 k 次的 最长子序列 。

子序列 是由其他字符串删除某些（或不删除）字符派生而来的一个字符串。

如果 seq * k 是 s 的一个子序列，其中 seq * k 表示一个由 seq 串联 k 次构造的字符串，那么就称 seq 是字符串 s 中一个 重复 k 次 的子序列。

举个例子，"bba" 是字符串 "bababcba" 中的一个重复 2 次的子序列，因为字符串 "bbabba" 是由 "bba" 串联 2 次构造的，而 "bbabba" 是字符串 "bababcba" 的一个子序列。

返回字符串 s 中 重复 k 次的最长子序列 。如果存在多个满足的子序列，则返回 字典序最大 的那个。如果不存在这样的子序列，返回一个空字符串。

示例 1：

example 1

输入：s = "letsleetcode", k = 2
输出："let"
解释：存在两个最长子序列重复 2 次：let" 和 "ete" 。
"let" 是其中字典序最大的一个。

示例 2：

输入：s = "bb", k = 2
输出："b"
解释：重复 2 次的最长子序列是 "b" 。

示例 3：

输入：s = "ab", k = 2
输出：""
解释：不存在重复 2 次的最长子序列。返回空字符串。

提示：

n == s.length
2 <= k <= 2000
2 <= n < min(2001, k * 8)
s 由小写英文字母组成

方法一：BFS · Go 实现

思考

$n < min (2001, k \cdot 8)$ ，重复 $k$ 次的子序列长度至多为 $⌊ n / k ⌋ \leq 7$ 。字符须至少出现 $k$ 次才可能进入答案。

在长度受限时，按字典序从短到长扩展候选，比 DFS 更易保证「最后一次成功」即为最长且字典序最大（同长时后扩展的字母更大）。

队列从空串出发，仅把出现次数 $\geq k$ 的字母按升序追加；check 用双指针判断 $t$ 在 $s$ 中能否匹配 $k$ 遍。

我们可以先统计字符串中每个字符出现的次数，然后将出现次数大于等于 $k$ 的字符按从小到大的顺序存入一个列表 $cs$ 中。接下来，我们可以使用 BFS 来枚举所有可能的子序列。

我们定义一个队列 $q$ ，初始时将空字符串放入队列中。然后，我们从队列中取出一个字符串 $cur$ ，并尝试将每个字符 $c \in cs$ 添加到 $cur$ 的末尾，形成一个新的字符串 $nxt$ 。如果 $nxt$ 是一个重复 $k$ 次的子序列，我们就将其加入到答案中，并将 $nxt$ 放入队列中继续处理。

我们需要一个辅助函数 $check(t, k)$ 来判断字符串 $t$ 是否是字符串 $s$ 的一个重复 $k$ 次的子序列。具体地，我们可以使用两个指针来遍历字符串 $s$ 和 $t$ ，如果在遍历过程中能够找到 $t$ 的所有字符，并且能够重复 $k$ 次，那么就返回 $true$ ，否则返回 $false$ 。

func longestSubsequenceRepeatedK(s string, k int) string {
	check := func(t string, k int) bool {
		i := 0
		for _, c := range s {
			if byte(c) == t[i] {
				i++
				if i == len(t) {
					k--
					if k == 0 {
						return true
					}
					i = 0
				}
			}
		}
		return false
	}

	cnt := [26]int{}
	for i := 0; i < len(s); i++ {
		cnt[s[i]-'a']++
	}

	cs := []byte{}
	for c := byte('a'); c <= 'z'; c++ {
		if cnt[c-'a'] >= k {
			cs = append(cs, c)
		}
	}

	q := []string{""}
	ans := ""
	for len(q) > 0 {
		cur := q[0]
		q = q[1:]
		for _, c := range cs {
			nxt := cur + string(c)
			if check(nxt, k) {
				ans = nxt
				q = append(q, nxt)
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2044. 统计按位或能得到最大值的子集数目

中等2 种解法

标签：位运算、数组、回溯、枚举

题目、示例与约束

给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。

如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个子集。如果选中的元素下标位置不一样，则认为两个子集不同。

对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。

示例 1：

输入：nums = [3,1]
输出：2
解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
- [3]
- [3,1]

示例 2：

输入：nums = [2,2,2]
输出：7
解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 2³ - 1 = 7 个子集。

示例 3：

输入：nums = [3,2,1,5]
输出：6
解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

提示：

1 <= nums.length <= 16
1 <= nums[i] <= 10⁵

方法一：DFS · Go 实现

思考

$n \leq 16$ ，子集至多 $2^{16}$ 。全体或即为最大或值 $m x$ ，只需统计或等于 $m x$ 的非空子集（空集或为 $0$ ，一般不是最大）。

DFS 对每个下标选或不选，到达末尾时比较当前或值。递归深度 $n$ ，无需额外存储全部掩码。

数组 $nums$ 中按位或的最大值 $mx$ 可以通过对数组中所有元素按位或得到。

然后我们可以使用深度优先搜索来枚举所有子集，统计按位或等于 $mx$ 的子集个数。我们设计一个函数 $dfs(i, t)$ ，表示从下标 $i$ 开始，当前按位或的值为 $t$ 的子集个数。初始时 $i = 0$ , $t = 0$ 。

在函数 $dfs(i, t)$ 中，如果 $i$ 等于数组长度，说明已经枚举完所有元素，此时如果 $t$ 等于 $mx$ ，则答案加一。否则，我们可以选择不包含当前元素 $nums[i]$ ，或者包含当前元素 $nums[i]$ ，因此我们可以递归调用 $dfs(i + 1, t)$ 和 $dfs(i + 1, t | nums[i])$ 。

最后返回答案即可。

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

func countMaxOrSubsets(nums []int) (ans int) {
	mx := 0
	for _, x := range nums {
		mx |= x
	}

	var dfs func(i, t int)
	dfs = func(i, t int) {
		if i == len(nums) {
			if t == mx {
				ans++
			}
			return
		}
		dfs(i+1, t)
		dfs(i+1, t|nums[i])
	}

	dfs(0, 0)
	return
}

方法二：二进制枚举 · Go 实现

思考

方法一依赖递归。二进制枚举每个掩码，按位累或，同时维护当前最大与计数，可在一层循环内完成，且不必预先知道 $m x$ 。

代价是多一个 $n$ 的内层扫描，空间降为常数。

我们可以使用二进制枚举来统计所有子集的按位或结果。对于长度为 $n$ 的数组 $nums$ ，我们可以使用一个整数 $mask$ 来表示一个子集，其中 $mask$ 的第 $i$ 位为 1 表示包含元素 $nums[i]$ ，为 0 则表示不包含。

我们可以遍历所有可能的 $mask$ ，从 $0$ 到 $2^{n} - 1$ 。对于每个 $mask$ ，我们可以计算出对应子集的按位或结果，并更新最大值 $mx$ 和答案 $ans$ 。

时间复杂度 $O (2^{n} \cdot n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O (1)$ 。

func countMaxOrSubsets(nums []int) (ans int) {
	n := len(nums)
	mx := 0

	for mask := 0; mask < (1 << n); mask++ {
		t := 0
		for i, v := range nums {
			if (mask>>i)&1 == 1 {
				t |= v
			}
		}
		if mx < t {
			mx = t
			ans = 1
		} else if mx == t {
			ans++
		}
	}

	return
}

力扣原题 · Doocs 题解来源

2048. 下一个更大的数值平衡数

中等1 种解法

标签：哈希表、数学、回溯、计数、枚举

题目、示例与约束

如果整数 x 满足：对于每个数位 d ，这个数位恰好在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。

给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。

示例 1：

输入：n = 1
输出：22
解释：
22 是一个数值平衡数，因为：
- 数字 2 出现 2 次 
这也是严格大于 1 的最小数值平衡数。

示例 2：

输入：n = 1000
输出：1333
解释：
1333 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。

示例 3：

输入：n = 3000
输出：3133
解释：
3133 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 3000 的最小数值平衡数。

提示：

0 <= n <= 10⁶

方法一：枚举 · Go 实现

思考

$n \leq 10^{6}$ ，下一个平衡数不超过 $1224444$ ，从 $n + 1$ 逐个检验可行。平衡指数字 $d$ 若出现则恰出现 $d$ 次。

对每个 $x$ 统计十进制各位频次，检查非零频次是否等于该数字本身。count 递增直到命中。

我们注意到，题目中 $n$ 的范围是 $[0, 10^{6}]$ ，而大于 $10^{6}$ 的其中一个数值平衡数是 $1224444$ ，因此我们直接枚举 $x \in [n + 1, . .]$ ，然后判断 $x$ 是否是数值平衡数即可。枚举的 $x$ 一定不会超过 $1224444$ 。

时间复杂度 $O (M - n)$ ，其中 $M = 1224444$ 。空间复杂度 $O (1)$ 。

func nextBeautifulNumber(n int) int {
	for x := n + 1; ; x++ {
		cnt := [10]int{}
		for y := x; y > 0; y /= 10 {
			cnt[y%10]++
		}
		ok := true
		for y := x; y > 0; y /= 10 {
			if y%10 != cnt[y%10] {
				ok = false
				break
			}
		}
		if ok {
			return x
		}
	}
}

力扣原题 · Doocs 题解来源

2056. 棋盘上有效移动组合的数目

困难1 种解法

标签：数组、字符串、回溯、模拟

题目、示例与约束

有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [r_i, c_i] 表示第 i 个棋子现在在棋盘上的位置为 (r_i, c_i) ，棋盘下标从 1 开始。

每个棋子的移动中，首先选择移动的方向，然后选择 移动的步数 ，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：

车可以 水平或者竖直 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1) 或者 (r, c-1) 移动。
后可以 水平竖直或者斜对角 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1)，(r, c-1)，(r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。
象可以 斜对角 从 (r, c) 沿着方向 (r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。

你必须同时移动棋盘上的每一个棋子。移动组合 包含所有棋子的移动。每一秒，每个棋子都沿着它们选择的方向往前移动一步，直到它们到达目标位置。所有棋子从时刻 0 开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 不有效 。

请你返回有效移动组合的数目。

注意：

初始时，不会有两个棋子 在 同一个位置。
有可能在一个移动组合中，有棋子不移动。
如果两个棋子 直接相邻 且两个棋子下一秒要互相占据对方的位置，可以将它们在同一秒内 交换位置 。

示例 1:

输入：pieces = ["rook"], positions = [[1,1]]
输出：15
解释：上图展示了棋子所有可能的移动。

示例 2：

输入：pieces = ["queen"], positions = [[1,1]]
输出：22
解释：上图展示了棋子所有可能的移动。

示例 3:

输入：pieces = ["bishop"], positions = [[4,3]]
输出：12
解释：上图展示了棋子所有可能的移动。

示例 4:

输入：pieces = ["rook","rook"], positions = [[1,1],[8,8]]
输出：223
解释：每个车有 15 种移动，所以总共有 15 * 15 = 225 种移动组合。
但是，有两个是不有效的移动组合：
- 将两个车都移动到 (8, 1) ，会导致它们在同一个格子相遇。
- 将两个车都移动到 (1, 8) ，会导致它们在同一个格子相遇。
所以，总共有 225 - 2 = 223 种有效移动组合。
注意，有两种有效的移动组合，分别是一个车在 (1, 8) ，另一个车在 (8, 1) 。
即使棋盘状态是相同的，这两个移动组合被视为不同的，因为每个棋子移动操作是不相同的。

示例 5：

输入：pieces = ["queen","bishop"], positions = [[5,7],[3,4]]
输出：281
解释：总共有 12 * 24 = 288 种移动组合。
但是，有一些不有效的移动组合：
- 如果后停在 (6, 7) ，它会阻挡象到达 (6, 7) 或者 (7, 8) 。
- 如果后停在 (5, 6) ，它会阻挡象到达 (5, 6) ，(6, 7) 或者 (7, 8) 。
- 如果象停在 (5, 2) ，它会阻挡后到达 (5, 2) 或者 (5, 1) 。
在 288 个移动组合当中，281 个是有效的。

提示：

n == pieces.length
n == positions.length
1 <= n <= 4
pieces 只包含字符串 "rook" ，"queen" 和 "bishop" 。
棋盘上最多只有一个后。
1 <= r_i, c_i <= 8
每一个 positions[i] 互不相同。

方法一：DFS · Go 实现

思考

棋子至多 $4$ 个，棋盘 $8 \times 8$ ，方向各不超过 $8$ 。组合爆炸但规模仍可用 DFS：按顺序为每个棋子选定方向与停步时刻，并与此前棋子的时空轨迹查冲突。

dist[i][x][y] 记录经过时间，end 记录终点。停步要求更早棋子未在该时刻后仍占格；途经要求无同时同格、也无已被占用的终点。

全部棋子安排完毕则方案加一。

题目最多只有 $4$ 个棋子，每个棋子的移动方向最多有 $8$ 种，我们可以考虑使用 DFS 搜索所有的移动组合。

我们按照顺序依次枚举每个棋子，对于每个棋子，我们可以选择不移动，或者按照规则移动，用数组 $dist [i]$ 记录第 $i$ 个棋子的移动情况，其中 $dist [i] [x] [y]$ 表示第 $i$ 个棋子经过坐标 $(x, y)$ 时的时间，用数组 $end [i]$ 记录第 $i$ 个棋子的终点坐标和时间。在搜索时，我们需要分别判断当前棋子是否可以停止移动，以及当前棋子是否可以继续在当前方向移动。

我们定义方法 $checkStop (i, x, y, t)$ 判断第 $i$ 个棋子是否在时间 $t$ 时停在坐标 $(x, y)$ ，如果对于此前的所有棋子 $j$ ，都有 $dist [j] [x] [y] < t$ ，那么第 $i$ 个棋子可以停止移动。

另外，我们定义方法 $checkPass (i, x, y, t)$ 判断第 $i$ 个棋子是否可以在时间 $t$ 时经过坐标 $(x, y)$ 。如果此前有其它棋子 $j$ 也在时间 $t$ 经过坐标 $(x, y)$ ，或者有其它棋子 $j$ 停在 $(x, y)$ ，且时间不超过 $t$ ，那么第 $i$ 个棋子不能在时间 $t$ 时经过坐标 $(x, y)$ 。

时间复杂度 $O ((n \times M)^{n})$ ，空间复杂度 $O (n \times M)$ 。其中 $n$ 是棋子的数量，而 $M$ 是每个棋子的移动范围。

func countCombinations(pieces []string, positions [][]int) (ans int) {
	n := len(pieces)
	m := 9
	dist := make([][][]int, n)
	for i := range dist {
		dist[i] = make([][]int, m)
		for j := range dist[i] {
			dist[i][j] = make([]int, m)
		}
	}

	end := make([][3]int, n)

	rookDirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	bishopDirs := [][2]int{{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
	queenDirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}

	resetDist := func(i int) {
		for j := 0; j < m; j++ {
			for k := 0; k < m; k++ {
				dist[i][j][k] = -1
			}
		}
	}

	checkStop := func(i, x, y, t int) bool {
		for j := 0; j < i; j++ {
			if dist[j][x][y] >= t {
				return false
			}
		}
		return true
	}

	checkPass := func(i, x, y, t int) bool {
		for j := 0; j < i; j++ {
			if dist[j][x][y] == t {
				return false
			}
			if end[j][0] == x && end[j][1] == y && end[j][2] <= t {
				return false
			}
		}
		return true
	}

	isValid := func(x, y int) bool {
		return x >= 1 && x < m && y >= 1 && y < m
	}

	getDirs := func(piece string) [][2]int {
		switch piece[0] {
		case 'r':
			return rookDirs
		case 'b':
			return bishopDirs
		default:
			return queenDirs
		}
	}

	var dfs func(i int)
	dfs = func(i int) {
		if i >= n {
			ans++
			return
		}

		x, y := positions[i][0], positions[i][1]
		resetDist(i)
		dist[i][x][y] = 0
		end[i] = [3]int{x, y, 0}

		if checkStop(i, x, y, 0) {
			dfs(i + 1)
		}

		dirs := getDirs(pieces[i])
		for _, dir := range dirs {
			resetDist(i)
			dist[i][x][y] = 0
			nx, ny, nt := x+dir[0], y+dir[1], 1

			for isValid(nx, ny) && checkPass(i, nx, ny, nt) {
				dist[i][nx][ny] = nt
				end[i] = [3]int{nx, ny, nt}
				if checkStop(i, nx, ny, nt) {
					dfs(i + 1)
				}
				nx += dir[0]
				ny += dir[1]
				nt++
			}
		}
	}

	dfs(0)
	return
}

力扣原题 · Doocs 题解来源

2059. 转化数字的最小运算数

中等3 种解法

标签：广度优先搜索、数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，该数组由 互不相同 的数字组成。另给你两个整数 start 和 goal 。

整数 x 的值最开始设为 start ，你打算执行一些运算使 x 转化为 goal 。你可以对数字 x 重复执行下述运算：

如果 0 <= x <= 1000 ，那么，对于数组中的任一下标 i（0 <= i < nums.length），可以将 x 设为下述任一值：

x + nums[i]
x - nums[i]
x ^ nums[i]（按位异或 XOR）

注意，你可以按任意顺序使用每个 nums[i] 任意次。使 x 越过 0 <= x <= 1000 范围的运算同样可以生效，但该该运算执行后将不能执行其他运算。

返回将 x = start 转化为 goal 的最小操作数；如果无法完成转化，则返回 -1 。

示例 1：

输入：nums = [2,4,12], start = 2, goal = 12
输出：2
解释：
可以按 2 → 14 → 12 的转化路径进行，只需执行下述 2 次运算：
- 2 + 12 = 14
- 14 - 2 = 12

示例 2：

输入：nums = [3,5,7], start = 0, goal = -4
输出：2
解释：
可以按 0 → 3 → -4 的转化路径进行，只需执行下述 2 次运算：
- 0 + 3 = 3
- 3 - 7 = -4
注意，最后一步运算使 x 超过范围 0 <= x <= 1000 ，但该运算仍然可以生效。

示例 3：

输入：nums = [2,8,16], start = 0, goal = 1
输出：-1
解释：
无法将 0 转化为 1

提示：

1 <= nums.length <= 1000
-10⁹ <= nums[i], goal <= 10⁹
0 <= start <= 1000
start != goal
nums 中的所有整数互不相同

方法一：BFS · Go 实现

思考

每次对当前值做加、减或异或 $n u m s [i]$ ，目标可达范围实际被限制在继续扩展的中间态 $[0, 1000]$ 。状态数 $\leq 1001$ ，最短操作次数适合 BFS。

从 $s t a r t$ 出队，对每个数与三种运算生成 $n x$ ；命中 $g o a l$ 即返回步数，合法中间态入队并标记，避免重复。

从 $s t a r t$ 出发，对每个数做加减异或，广搜到达 $g o a l$ 的最少步数。

func minimumOperations(nums []int, start int, goal int) int {
	type pair struct {
		x    int
		step int
	}

	ops := []func(int, int) int{
		func(x, y int) int { return x + y },
		func(x, y int) int { return x - y },
		func(x, y int) int { return x ^ y },
	}
	vis := make([]bool, 1001)
	q := []pair{{start, 0}}

	for len(q) > 0 {
		x, step := q[0].x, q[0].step
		q = q[1:]
		for _, num := range nums {
			for _, op := range ops {
				nx := op(x, num)
				if nx == goal {
					return step + 1
				}
				if nx >= 0 && nx <= 1000 && !vis[nx] {
					q = append(q, pair{nx, step + 1})
					vis[nx] = true
				}
			}
		}
	}
	return -1
}

方法二：BFS（分层） · Go 实现

思考

方法一在入队时携带步数。改为按层扩展， $a n s$ 每层加一，语义相同而队列元素更轻。

next 集中生成后继，层次循环结束仍未到达则返回 $- 1$ 。

同样广搜，按层扩展下一状态。

func minimumOperations(nums []int, start int, goal int) int {
	next := func(x int) []int {
		var res []int
		for _, num := range nums {
			res = append(res, []int{x + num, x - num, x ^ num}...)
		}
		return res
	}
	q := []int{start}
	vis := make([]bool, 1001)
	ans := 0
	for len(q) > 0 {
		ans++
		for n := len(q); n > 0; n-- {
			x := q[0]
			q = q[1:]
			for _, y := range next(x) {
				if y == goal {
					return ans
				}
				if y >= 0 && y <= 1000 && !vis[y] {
					vis[y] = true
					q = append(q, y)
				}
			}
		}
	}
	return -1
}

方法三：双向 BFS · Go 实现

思考

单向 BFS 在分支因子大时队列偏长。 $g o a l$ 也可能作为起点向回走（运算可逆意义下的相遇）。两端同时扩展，每次选更短的一侧，相遇步数相加。

中间态仍限制在 $[0, 1000]$ ， $g o a l$ 本身可在范围外，故目标侧首次扩展即可命中。

从 $s t a r t$ 和 $g o a l$ 两端同时扩展，相遇即得到最少操作次数。

func minimumOperations(nums []int, start int, goal int) int {
	next := func(x int) []int {
		var res []int
		for _, num := range nums {
			res = append(res, []int{x + num, x - num, x ^ num}...)
		}
		return res
	}
	m1, m2 := map[int]int{start: 0}, map[int]int{goal: 0}
	q1, q2 := []int{start}, []int{goal}
	extend := func() int {
		for i := len(q1); i > 0; i-- {
			x := q1[0]
			q1 = q1[1:]
			step, _ := m1[x]
			for _, y := range next(x) {
				if _, ok := m1[y]; ok {
					continue
				}
				if v, ok := m2[y]; ok {
					return step + 1 + v
				}
				if y >= 0 && y <= 1000 {
					m1[y] = step + 1
					q1 = append(q1, y)
				}
			}
		}
		return -1
	}
	for len(q1) > 0 && len(q2) > 0 {
		if len(q1) > len(q2) {
			m1, m2 = m2, m1
			q1, q2 = q2, q1
		}
		t := extend()
		if t != -1 {
			return t
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

2146. 价格范围内最高排名的 K 样物品

中等1 种解法

标签：广度优先搜索、数组、矩阵、排序、堆（优先队列）

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为：

0 表示无法穿越的一堵墙。
1 表示可以自由通过的一个空格子。
所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。

从一个格子走到上下左右相邻格子花费 1 步。

同时给你一个整数数组 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你开始位置为 (row, col) ，同时你只对物品价格在 闭区间 [low, high] 之内的物品感兴趣。同时给你一个整数 k 。

你想知道给定范围内且 排名最高 的 k 件物品的位置。排名按照优先级从高到低的以下规则制定：

距离：定义为从 start 到一件物品的最短路径需要的步数（较近距离的排名更高）。
价格：较低价格的物品有更高优先级，但只考虑在给定范围之内的价格。
行坐标：较小行坐标的有更高优先级。
列坐标：较小列坐标的有更高优先级。

请你返回给定价格内排名最高的 k 件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 k 件物品，那么请将它们的坐标全部返回。

示例 1：

输入：grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
输出：[[0,1],[1,1],[2,1]]
解释：起点为 (0,0) 。
价格范围为 [2,5] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(2,1) 和 (2,2) 。
这些物品的排名为：
- (0,1) 距离为 1
- (1,1) 距离为 2
- (2,1) 距离为 3
- (2,2) 距离为 4
所以，给定价格范围内排名最高的 3 件物品的坐标为 (0,1)，(1,1) 和 (2,1) 。

示例 2：

输入：grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
输出：[[2,1],[1,2]]
解释：起点为 (2,3) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(1,2) 和 (2,1) 。
这些物品的排名为： 
- (2,1) 距离为 2 ，价格为 2
- (1,2) 距离为 2 ，价格为 3
- (1,1) 距离为 3
- (0,1) 距离为 4
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (1,2) 。

示例 3：

输入：grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
输出：[[2,1],[2,0]]
解释：起点为 (0,0) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (2,0) 和 (2,1) 。
这些物品的排名为：
- (2,1) 距离为 5
- (2,0) 距离为 6
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (2,0) 。
注意，k = 3 但给定价格范围内只有 2 件物品。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
0 <= grid[i][j] <= 10⁵
pricing.length == 2
2 <= low <= high <= 10⁵
start.length == 2
0 <= row <= m - 1
0 <= col <= n - 1
grid[row][col] > 0
1 <= k <= m * n

方法一：BFS + 排序 · Go 实现

思考

排名先比距离，再比价格、行、列。网格可达 $10^{4}$ 量级，对每个格子单独求最短路过重。从起点 BFS 的层次即曼哈顿障碍距离，且首次访问即为最短。

搜索中收集价格落在 $[low, high]$ 的格子及其距离，最后按四元组排序取前 $k$ 。

把访问过的格子置 $0$ 以免入队两次。

我们可以从 $(row, col)$ 出发，使用广度优先搜索找到所有价格在 $[low, high]$ 范围内的物品，将这些物品的距离、价格、行坐标和列坐标存入数组 $pq$ 中。

最后对 $pq$ 按照距离、价格、行坐标和列坐标的顺序排序，取前 $k$ 个物品的坐标返回。

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

func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) (ans [][]int) {
	m, n := len(grid), len(grid[0])
	row, col := start[0], start[1]
	low, high := pricing[0], pricing[1]
	q := [][2]int{{row, col}}
	pq := [][]int{}
	if low <= grid[row][col] && grid[row][col] <= high {
		pq = append(pq, []int{0, grid[row][col], row, col})
	}
	grid[row][col] = 0
	dirs := [5]int{-1, 0, 1, 0, -1}
	for step := 1; len(q) > 0; step++ {
		for sz := len(q); sz > 0; sz-- {
			x, y := q[0][0], q[0][1]
			q = q[1:]
			for j := 0; j < 4; j++ {
				nx, ny := x+dirs[j], y+dirs[j+1]
				if nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0 {
					if low <= grid[nx][ny] && grid[nx][ny] <= high {
						pq = append(pq, []int{step, grid[nx][ny], nx, ny})
					}
					grid[nx][ny] = 0
					q = append(q, [2]int{nx, ny})
				}
			}
		}
	}
	sort.Slice(pq, func(i, j int) bool {
		a, b := pq[i], pq[j]
		if a[0] != b[0] {
			return a[0] < b[0]
		}
		if a[1] != b[1] {
			return a[1] < b[1]
		}
		if a[2] != b[2] {
			return a[2] < b[2]
		}
		return a[3] < b[3]
	})
	for i := 0; i < len(pq) && i < k; i++ {
		ans = append(ans, pq[i][2:])
	}
	return
}

力扣原题 · Doocs 题解来源

2151. 基于陈述统计最多好人数

困难1 种解法

标签：位运算、数组、回溯、枚举

题目、示例与约束

游戏中存在两种角色：

好人：该角色只说真话。
坏人：该角色可能说真话，也可能说假话。

给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说，statements[i][j] 可以是下述值之一：

0 表示 i 的陈述认为 j 是坏人。
1 表示 i 的陈述认为 j 是好人。
2 表示 i 没有对 j 作出陈述。

另外，玩家不会对自己进行陈述。形式上，对所有 0 <= i < n ，都有 statements[i][i] = 2 。

根据这 n 个玩家的陈述，返回可以认为是好人的最大数目。

示例 1：

输入：statements = [[2,1,2],[1,2,2],[2,0,2]]
输出：2
解释：每个人都做一条陈述。
- 0 认为 1 是好人。
- 1 认为 0 是好人。
- 2 认为 1 是坏人。
以 2 为突破点。
- 假设 2 是一个好人：
    - 基于 2 的陈述，1 是坏人。
    - 那么可以确认 1 是坏人，2 是好人。
    - 基于 1 的陈述，由于 1 是坏人，那么他在陈述时可能：
        - 说真话。在这种情况下会出现矛盾，所以假设无效。
        - 说假话。在这种情况下，0 也是坏人并且在陈述时说假话。
    - 在认为 2 是好人的情况下，这组玩家中只有一个好人。
- 假设 2 是一个坏人：
    - 基于 2 的陈述，由于 2 是坏人，那么他在陈述时可能：
        - 说真话。在这种情况下，0 和 1 都是坏人。
            - 在认为 2 是坏人但说真话的情况下，这组玩家中没有一个好人。
        - 说假话。在这种情况下，1 是好人。
            - 由于 1 是好人，0 也是好人。
            - 在认为 2 是坏人且说假话的情况下，这组玩家中有两个好人。
在最佳情况下，至多有两个好人，所以返回 2 。
注意，能得到此结论的方法不止一种。

示例 2：

输入：statements = [[2,0],[0,2]]
输出：1
解释：每个人都做一条陈述。
- 0 认为 1 是坏人。
- 1 认为 0 是坏人。
以 0 为突破点。
- 假设 0 是一个好人：
    - 基于与 0 的陈述，1 是坏人并说假话。
    - 在认为 0 是好人的情况下，这组玩家中只有一个好人。
- 假设 0 是一个坏人：
    - 基于 0 的陈述，由于 0 是坏人，那么他在陈述时可能：
        - 说真话。在这种情况下，0 和 1 都是坏人。
            - 在认为 0 是坏人但说真话的情况下，这组玩家中没有一个好人。
        - 说假话。在这种情况下，1 是好人。
            - 在认为 0 是坏人且说假话的情况下，这组玩家中只有一个好人。
在最佳情况下，至多有一个好人，所以返回 1 。 
注意，能得到此结论的方法不止一种。

提示：

n == statements.length == statements[i].length
2 <= n <= 15
statements[i][j] 的值为 0、1 或 2
statements[i][i] == 2

方法一：二进制枚举 · Go 实现

思考

每人可好可坏，好人的证词必须与假设一致，坏人的证词任意。 $n \leq 15$ ，可枚举 $2^{n}$ 种好人集合。

对掩码中的每一位好人，核对其对其他人的 $0 / 1$ 陈述是否与掩码相符；矛盾则该掩码非法，否则人数可参与比较。

枚举全部非空掩码（含全坏，人数为 $0$ ），取合法掩码中 $1$ 的个数最大值。

二进制枚举好人的状态 $m a s k$ ，由于“好人只说真话”，我们借此判断 $s t a t e m e n t s$ 与 $m a s k$ 是否存在矛盾，不存在则获取 $m a s k$ 中好人的数量 $c n t$ 。迭代获取最大的合法 $c n t$ 。

时间复杂度 $O (2^{n} * n^{2})$ ，其中 $n$ 表示 $s t a t e m e n t s$ 的长度。

func maximumGood(statements [][]int) int {
	n := len(statements)
	check := func(mask int) int {
		cnt := 0
		for i, s := range statements {
			if ((mask >> i) & 1) == 1 {
				for j, v := range s {
					if v < 2 && ((mask>>j)&1) != v {
						return 0
					}
				}
				cnt++
			}
		}
		return cnt
	}
	ans := 0
	for mask := 1; mask < 1<<n; mask++ {
		ans = max(ans, check(mask))
	}
	return ans
}

力扣原题 · Doocs 题解来源

2174. 通过翻转行或列来去除所有的 1 II 🔒

中等1 种解法

标签：位运算、广度优先搜索、数组、矩阵

题目、示例与约束

给定 下标从 0 开始 的 m x n 二进制 矩阵 grid。

在一次操作中，可以选择满足以下条件的任意 i 和 j:

0 <= i < m
0 <= j < n
grid[i][j] == 1

并将第 i 行和第 j 列中的所有单元格的值更改为零。

返回从 grid 中删除所有 1 所需的最小操作数。

示例 1:

输入: grid = [[1,1,1],[1,1,1],[0,1,0]]
输出: 2
解释:
在第一个操作中，将第 1 行和第 1 列的所有单元格值更改为 0。
在第二个操作中，将第 0 行和第 0 列的所有单元格值更改为 0。

示例 2:

输入: grid = [[0,1,0],[1,0,1],[0,1,0]]
输出: 2
解释:
在第一个操作中，将第 1 行和第 0 列的所有单元格值更改为 0。
在第二个操作中，将第 2 行和第 1 列的所有单元格值更改为 0。
注意，我们不能使用行 1 和列 1 执行操作，因为 grid[1][1]!= 1。

示例 3:

输入: grid = [[0,0],[0,0]]
输出: 0
解释:
没有 1 可以移除，所以返回0。

提示:

m == grid.length
n == grid[i].length
1 <= m, n <= 15
1 <= m * n <= 15
grid[i][j] 为 0 或 1。

方法一：状态压缩 + BFS · Go 实现

思考

一次操作选定一个 $1$ ，把它所在行与列上的 $1$ 全部清除，求最少次数。网格至多 $8 \times 8$ ，状态可压成整数。不同操作顺序对应同一集合时结果相同，宜按层搜索最短序列。

把矩阵压成比特 $state$ ，每次枚举仍为 $1$ 的格子，清除其行列对应比特得到新状态。BFS 的层数即操作次数。

起点为初始掩码，终点为 $0$ 。

func removeOnes(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	state := 0
	for i, row := range grid {
		for j, v := range row {
			if v == 1 {
				state |= 1 << (i*n + j)
			}
		}
	}
	q := []int{state}
	vis := map[int]bool{state: true}
	ans := 0
	for len(q) > 0 {
		for k := len(q); k > 0; k-- {
			state = q[0]
			if state == 0 {
				return ans
			}
			q = q[1:]
			for i, row := range grid {
				for j, v := range row {
					if v == 0 {
						continue
					}
					nxt := state
					for r := 0; r < m; r++ {
						nxt &= ^(1 << (r*n + j))
					}
					for c := 0; c < n; c++ {
						nxt &= ^(1 << (i*n + c))
					}
					if !vis[nxt] {
						vis[nxt] = true
						q = append(q, nxt)
					}
				}
			}
		}
		ans++
	}
	return -1
}

力扣原题 · Doocs 题解来源

2178. 拆分成最多数目的正偶数之和

中等1 种解法

标签：贪心、数学、回溯

题目、示例与约束

给你一个整数 finalSum 。请你将它拆分成若干个 互不相同 的正偶数之和，且拆分出来的正偶数数目最多。

比方说，给你 finalSum = 12 ，那么这些拆分是 符合要求 的（互不相同的正偶数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意 finalSum 不能拆分成 (2 + 2 + 4 + 4) ，因为拆分出来的整数必须互不相同。

请你返回一个整数数组，表示将整数拆分成最多数目的正偶数数组。如果没有办法将 finalSum 进行拆分，请你返回一个空数组。你可以按任意顺序返回这些整数。

示例 1：

输入：finalSum = 12
输出：[2,4,6]
解释：以下是一些符合要求的拆分：(2 + 10)，(2 + 4 + 6) 和 (4 + 8) 。
(2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。
[2,6,4] ，[6,2,4] 等等也都是可行的解。

示例 2：

输入：finalSum = 7
输出：[]
解释：没有办法将 finalSum 进行拆分。
所以返回空数组。

示例 3：

输入：finalSum = 28
输出：[6,8,2,12]
解释：以下是一些符合要求的拆分：(2 + 26)，(6 + 8 + 2 + 12) 和 (4 + 24) 。
(6 + 8 + 2 + 12) 有最多数目的整数，数目为 4 ，所以我们返回 [6,8,2,12] 。
[10,2,4,12] ，[6,2,4,16] 等等也都是可行的解。

提示：

1 <= finalSum <= 10¹⁰

方法一：贪心 · Go 实现

思考

把偶数和拆成尽可能多的互异正偶数。奇数和无法拆。若预留较大的数，会减少个数。

从 $2, 4, 6, \dots$ 依次取出，直到剩余不足下一个偶数，把余数加到最后一项。最后一项因此可能变大，但仍与前面互异，因为余数小于下一个未取偶数。

奇数直接返回空列表。

如果 $finalSum$ 是奇数，那么无法拆分成若干个互不相同的正偶数之和，直接返回空数组。

否则，我们可以贪心地按照 $2, 4, 6, \dots$ 的顺序拆分 $finalSum$ ，直到 $finalSum$ 无法再拆分出一个不同的正偶数为止，此时我们将剩余的 $finalSum$ 加到最后一个正偶数上即可。

时间复杂度 $O (\sqrt{finalSum})$ ，忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

func maximumEvenSplit(finalSum int64) (ans []int64) {
	if finalSum%2 == 1 {
		return
	}
	for i := int64(2); i <= finalSum; i += 2 {
		ans = append(ans, i)
		finalSum -= i
	}
	ans[len(ans)-1] += finalSum
	return
}

力扣原题 · Doocs 题解来源

2212. 射箭比赛中的最大得分

中等1 种解法

标签：位运算、数组、回溯、枚举

题目、示例与约束

Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：

Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。
分数按下述规则计算：
1. 箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11）。
2. 箭靶上每个区域都对应一个得分 k（范围是 0 到 11），Alice 和 Bob 分别在得分 k 区域射中 a_k 和 b_k 支箭。如果 a_k >= b_k ，那么 Alice 得 k 分。如果 a_k < b_k ，则 Bob 得 k 分
3. 如果 a_k == b_k == 0 ，那么无人得到 k 分。

例如，Alice 和 Bob 都向计分为 11 的区域射 2 支箭，那么 Alice 得 11 分。如果 Alice 向计分为 11 的区域射 0 支箭，但 Bob 向同一个区域射 2 支箭，那么 Bob 得 11 分。

给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ，该数组表示 Alice 射中 0 到 11 每个计分区域的箭数量。现在，Bob 想要尽可能 最大化 他所能获得的总分。

返回数组 bobArrows ，该数组表示 Bob 射中 0 到 11 每个计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。

如果存在多种方法都可以使 Bob 获得最大总分，返回其中 任意一种 即可。

示例 1：

输入：numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
输出：[0,0,0,0,1,1,0,0,1,2,3,1]
解释：上表显示了比赛得分情况。
Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。
可以证明 Bob 无法获得比 47 更高的分数。

示例 2：

输入：numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
输出：[0,0,0,0,0,0,0,0,1,1,1,0]
解释：上表显示了比赛得分情况。
Bob 获得总分 8 + 9 + 10 = 27 。
可以证明 Bob 无法获得比 27 更高的分数。

提示：

1 <= numArrows <= 10⁵
aliceArrows.length == bobArrows.length == 12
0 <= aliceArrows[i], bobArrows[i] <= numArrows
sum(aliceArrows[i]) == numArrows

方法一：二进制枚举 · Go 实现

思考

Bob 要在 $12$ 个环上分配箭，某环得分当且仅当箭数严格多于 Alice。若按每环箭数搜索， $numArrows$ 可达 $10^{5}$ ，状态过多。环数只有 $12$ ，真正要决定的是「赢下哪些环」。

赢下第 $i$ 环恰好需要 $a l i c e A r r o w s [i] + 1$ 支箭，得分固定为 $i$ 。因此用长度为 $12$ 的二进制掩码枚举得分集合，累加所需箭数与得分；箭数不超过限额且得分更优时记下该掩码。

最后按掩码还原各环箭数，剩余箭全部放入 $0$ 环（该环本不得分）。枚举量 $2^{12}$ ，可以接受。

由于区域数目只有 $12$ 个，因此我们使用二进制枚举的方式，枚举 $Bob$ 在哪些区域得分。用一个变量 $st$ 表示 $Bob$ 获得最大得分的方案，而 $mx$ 表示 $Bob$ 获得的最大得分。

我们在 $[1, 2^{m})$ 的区间内枚举 $Bob$ 的得分方案，其中 $m$ 是 $aliceArrows$ 的长度。对于每一个方案，我们计算 $Bob$ 的得分 $s$ 以及射箭的数量 $cnt$ 。如果 $cnt \leq numArrows$ 且 $s > mx$ ，我们就更新 $mx$ 和 $st$ 。

然后，我们根据 $st$ 计算 $Bob$ 的得分方案，如果最后还有剩余的射箭，我们将剩余的射箭分配给第一个区域，即下标为 $0$ 的区域。

时间复杂度 $O (2^{m} \times m)$ ，其中 $m$ 是 $aliceArrows$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

func maximumBobPoints(numArrows int, aliceArrows []int) []int {
	st, mx := 0, 0
	m := len(aliceArrows)
	for mask := 1; mask < 1<<m; mask++ {
		cnt, s := 0, 0
		for i, x := range aliceArrows {
			if mask>>i&1 == 1 {
				s += i
				cnt += x + 1
			}
		}
		if cnt <= numArrows && s > mx {
			mx = s
			st = mask
		}
	}
	ans := make([]int, m)
	for i, x := range aliceArrows {
		if (st>>i)&1 == 1 {
			ans[i] = x + 1
			numArrows -= ans[i]
		}
	}
	ans[0] += numArrows
	return ans
}

力扣原题 · Doocs 题解来源

2258. 逃离火灾

困难1 种解法

标签：广度优先搜索、数组、二分查找、矩阵

题目、示例与约束

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：

0 表示草地。
1 表示着火的格子。
2 表示一座墙，你跟火都不能通过这个格子。

一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到相邻的草地格子。每次你移动之后，着火的格子会扩散到所有不是墙的相邻格子。

请你返回你在初始位置可以停留的最多分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你总是能到达安全屋，请你返回 10⁹ 。

注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。

如果两个格子有共同边，那么它们为相邻格子。

示例 1：

输入：grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
输出：3
解释：上图展示了你在初始位置停留 3 分钟后的情形。
你仍然可以安全到达安全屋。
停留超过 3 分钟会让你无法安全到达安全屋。

示例 2：

输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
输出：-1
解释：上图展示了你马上开始朝安全屋移动的情形。
火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。
所以返回 -1 。

示例 3：

输入：grid = [[0,0,0],[2,2,0],[1,2,0]]
输出：1000000000
解释：上图展示了初始网格图。
注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。
所以返回 10⁹ 。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 300
4 <= m * n <= 2 * 10⁴
grid[i][j] 是 0 ，1 或者 2 。
grid[0][0] == grid[m - 1][n - 1] == 0

方法一：二分查找 + BFS · Go 实现

思考

人先停留 $t$ 分钟再出发，火每分钟向四向蔓延，问最大可行 $t$ 。网格至多约 $2 \times 10^{4}$ 格。若 $t$ 可行，更短的停留也可行，答案单调，适合二分。

对候选 $t$ ，先让火蔓延 $t$ 分钟；若起点已着火则失败。再让人与火同步 BFS：人只走进尚未着火的空地，每走完一层火再蔓延一次。人先于火到达终点（或与火同时到达终点）则成功。上界取 $m n$ ，若连上界都成功则返回 $10^{9}$ 。

我们注意到，如果一个停留时间 $t$ 满足条件，那么所有小于 $t$ 的时间也都满足条件。因此我们可以考虑使用二分查找的方法找到最大的满足条件的时间。

我们定义二分查找的左边界 $l = - 1$ ，右边界 $r = m \times n$ 。每一次二分查找，我们都将 $l$ 和 $r$ 的中点 $m i d$ 作为当前的停留时间，判断是否满足条件。如果满足条件，那么我们将 $l$ 更新为 $m i d$ ，否则我们将 $r$ 更新为 $m i d - 1$ 。最后，如果 $l = m \times n$ ，那么说明不存在满足条件的停留时间，我们返回 $10^{9}$ ，否则我们返回 $l$ 。

问题的关键转化为如何判断一个停留时间 $t$ 是否满足条件。我们可以使用广度优先搜索的方法，在 $t$ 时间内，模拟火的蔓延过程。如果停留 $t$ 时间后，火蔓延到了起点位置，那么说明不满足条件，提前返回。否则，我们这时候再使用广度优先搜索，每一次从当前位置向四个方向进行搜索，每一轮结束后，我们还需要将火向四个方向蔓延一次。如果在这个过程中，我们找到了一条从起点到终点的路径，那么说明满足条件。

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

func maximumMinutes(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	fire := make([][]bool, m)
	vis := make([][]bool, m)
	dirs := [5]int{-1, 0, 1, 0, -1}
	for i := range fire {
		fire[i] = make([]bool, n)
		vis[i] = make([]bool, n)
	}
	l, r := -1, m*n
	spread := func(q [][2]int) [][2]int {
		nq := [][2]int{}
		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 && !fire[x][y] && grid[x][y] == 0 {
					fire[x][y] = true
					nq = append(nq, [2]int{x, y})
				}
			}
		}
		return nq
	}
	check := func(t int) bool {
		for i := range fire {
			for j := range fire[i] {
				fire[i][j] = false
				vis[i][j] = false
			}
		}
		q1 := [][2]int{}
		for i := 0; i < m; i++ {
			for j := 0; j < n; j++ {
				if grid[i][j] == 1 {
					q1 = append(q1, [2]int{i, j})
					fire[i][j] = true
				}
			}
		}
		for ; t > 0 && len(q1) > 0; t-- {
			q1 = spread(q1)
		}
		q2 := [][2]int{{0, 0}}
		vis[0][0] = true
		for ; len(q2) > 0; q1 = spread(q1) {
			for d := len(q2); d > 0; d-- {
				p := q2[0]
				q2 = q2[1:]
				if fire[p[0]][p[1]] {
					continue
				}
				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 && !fire[x][y] && !vis[x][y] && grid[x][y] == 0 {
						if x == m-1 && y == n-1 {
							return true
						}
						vis[x][y] = true
						q2 = append(q2, [2]int{x, y})
					}
				}
			}
		}
		return false
	}
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	if l == m*n {
		return int(1e9)
	}
	return l
}

力扣原题 · Doocs 题解来源

2375. 根据模式串构造最小数字

中等1 种解法

标签：栈、贪心、字符串、回溯

题目、示例与约束

给你下标从 0 开始、长度为 n 的字符串 pattern ，它包含两种字符，'I' 表示上升，'D' 表示下降。

你需要构造一个下标从 0 开始长度为 n + 1 的字符串，且它要满足以下条件：

num 包含数字 '1' 到 '9' ，其中每个数字至多使用一次。
如果 pattern[i] == 'I' ，那么 num[i] < num[i + 1] 。
如果 pattern[i] == 'D' ，那么 num[i] > num[i + 1] 。

请你返回满足上述条件字典序最小的字符串 num。

示例 1：

输入：pattern = "IIIDIDDD"
输出："123549876"
解释：
下标 0 ，1 ，2 和 4 处，我们需要使 num[i] < num[i+1] 。
下标 3 ，5 ，6 和 7 处，我们需要使 num[i] > num[i+1] 。
一些可能的 num 的值为 "245639871" ，"135749862" 和 "123849765" 。
"123549876" 是满足条件最小的数字。
注意，"123414321" 不是可行解因为数字 '1' 使用次数超过 1 次。

示例 2：

输入：pattern = "DDD"
输出："4321"
解释：
一些可能的 num 的值为 "9876" ，"7321" 和 "8742" 。
"4321" 是满足条件最小的数字。

提示：

1 <= pattern.length <= 8
pattern 只包含字符 'I' 和 'D' 。

方法一：DFS · Go 实现

思考

要用 $1. .9$ 各至多一次排出满足 $I / D$ 的最短数字串，且字典序最小。 $p a t t e r n$ 长至多 $8$ ，全排列不超过 $9!$ ，按从小到大搜索即可。

DFS 按位尝试未用数字：已有前缀时用上一个模式约束升降。先试小数字，第一次填满的串即最小解，随即停止。

定义 $d f s (u)$ ，其中 $u$ 表示当前答案字符串的长度。从 $u = 0$ 开始搜索，直至找到第一个符合条件的字符串。

时间复杂度 $O (n!)$ ，空间复杂度 $O (n)$ 。其中 $n$ 表示字符串 $p a t t e r n$ 的长度。

func smallestNumber(pattern string) string {
	vis := make([]bool, 10)
	t := []byte{}
	ans := ""
	var dfs func(u int)
	dfs = func(u int) {
		if ans != "" {
			return
		}
		if u == len(pattern)+1 {
			ans = string(t)
			return
		}
		for i := 1; i < 10; i++ {
			if !vis[i] {
				if u > 0 && pattern[u-1] == 'I' && int(t[len(t)-1]-'0') >= i {
					continue
				}
				if u > 0 && pattern[u-1] == 'D' && int(t[len(t)-1]-'0') <= i {
					continue
				}
				vis[i] = true
				t = append(t, byte('0'+i))
				dfs(u + 1)
				vis[i] = false
				t = t[:len(t)-1]
			}
		}
	}
	dfs(0)
	return ans
}

力扣原题 · Doocs 题解来源

2397. 被列覆盖的最多行数

中等1 种解法

标签：位运算、数组、回溯、枚举、矩阵

题目、示例与约束

给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的不同列的数量。

如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被覆盖了。

形式上，假设 s = {c₁, c₂, ...., c_numSelect} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：

对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col]（0 <= col <= n - 1），col 均存在于 s 中，或者
row 中 不存在 值为 1 的单元格。

你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。

返回一个整数，表示可以由 numSelect 列构成的集合覆盖的 最大行数 。

示例 1：

输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
输出：3
解释：
图示中显示了一种覆盖 3 行的可行办法。
选择 s = {0, 2} 。
- 第 0 行被覆盖，因为其中没有出现 1 。
- 第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。
- 第 2 行未被覆盖，因为 matrix[2][1] == 1 但是 1 未存在于 s 中。
- 第 3 行被覆盖，因为 matrix[2][2] == 1 且 2 存在于 s 中。
因此，可以覆盖 3 行。
另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。

示例 2：

输入：matrix = [[1],[0]], numSelect = 1
输出：2
解释：
选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。
所以我们返回 2 。

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 12
matrix[i][j] 要么是 0 要么是 1
1 <= numSelect <= n

方法一：二进制枚举 · Go 实现

思考

选恰 $n u m S e l e c t$ 列，使被这些列覆盖全部 $1$ 的行尽量多。 $n \leq 12$ ，列子集可以枚举。

每行压成位掩码。枚举列掩码，位数等于 $n u m S e l e c t$ 时，统计满足 $r o w \land m a s k = r o w$ 的行数并取最大。

我们先将矩阵中的每一行转换成一个二进制数，记录在数组 $r o w s$ 中，其中 $r o w s [i]$ 表示第 $i$ 行对应的二进制数，而 $r o w s [i]$ 这个二进制数的第 $j$ 位表示第 $i$ 行第 $j$ 列的值。

接下来，我们枚举所有的 $2^{n}$ 种列选择方案，其中 $n$ 为矩阵的列数。对于每一种列选择方案，我们判断是否选中了 numSelect 列，如果不是，则跳过。否则，我们统计矩阵中有多少行中的所有 $1$ 都被选中的列覆盖，即统计有多少行的二进制数 $r o w s [i]$ 与列选择方案 $m a s k$ 按位与的结果等于 $r o w s [i]$ ，并更新最大的行数。

时间复杂度 $O (2^{n} \times m)$ ，空间复杂度 $O (m)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

func maximumRows(matrix [][]int, numSelect int) (ans int) {
	m, n := len(matrix), len(matrix[0])
	rows := make([]int, m)
	for i, row := range matrix {
		for j, x := range row {
			if x == 1 {
				rows[i] |= 1 << j
			}
		}
	}
	for mask := 1; mask < 1<<n; mask++ {
		if bits.OnesCount(uint(mask)) != numSelect {
			continue
		}
		t := 0
		for _, x := range rows {
			if (x & mask) == x {
				t++
			}
		}
		if ans < t {
			ans = t
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2596. 检查骑士巡视方案

中等1 种解法

标签：深度优先搜索、广度优先搜索、数组、矩阵、模拟

题目、示例与约束

骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。

给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

示例 1：

输入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
输出：true
解释：grid 如上图所示，可以证明这是一个有效的巡视方案。

示例 2：

输入：grid = [[0,3,6],[5,8,1],[2,7,4]]
输出：false
解释：grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。

提示：

n == grid.length == grid[i].length
3 <= n <= 7
0 <= grid[row][col] < n * n
grid 中的所有整数 互不相同

方法一：模拟 · Go 实现

思考

判断网格是否为骑士从 $(0, 0)$ 出发、按 $0, 1, \dots, n^{2} - 1$ 的巡游。 $n \leq 7$ ，把每个步数的坐标记下后检查相邻步是否为日字即可。起点必须是 $0$ 。

我们先用数组 $pos$ 记录骑士访问的每个格子的坐标，然后遍历 $pos$ 数组，检查相邻两个格子的坐标差是否为 $(1, 2)$ 或 $(2, 1)$ 即可。若不满足，则返回 $false$ 。

否则遍历结束后，返回 $true$

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n^{2})$ 。其中 $n$ 为棋盘的边长。

func checkValidGrid(grid [][]int) bool {
	if grid[0][0] != 0 {
		return false
	}
	n := len(grid)
	type pair struct{ x, y int }
	pos := make([]pair, n*n)
	for i, row := range grid {
		for j, x := range row {
			pos[x] = pair{i, j}
		}
	}
	for i := 1; i < n*n; i++ {
		p1, p2 := pos[i-1], pos[i]
		dx := abs(p1.x - p2.x)
		dy := abs(p1.y - p2.y)
		ok := (dx == 2 && dy == 1) || (dx == 1 && dy == 2)
		if !ok {
			return false
		}
	}
	return true
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

2664. 巡逻的骑士 🔒

中等1 种解法

标签：数组、回溯、矩阵

题目、示例与约束

给定两个正整数 m 和 n ，它们是一个 下标从 0 开始 的二维数组 board 的高度和宽度。还有一对正整数 (r, c) ，它们是骑士在棋盘上的起始位置。

你的任务是找到一个骑士的移动顺序，使得 board 中每个单元格都恰好被访问一次（起始单元格已被访问，不应再次访问）。

返回数组 board ，其中单元格的值显示从 0 开始访问该单元格的顺序（骑士的初始位置为 0）。

注意，如果 0 <= r2 <= m-1 且 0 <= c2 <= n-1 ，并且 min(abs(r1-r2), abs(c1-c2)) = 1 且 max(abs(r1-r2), abs(c1-c2)) = 2 ，则骑士可以从单元格 (r1, c1) 移动到单元格 (r2, c2) 。

示例 1 ：

输入：m = 1, n = 1, r = 0, c = 0
输出：[[0]]
解释只有一个单元格，骑士最初在其中，因此 1x1 网格中只有一个 0。

示例 2 ：

输入：m = 3, n = 4, r = 0, c = 0
输出：[[0,3,6,9],[11,8,1,4],[2,5,10,7]]
解释：按照以下移动顺序，我们可以访问整个棋盘。 
(0,0)->(1,2)->(2,0)->(0,1)->(1,3)->(2,1)->(0,2)->(2,3)->(1,1)->(0,3)->(2,2)->(1,0)

提示：

1 <= m, n <= 5
0 <= r <= m - 1
0 <= c <= n - 1
输入的数据保证在给定条件下至少存在一种访问所有单元格的移动顺序。

方法一：回溯 · Go 实现

思考

骑士须不重复走遍棋盘。棋盘至多 $5 \times 5$ ，路径搜索空间可回溯。按八个方向尝试未访问格，步号写满 $m n - 1$ 即成功并冻结棋盘。

失败则撤步。找到一路即可返回，不必枚举全部哈密顿路径。

我们创建一个二维数组 $g$ ，用于记录骑士的移动顺序，初始时 $g [r] [c] = - 1$ ，其余位置均为 $- 1$ 。另外，我们还需要一个变量 $o k$ ，用于记录是否找到了一种方案。

接下来，我们从 $(r, c)$ 开始进行深度优先搜索，每次搜索位置 $(i, j)$ 时，我们先判断 $g [i] [j]$ 是否等于 $m \times n - 1$ ，若是，说明我们已经找到了一种方案，此时将 $o k$ 置为 true 并且返回。否则我们枚举骑士的八个移动方向对应的位置 $(x, y)$ ，若满足 $0 \leq x < m$ , $0 \leq y < n$ ，并且 $g [x] [y] = - 1$ ，那么我们将 $g [x] [y]$ 更新为 $g [i] [j] + 1$ ，然后递归搜索位置 $(x, y)$ 。如果搜索结束后，变量 $o k$ 为 true，则直接返回。否则，我们将 $g [x] [y]$ 重置为 $- 1$ ，继续搜索其他方向。

最后返回二维数组 $g$ 即可。

时间复杂度 $O (8^{m \times n})$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 为题目给定的整数。

func tourOfKnight(m int, n int, r int, c int) [][]int {
	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
		for j := range g[i] {
			g[i][j] = -1
		}
	}
	g[r][c] = 0
	ok := false
	var dfs func(i, j int)
	dfs = func(i, j int) {
		if g[i][j] == m*n-1 {
			ok = true
			return
		}
		dirs := []int{-2, -1, 2, 1, -2, 1, 2, -1, -2}
		for k := 0; k < 8; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && g[x][y] == -1 {
				g[x][y] = g[i][j] + 1
				dfs(x, y)
				if ok {
					return
				}
				g[x][y] = -1
			}
		}
	}
	dfs(r, c)
	return g
}

力扣原题 · Doocs 题解来源

2698. 求一个整数的惩罚数

中等1 种解法

标签：数学、回溯

题目、示例与约束

给你一个正整数 n ，请你返回 n 的 惩罚数 。

n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：

1 <= i <= n
i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。

示例 1：

输入：n = 10
输出：182
解释：总共有 3 个范围在 [1, 10] 的整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
因此，10 的惩罚数为 1 + 81 + 100 = 182

示例 2：

输入：n = 37
输出：1478
解释：总共有 4 个范围在 [1, 37] 的整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
- 36 ，因为 36 * 36 = 1296 ，且 1296 可以分割成 1 + 29 + 6 。
因此，37 的惩罚数为 1 + 81 + 100 + 1296 = 1478

提示：

1 <= n <= 1000

方法一：枚举 + DFS · Go 实现

思考

判断 $i^{2}$ 的十进制能否分割成若干段其和为 $i$ 。 $n \leq 1000$ ，平方至多 $7$ 位，分割方案有限，枚举 $i$ 再 DFS 切分即可。

从左累积当前段，超过剩余目标则剪枝；切完时目标和为 $0$ 则合法，累加该平方。

我们枚举 $i$ ，其中 $1 \leq i \leq n$ ，对于每个 $i$ ，我们将 $x = i^{2}$ 的十进制表示的字符串进行分割，然后判断是否满足题目要求。如果满足，我们就将 $x$ 累加到答案中。

枚举结束，返回答案即可。

时间复杂度 $O (n^{1 + 2 \log_{10}^{2}})$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 为给定的正整数。

func punishmentNumber(n int) (ans int) {
	var check func(string, int, int) bool
	check = func(s string, i, x int) bool {
		m := len(s)
		if i >= m {
			return x == 0
		}
		y := 0
		for j := i; j < m; j++ {
			y = y*10 + int(s[j]-'0')
			if y > x {
				break
			}
			if check(s, j+1, x-y) {
				return true
			}
		}
		return false
	}
	for i := 1; i <= n; i++ {
		x := i * i
		s := strconv.Itoa(x)
		if check(s, 0, i) {
			ans += x
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2814. 避免淹死并到达目的地的最短时间 🔒

困难1 种解法

标签：广度优先搜索、数组、矩阵

题目、示例与约束

现给定一个 n * m 的索引从 0 开始的二维字符串网格 land，目前你站在为 "S" 的单元格上，你需要到达为 "D" 的单元格。在这片区域上还有另外三种类型的单元格：

"."：这些单元格是空的。
"X"：这些单元格是石头。
"*"：这些单元格被淹没了。

每秒钟，你可以移动到与当前单元格共享边的单元格（如果它存在）。此外，每秒钟，与被淹没的单元格共享边的每个 空单元格 也会被淹没。

在你的旅程中，有两个需要注意的问题：

你不能踩在石头单元格上。
你不能踩在被淹没的单元格上，因为你会淹死（同时，你也不能踩在在你踩上时会被淹没的单元格上）。

返回从起始位置到达目标位置所需的最小时间（以秒为单位），如果不可能达到目标位置，则返回 -1。

注意，目标位置永远不会被淹没。

示例 1：

输入：land = [["D",".","*"],[".",".","."],[".","S","."]]
输出：3
解释：下面的图片逐秒模拟了土地的变化。蓝色的单元格被淹没，灰色的单元格是石头。
 图片（0）显示了初始状态，图片（3）显示了当我们到达目标时的最终状态。正如你所看到的，我们需要 3 秒才能到达目标位置，答案是 3。
可以证明 3 是从 S 到 D 所需的最小时间。

示例 2：

输入：land = [["D","X","*"],[".",".","."],[".",".","S"]]
输出：-1
解释：下面的图片逐秒模拟了土地的变化。蓝色的单元格被淹没，灰色的单元格是石头。
图片（0）显示了初始状态。正如你所看到的，无论我们选择哪条路径，我们都会在第三秒淹没。并且从 S 到 D 的最小路径需要 4 秒。
所以答案是 -1。

示例 3：

输入：land = [["D",".",".",".","*","."],[".","X",".","X",".","."],[".",".",".",".","S","."]]
输出：6
解释：可以证明我们可以在 6 秒内到达目标位置。同时也可以证明 6 是从 S 到 D 所需的最小秒数。

提示：

2 <= n, m <= 100
land 只由 "S", "D", ".", "*" 和 "X" 组成。
恰好有一个单元格等于 "S"。
恰好有一个单元格等于 "D"。

方法一：两次 BFS · Go 实现

思考

水域每秒扩张，人不能踏入已淹没的格子。先对所有水域做多源 BFS，得到每格被淹时刻 $g [i] [j]$ ；再从起点 BFS，仅当邻格满足 $g [x] [y] > t + 1$ 时才可在时刻 $t + 1$ 进入，从而把动态洪水约束化为静态距离比较。

我们先跑一次 BFS，求出每个点到水域的最短距离，记录在数组 $g$ 中。然后再跑一次 BFS，从单元格 $(s_{i}, s_{j})$ 出发，求出到达目标单元格 $(d_{i}, d_{j})$ 的最短距离。在此过程中，如果当前单元格 $(i, j)$ 的相邻单元格 $(x, y)$ 满足 $g [x] [y] > t + 1$ ，那么我们就可以从 $(x, y)$ 走到 $(i, j)$ 。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是数组 $l a n d$ 的行数和列数。

func minimumSeconds(land [][]string) int {
	m, n := len(land), len(land[0])
	vis := make([][]bool, m)
	g := make([][]int, m)
	q := [][2]int{}
	var si, sj int
	for i, row := range land {
		vis[i] = make([]bool, n)
		g[i] = make([]int, n)
		for j := range g[i] {
			g[i][j] = 1 << 30
		}
		for j, c := range row {
			if c == "*" {
				q = append(q, [2]int{i, j})
			} else if c == "S" {
				si, sj = i, j
			}
		}
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for t := 0; len(q) > 0; t++ {
		for k := len(q); k > 0; k-- {
			p := q[0]
			q = q[1:]
			i, j := p[0], p[1]
			g[i][j] = t
			for d := 0; d < 4; d++ {
				x, y := i+dirs[d], j+dirs[d+1]
				if x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] {
					empty := land[x][y] == "."
					start := land[x][y] == "S"
					if empty || start {
						vis[x][y] = true
						q = append(q, [2]int{x, y})
					}
				}
			}
		}
	}
	q = append(q, [2]int{si, sj})
	vis = make([][]bool, m)
	for i := range vis {
		vis[i] = make([]bool, n)
	}
	vis[si][sj] = true
	for t := 0; len(q) > 0; t++ {
		for k := len(q); k > 0; k-- {
			p := q[0]
			q = q[1:]
			i, j := p[0], p[1]
			if land[i][j] == "D" {
				return t
			}
			for d := 0; d < 4; d++ {
				x, y := i+dirs[d], j+dirs[d+1]
				if x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y] > t+1 {
					empty := land[x][y] == "."
					dest := land[x][y] == "D"
					if empty || dest {
						vis[x][y] = true
						q = append(q, [2]int{x, y})
					}
				}
			}
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

3141. 最大汉明距离 🔒

困难1 种解法

标签：位运算、广度优先搜索、数组

题目、示例与约束

给定一个数组 nums 和一个整数 m，每个元素 nums[i] 满足 0 <= nums[i] < 2^m，返回数组 answer。answer 数组应该与 nums 有相同的长度，每个元素 answer[i] 表示 nums[i] 和数组中其它任何元素 nums[j] 的最大 汉明距离。

两个二进制整数之间的 汉明距离 定义为对应位上二进制位不同的数量（如果需要，添加前置零）。

示例 1：

输入：nums = [9,12,9,11], m = 4

输出：[2,3,2,3]

解释：

二进制表示为 nums = [1001,1100,1001,1011]。

每个下标的最大汉明距离为：

nums[0]：1001 与 1100 距离为 2。
nums[1]：1100 与 1011 距离为 3。
nums[2]：1001 与 1100 距离为 2。
nums[3]：1011 与 1100 距离为 3。

示例 2：

输入：nums = [3,4,6,10], m = 4

输出：[3,3,2,3]

解释：

二进制表示为 nums = [0011,0100,0110,1010]。

每个下标的最大汉明距离为：

nums[0]：0011 与 0100 距离为 3。
nums[1]：0100 与 0011 距离为 3。
nums[2]：0110 与 1010 距离为 2。
nums[3]：1010 与 0100 距离为 3。

提示：

1 <= m <= 17
2 <= nums.length <= 2^m
0 <= nums[i] < 2^m

方法一：逆向思维 + BFS · Go 实现

思考

对每个值求它与数组中某元素的最大汉明距离。若对每个数枚举其余数，在 $m$ 达 $17$ 、 $n$ 较大时过慢。

最大距离等于 $m$ 减去到「某数组元素」的最小距离。从数组中的数出发，在超立方体上按翻一位做 BFS，即可得到每个掩码到数组的最短汉明距离。

因此 $d i s t [x] = 0$ 当 $x$ 在数组中，多层扩展翻比特；对询问值 $x$ 取 $m - d i s t [x \oplus (2^{m} - 1)]$ ，即到其补码的最短距离改写成最大距离。

题目需要我们求出数组每个元素和其他元素的最大海明距离，我们不妨换个角度思考，我们对每个元素取反，然后求出其到数组中其他元素的最小海明距离，那么 $m$ 减去这个最小海明距离就是我们要求的最大海明距离。

我们可以使用广度优先搜索来求出每个取反的元素到其他元素的最小海明距离。

具体步骤如下：

初始化一个数组 $dist$ ，数组长度为 $2^{m}$ ，用来记录每个取反后的元素到其他元素的最小海明距离，初始时全部置为 $- 1$ 。
遍历数组 $nums$ ，将每个元素的取反值置为 $0$ ，并将其加入队列 $q$ 。
从 $k = 1$ 开始，不断遍历队列 $q$ ，每次遍历时，将队列中的元素取出，然后对其进行 $m$ 次取反操作，将取反后的元素加入队列 $t$ ，并将其到原元素的最小海明距离置为 $k$ 。
重复步骤 3，直到队列为空。

最后，我们遍历数组 $nums$ ，将每个元素取反后的值作为下标，从 $dist$ 数组中取出对应的最小海明距离，然后用 $m$ 减去这个值，就是我们要求的最大海明距离。

时间复杂度 $O (2^{m})$ ，空间复杂度 $O (2^{m})$ 。其中 $m$ 为题目给定的整数。

func maxHammingDistances(nums []int, m int) []int {
	dist := make([]int, 1<<m)
	for i := range dist {
		dist[i] = -1
	}
	q := []int{}
	for _, x := range nums {
		dist[x] = 0
		q = append(q, x)
	}
	for k := 1; len(q) > 0; k++ {
		t := []int{}
		for _, x := range q {
			for i := 0; i < m; i++ {
				y := x ^ (1 << i)
				if dist[y] == -1 {
					dist[y] = k
					t = append(t, y)
				}
			}
		}
		q = t
	}
	for i, x := range nums {
		nums[i] = m - dist[x^(1<<m-1)]
	}
	return nums
}

力扣原题 · Doocs 题解来源

3211. 生成不含相邻零的二进制字符串

中等1 种解法

标签：位运算、字符串、回溯

题目、示例与约束

给你一个正整数 n。

如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含至少一个 "1"，则称 x 是一个有效字符串。

返回所有长度为 n 的有效字符串，可以以任意顺序排列。

示例 1：

输入： n = 3

输出： ["010","011","101","110","111"]

解释：

长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。

示例 2：

输入： n = 1

输出： ["0","1"]

解释：

长度为 1 的有效字符串有："0" 和 "1"。

提示：

1 <= n <= 18

方法一：DFS · Go 实现

思考

$n \leq 18$ ，长度为 $n$ 的二进制串共 $2^{n}$ 个，先生成再过滤相邻 $00$ 可以接受，但大量非法前缀不必展开。

按位 DFS：在位置 $i$ 尝试填 $0$ 或 $1$ ，仅当填 $0$ 时要求 $i = 0$ 或前一位为 $1$ 。走到长度 $n$ 即收入答案。剪枝后搜索树恰好对应全体合法串。

我们可以枚举长度为 $n$ 的二进制字符串的每个位置 $i$ ，然后对于每个位置 $i$ ，我们可以枚举其可以取的值 $j$ ，如果 $j$ 为 $0$ ，那么我们需要判断其前一个位置是否为 $1$ ，如果为 $1$ ，则可以继续递归下去，否则不合法，如果 $j$ 为 $1$ ，则直接递归下去。

时间复杂度 $O (n \times 2^{n})$ ，其中 $n$ 为字符串长度。忽略答案数组的空间消耗，空间复杂度 $O (n)$ 。

func validStrings(n int) (ans []string) {
	t := []byte{}
	var dfs func(int)
	dfs = func(i int) {
		if i >= n {
			ans = append(ans, string(t))
			return
		}
		for j := 0; j < 2; j++ {
			if (j == 0 && (i == 0 || t[i-1] == '1')) || j == 1 {
				t = append(t, byte('0'+j))
				dfs(i + 1)
				t = t[:len(t)-1]
			}
		}
	}
	dfs(0)
	return
}

力扣原题 · Doocs 题解来源

3283. 吃掉所有兵需要的最多移动次数

困难1 种解法

标签：位运算、广度优先搜索、数组、数学、位掩码、博弈

题目、示例与约束

给你一个 50 x 50 的国际象棋棋盘，棋盘上有一个马和一些兵。给你两个整数 kx 和 ky ，其中 (kx, ky) 表示马所在的位置，同时还有一个二维数组 positions ，其中 positions[i] = [x_i, y_i] 表示第 i 个兵在棋盘上的位置。

Alice 和 Bob 玩一个回合制游戏，Alice 先手。玩家的一次操作中，可以执行以下操作：

玩家选择一个仍然在棋盘上的兵，然后移动马，通过最少的步数吃掉这个兵。注意，玩家可以选择任意一个兵，不一定 要选择从马的位置出发最少移动步数的兵。
在马吃兵的过程中，马可能会经过一些其他兵的位置，但这些兵不会被吃掉。只有选中的兵在这个回合中被吃掉。

Alice 的目标是 最大化 两名玩家的总移动次数，直到棋盘上不再存在兵，而 Bob 的目标是 最小化 总移动次数。

假设两名玩家都采用最优策略，请你返回可以达到的最大总移动次数。

在一次移动中，如下图所示，马有 8 个可以移动到的位置，每个移动位置都是沿着坐标轴的一个方向前进 2 格，然后沿着垂直的方向前进 1 格。

示例 1：

输入：kx = 1, ky = 1, positions = [[0,0]]

输出：4

解释：

马需要移动 4 步吃掉 (0, 0) 处的兵。

示例 2：

输入：kx = 0, ky = 2, positions = [[1,1],[2,2],[3,3]]

输出：8

解释：

Alice 选择 (2, 2) 处的兵，移动马吃掉它需要 2 步：(0, 2) -> (1, 4) -> (2, 2) 。
Bob 选择 (3, 3) 处的兵，移动马吃掉它需要 2 步：(2, 2) -> (4, 1) -> (3, 3) 。
Alice 选择 (1, 1) 处的兵，移动马吃掉它需要 4 步：(3, 3) -> (4, 1) -> (2, 2) -> (0, 3) -> (1, 1) 。

示例 3：

输入：kx = 0, ky = 0, positions = [[1,2],[2,4]]

输出：3

解释：

Alice 选择 (2, 4) 处的兵，移动马吃掉它需要 2 步：(0, 0) -> (1, 2) -> (2, 4) 。注意，(1, 2) 处的兵不会被吃掉。
Bob 选择 (1, 2) 处的兵，移动马吃掉它需要 1 步：(2, 4) -> (1, 2) 。

提示：

0 <= kx, ky <= 49
1 <= positions.length <= 15
positions[i].length == 2
0 <= positions[i][0], positions[i][1] <= 49
positions[i] 两两互不相同。
输入保证对于所有 0 <= i < positions.length ，都有 positions[i] != [kx, ky] 。

方法一：BFS + 状态压缩 + 记忆化搜索 · Go 实现

思考

马要轮流吃光至多 $15$ 个兵，Alice 最大化总步、Bob 最小化。棋盘 $50 \times 50$ ，对每个兵做一次 BFS 得到马步距离；吃兵顺序是 $15!$ 量级，需状态压缩博弈。

$dfs (l a s t, s t a t e, k)$ ： $l a s t$ 为上一个被吃的兵（初值为马的位置）， $s t a t e$ 为剩余兵集合， $k$ 为是否 Alice。Alice 取最大、Bob 取最小，边权用预处理的 $d i s t [l a s t] [x] [y]$ 。记忆化后状态 $O (n \cdot 2^{n})$ 。

我们首先预处理出每个兵到棋盘上任意一个位置的马的最短距离，记录在数组 $dist$ 中，即 $dist [i] [x] [y]$ 表示第 $i$ 个兵到 $(x, y)$ 位置的马的最短距离。

接下来，我们设计一个函数 $dfs (last, state, k)$ ，其中 $last$ 表示上一个吃掉的兵的编号，而 $state$ 表示当前还剩下的兵的状态，而 $k$ 表示当前是 Alice 还是 Bob 的回合。函数的返回值表示当前回合的最大移动次数。那么答案为 $dfs (n, 2^{n} - 1, 1)$ 。这里我们初始时上一个吃掉的兵的编号记为 $n$ ，这也是马所在的位置。

函数 $dfs$ 的具体实现如下：

如果 $state = 0$ ，表示没有兵了，返回 $0$ ；
如果 $k = 1$ ，表示当前是 Alice 的回合，我们需要找到一个兵，使得吃掉这个兵后的移动次数最大，即 $dfs (i, state \oplus 2^{i}, k \oplus 1) + dist [last] [x] [y]$ ；
如果 $k = 0$ ，表示当前是 Bob 的回合，我们需要找到一个兵，使得吃掉这个兵后的移动次数最小，即 $dfs (i, state \oplus 2^{i}, k \oplus 1) + dist [last] [x] [y]$ 。

为了避免重复计算，我们使用记忆化搜索，即使用哈希表记录已经计算过的状态。

时间复杂度 $O (n \times m^{2} + 2^{n} \times n^{2})$ ，空间复杂度 $O (n \times m^{2} + 2^{n} \times n)$ 。其中 $n$ 和 $m$ 分别为兵的数量和棋盘的大小。

func maxMoves(kx int, ky int, positions [][]int) int {
	n := len(positions)
	const m = 50
	dx := []int{1, 1, 2, 2, -1, -1, -2, -2}
	dy := []int{2, -2, 1, -1, 2, -2, 1, -1}
	dist := make([][][]int, n+1)
	for i := range dist {
		dist[i] = make([][]int, m)
		for j := range dist[i] {
			dist[i][j] = make([]int, m)
			for k := range dist[i][j] {
				dist[i][j][k] = -1
			}
		}
	}

	for i := 0; i <= n; i++ {
		x := kx
		y := ky
		if i < n {
			x = positions[i][0]
			y = positions[i][1]
		}
		q := [][2]int{[2]int{x, y}}
		dist[i][x][y] = 0

		for step := 1; len(q) > 0; step++ {
			for k := len(q); k > 0; k-- {
				p := q[0]
				q = q[1:]
				x1, y1 := p[0], p[1]
				for j := 0; j < 8; j++ {
					x2 := x1 + dx[j]
					y2 := y1 + dy[j]
					if x2 >= 0 && x2 < m && y2 >= 0 && y2 < m && dist[i][x2][y2] == -1 {
						dist[i][x2][y2] = step
						q = append(q, [2]int{x2, y2})
					}
				}
			}
		}
	}
	f := make([][][]int, n+1)
	for i := range f {
		f[i] = make([][]int, 1<<n)
		for j := range f[i] {
			f[i][j] = make([]int, 2)
			for k := range f[i][j] {
				f[i][j][k] = -1
			}
		}
	}
	var dfs func(last, state, k int) int
	dfs = func(last, state, k int) int {
		if state == 0 {
			return 0
		}
		if f[last][state][k] != -1 {
			return f[last][state][k]
		}

		var res int
		if k == 0 {
			res = math.MaxInt32
		}

		for i, p := range positions {
			x, y := p[0], p[1]
			if (state>>i)&1 == 1 {
				t := dfs(i, state^(1<<i), k^1) + dist[last][x][y]
				if k == 1 {
					res = max(res, t)
				} else {
					res = min(res, t)
				}
			}
		}
		f[last][state][k] = res
		return res
	}

	return dfs(n, (1<<n)-1, 1)
}

力扣原题 · Doocs 题解来源

LeetCode Go · 回溯与搜索（4） ​

1718. 构建字典序最大的可行序列 ​

1730. 获取食物的最短路径 🔒 ​

1743. 从相邻元素对还原数组 ​

1765. 地图中的最高点 ​

1778. 未知网格中的最短路径 🔒 ​

1849. 将字符串拆分为递减的连续值 ​

1863. 找出所有子集的异或总和再求和 ​

1926. 迷宫中离入口最近的出口 ​

1980. 找出不同的二进制字符串 ​

1992. 找到所有的农场组 ​

2014. 重复 K 次的最长子序列 ​

2044. 统计按位或能得到最大值的子集数目 ​

2048. 下一个更大的数值平衡数 ​

2056. 棋盘上有效移动组合的数目 ​

2059. 转化数字的最小运算数 ​

2146. 价格范围内最高排名的 K 样物品 ​

2151. 基于陈述统计最多好人数 ​

2174. 通过翻转行或列来去除所有的 1 II 🔒 ​

2178. 拆分成最多数目的正偶数之和 ​

2212. 射箭比赛中的最大得分 ​

2258. 逃离火灾 ​

2375. 根据模式串构造最小数字 ​

2397. 被列覆盖的最多行数 ​

2596. 检查骑士巡视方案 ​

2664. 巡逻的骑士 🔒 ​

2698. 求一个整数的惩罚数 ​

2814. 避免淹死并到达目的地的最短时间 🔒 ​

3141. 最大汉明距离 🔒 ​

3211. 生成不含相邻零的二进制字符串 ​

3283. 吃掉所有兵需要的最多移动次数 ​

继续阅读

LeetCode Go · 回溯与搜索（4）

1718. 构建字典序最大的可行序列

1730. 获取食物的最短路径 🔒

1743. 从相邻元素对还原数组

1765. 地图中的最高点

1778. 未知网格中的最短路径 🔒

1849. 将字符串拆分为递减的连续值

1863. 找出所有子集的异或总和再求和

1926. 迷宫中离入口最近的出口

1980. 找出不同的二进制字符串

1992. 找到所有的农场组

2014. 重复 K 次的最长子序列

2044. 统计按位或能得到最大值的子集数目

2048. 下一个更大的数值平衡数

2056. 棋盘上有效移动组合的数目

2059. 转化数字的最小运算数

2146. 价格范围内最高排名的 K 样物品

2151. 基于陈述统计最多好人数

2174. 通过翻转行或列来去除所有的 1 II 🔒

2178. 拆分成最多数目的正偶数之和

2212. 射箭比赛中的最大得分

2258. 逃离火灾

2375. 根据模式串构造最小数字

2397. 被列覆盖的最多行数

2596. 检查骑士巡视方案

2664. 巡逻的骑士 🔒

2698. 求一个整数的惩罚数

2814. 避免淹死并到达目的地的最短时间 🔒

3141. 最大汉明距离 🔒

3211. 生成不含相邻零的二进制字符串

3283. 吃掉所有兵需要的最多移动次数