LeetCode Go · 数学与几何（3）

812. 最大三角形面积

简单1 种解法

标签：几何、数组、数学、多边形

题目、示例与约束

给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [x_i, y_i] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10^-5 内的答案将会视为正确答案。

示例 1：

输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出：2.00000
解释：输入中的 5 个点如上图所示，红色的三角形面积最大。

示例 2：

输入：points = [[1,0],[0,0],[0,1]]
输出：0.50000

提示：

3 <= points.length <= 50
-50 <= x_i, y_i <= 50
给出的所有点 互不相同

方法一：枚举三点面积公式 · Go 实现

思考

最大三角形面积由三点叉积的一半给出。点数至多 $50$ ，三重枚举约 $10^{5}$ 次可接受。

对每组三点用向量叉积取绝对值的一半，维护全局最大值。共线三点面积为 $0$ ，不会干扰答案。

给定平面上三点 $(x_{1}, y_{1})$ , $(x_{2}, y_{2})$ , $(x_{3}, y_{3})$ ，其面积公式为：

S = \frac{1}{2} | x_{1} y_{2} + x_{2} y_{3} + x_{3} y_{1} - x_{1} y_{3} - x_{2} y_{1} - x_{3} y_{2} |

我们可以枚举所有的三点组合，计算面积的最大值。

时间复杂度 $O (n^{3})$ ，其中 $n$ 是点的数量。空间复杂度 $O (1)$ 。

go

func largestTriangleArea(points [][]int) float64 {
	ans := 0.0
	for _, p1 := range points {
		x1, y1 := p1[0], p1[1]
		for _, p2 := range points {
			x2, y2 := p2[0], p2[1]
			for _, p3 := range points {
				x3, y3 := p3[0], p3[1]
				u1, v1 := x2-x1, y2-y1
				u2, v2 := x3-x1, y3-y1
				t := float64(abs(u1*v2-u2*v1)) / 2.0
				ans = math.Max(ans, t)
			}
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

829. 连续整数求和

困难1 种解法

标签：数学、枚举

题目、示例与约束

给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。

示例 1:

输入: n = 5
输出: 2
解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。

示例 2:

输入: n = 9
输出: 3
解释: 9 = 4 + 5 = 2 + 3 + 4

示例 3:

输入: n = 15
输出: 4
解释: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提示:

1 <= n <= 10⁹

方法一：数学推导 · Go 实现

思考

$n$ 写成 $k$ 个连续正整数之和，即 $n = k \cdot a + k (k - 1) / 2$ 。 $n$ 达 $10^{9}$ ，枚举起点不可行，应枚举长度 $k$ 。

整理得 $2 n / k - k + 1$ 为偶数正整数。 $k (k + 1) \leq 2 n$ 即可枚举完所有合法长度，判断整除与奇偶后计数。

连续正整数构成一个公差 $d = 1$ 的等差数列。我们假设等差数列的第一项为 $a$ ，项数为 $k$ ，那么 $n = (a + a + k - 1) \times k / 2$ ，即 $n \times 2 = (a \times 2 + k - 1) \times k$ 。这里我们可以得出 $k$ 一定能整除 $n \times 2$ ，并且 $(n \times 2) / k - k + 1$ 一定是偶数。

由于 $a \geq 1$ ，所以 $n \times 2 = (a \times 2 + k - 1) \times k \geq k \times (k + 1)$ 。

综上，我们可以得出：

$k$ 一定能整除 $n \times 2$ ；
$k \times (k + 1) \leq n \times 2$ ；
$(n \times 2) / k - k + 1$ 一定是偶数。

我们从 $k = 1$ 开始枚举，当 $k \times (k + 1) > n \times 2$ 时，我们可以结束枚举。在枚举的过程中，我们判断 $k$ 是否能整除 $n \times 2$ ，并且 $(n \times 2) / k - k + 1$ 是否是偶数，如果是则满足条件，答案加一。

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

时间复杂度 $O (\sqrt{n})$ ，其中 $n$ 为给定的正整数。空间复杂度 $O (1)$ 。

go

func consecutiveNumbersSum(n int) int {
	n <<= 1
	ans := 0
	for k := 1; k*(k+1) <= n; k++ {
		if n%k == 0 && (n/k+1-k)%2 == 0 {
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

836. 矩形重叠

简单1 种解法

标签：几何、数学

题目、示例与约束

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。

如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

示例 1：

输入： rec1 = [0,0,2,2], rec2 = [1,1,3,3]

输出： true

解释：

两个矩形在由 (1,1)、(2,1)、(1,2) 和 (2,2) 四个顶点围成的区域内重叠。

该区域的面积大于零，因此两个矩形重叠。

示例 2：

输入： rec1 = [0,0,1,1], rec2 = [1,0,2,1]

输出： false

解释：

两个矩形共用 x = 1 处的竖直边，但它们没有任何公共的内部区域。

由于它们的交集面积为零，因此两个矩形不重叠。

示例 3：

输入： rec1 = [0,0,1,1], rec2 = [2,2,3,3]

输出： false

解释：

两个矩形完全分离。矩形 rec1 在 x = 1 和 y = 1 处结束，而矩形 rec2 从 x = 2 和 y = 2 处开始。

因此，它们没有任何公共点，也就不存在重叠。

提示：

rec1.length == 4
rec2.length == 4
-10⁹ <= rec1[i], rec2[i] <= 10⁹
rec1 和 rec2 表示一个面积不为零的有效矩形

方法一：判断不重叠的情况 · Go 实现

思考

判断两个轴对齐矩形是否有正面积相交。直接描述相交区域的边界较繁，补集更干净：上下错开或左右错开则不相交。

四个不等式任一成立即分离，对其取反便得到重叠判定。题目保证矩形面积非零，无需处理退化边。

我们记矩形 $rec1$ 的坐标点为 $(x_{1}, y_{1}, x_{2}, y_{2})$ ，矩形 $rec2$ 的坐标点为 $(x_{3}, y_{3}, x_{4}, y_{4})$ 。

那么当满足以下任一条件时，矩形 $rec1$ 和 $rec2$ 不重叠：

满足 $y_{3} \geq y_{2}$ ，即 $rec2$ 在 $rec1$ 的上方；
满足 $y_{4} \leq y_{1}$ ，即 $rec2$ 在 $rec1$ 的下方；
满足 $x_{3} \geq x_{2}$ ，即 $rec2$ 在 $rec1$ 的右方；
满足 $x_{4} \leq x_{1}$ ，即 $rec2$ 在 $rec1$ 的左方。

当以上条件都不满足时，矩形 $rec1$ 和 $rec2$ 重叠。

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

go

func isRectangleOverlap(rec1 []int, rec2 []int) bool {
	x1, y1, x2, y2 := rec1[0], rec1[1], rec1[2], rec1[3]
	x3, y3, x4, y4 := rec2[0], rec2[1], rec2[2], rec2[3]
	return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1)
}

力扣原题 · Doocs 题解来源

840. 矩阵中的幻方

中等1 种解法

标签：数组、哈希表、数学、矩阵

题目、示例与约束

3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？

注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。

示例 1：

输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]
输出: 1
解释: 
下面的子矩阵是一个 3 x 3 的幻方：

而这一个不是：

总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

示例 2:

输入: grid = [[8]]
输出: 0

提示:

row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

方法一：枚举 · Go 实现

思考

幻方是 $1 \dots 9$ 各出现一次且三行三列两对角线和相等。网格至多 $10 \times 10$ ，枚举每个 $3 \times 3$ 左上角即可。

对窗口统计集合、行列和与对角线和，有重复、越界或不等于对角线和则否。累加合法窗口个数。

我们直接枚举每个 $3 \times 3$ 子矩阵的左上角坐标 $(i, j)$ ，然后判断该子矩阵是否满足“幻方矩阵”，若是，答案加一。枚举结束后，返回答案即可。

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

go

func numMagicSquaresInside(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	check := func(i, j int) int {
		if i+3 > m || j+3 > n {
			return 0
		}
		cnt := [16]int{}
		row := [3]int{}
		col := [3]int{}
		a, b := 0, 0
		for x := i; x < i+3; x++ {
			for y := j; y < j+3; y++ {
				v := grid[x][y]
				if v < 1 || v > 9 || cnt[v] > 0 {
					return 0
				}
				cnt[v]++
				row[x-i] += v
				col[y-j] += v
				if x-i == y-j {
					a += v
				}
				if x-i == 2-(y-j) {
					b += v
				}
			}
		}
		if a != b {
			return 0
		}
		for k := 0; k < 3; k++ {
			if row[k] != a || col[k] != a {
				return 0
			}
		}
		return 1
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			ans += check(i, j)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

843. 猜猜这个单词

困难1 种解法

标签：极小化极大、数组、数学、字符串、博弈、交互

题目、示例与约束

给你一个由不同字符串组成的单词列表 words ，其中 words[i] 长度均为 6 。words 中的一个单词将被选作秘密单词 secret 。

另给你一个辅助对象 Master ，你可以调用 Master.guess(word) 来猜单词，其中参数 word 长度为 6 且必须是 words 中的字符串。

Master.guess(word) 将会返回如下结果：

如果 word 不是 words 中的字符串，返回 -1 ，或者
一个整数，表示你所猜测的单词 word 与 秘密单词 secret 的准确匹配（值和位置同时匹配）的数目。

每组测试用例都会包含一个参数 allowedGuesses ，其中 allowedGuesses 是你可以调用 Master.guess(word) 的最大次数。

对于每组测试用例，在不超过允许猜测的次数的前提下，你应该调用 Master.guess 来猜出秘密单词。最终，你将会得到以下结果：

如果你调用 Master.guess 的次数大于 allowedGuesses 所限定的次数或者你没有用 Master.guess 猜到秘密单词，则得到 "Either you took too many guesses, or you did not find the secret word." 。
如果你调用 Master.guess 猜到秘密单词，且调用 Master.guess 的次数小于或等于 allowedGuesses ，则得到 "You guessed the secret word correctly." 。

生成的测试用例保证你可以利用某种合理的策略（而不是暴力）猜到秘密单词。

示例 1：

输入：secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：
master.guess("aaaaaa") 返回 -1 ，因为 "aaaaaa" 不在 words 中。
master.guess("acckzz") 返回 6 ，因为 "acckzz" 是秘密单词 secret ，共有 6 个字母匹配。
master.guess("ccbazz") 返回 3 ，因为 "ccbazz" 共有 3 个字母匹配。
master.guess("eiowzz") 返回 2 ，因为 "eiowzz" 共有 2 个字母匹配。
master.guess("abcczz") 返回 4 ，因为 "abcczz" 共有 4 个字母匹配。
一共调用 5 次 master.guess ，其中一个为秘密单词，所以通过测试用例。

示例 2：

输入：secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：共有 2 个单词，且其中一个为秘密单词，可以通过测试用例。

提示：

1 <= words.length <= 100
words[i].length == 6
words[i] 仅由小写英文字母组成
words 中所有字符串 互不相同
secret 存在于 words 中
10 <= allowedGuesses <= 30

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

Doocs 参考题解 · CC BY-SA 4.0

根据题意整理：本地 Doocs 实现围栏为空，不能称为已有代码的翻译。预计算任意两词相同位置的字符数。维护仍可能为秘密词的候选集合，每轮枚举未猜过的词，把候选按反馈值分桶，选择最大桶最小的词（极小化最坏剩余规模）；相同时优先猜候选词。调用平台后，只保留匹配数等于反馈的候选，反馈为 6 即结束。

变量与复杂度：N 为单词数，L=6 为词长，G 为实际猜测次数。matches 保存两词匹配数，candidates 保存候选下标，used 防止重复猜测。预处理 O(N²L)，搜索 O(GN²)，空间 O(N²)。采用题目要求的合理划分策略；allowedGuesses 由评测掌握，不是函数入参，不使用随机试猜。

平台接口：函数 findSecretWord(words []string, master *Master) 无返回值。Master 由平台提供，其 Guess(word string) int 返回 -1 或 0..6；测试中的 Master 是本地 mock，不发起网络请求。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

go

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/0800-0899/0843.Guess%20the%20Word/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

func findSecretWord(words []string, master *Master) {
	n := len(words)
	matches := make([][]int, n)
	candidates := make([]int, n)
	used := make([]bool, n)
	for i := range words {
		candidates[i] = i
		matches[i] = make([]int, n)
		for j := range words {
			for k := 0; k < 6; k++ {
				if words[i][k] == words[j][k] {
					matches[i][j]++
				}
			}
		}
	}
	for len(candidates) > 0 {
		possible := make([]bool, n)
		for _, i := range candidates {
			possible[i] = true
		}
		best, worstBest := -1, n+1
		for i := range words {
			if used[i] {
				continue
			}
			buckets := [6]int{}
			for _, j := range candidates {
				if matches[i][j] < 6 {
					buckets[matches[i][j]]++
				}
			}
			worst := 0
			for _, count := range buckets {
				if count > worst {
					worst = count
				}
			}
			if worst < worstBest || (worst == worstBest && possible[i] && !possible[best]) {
				best, worstBest = i, worst
			}
		}
		used[best] = true
		response := master.Guess(words[best])
		if response == 6 || response < 0 {
			return
		}
		next := make([]int, 0, len(candidates))
		for _, j := range candidates {
			if matches[best][j] == response {
				next = append(next, j)
			}
		}
		candidates = next
	}
}

力扣原题 · Doocs 题解来源

858. 镜面反射

中等1 种解法

标签：几何、数学、最大公约数、数论、最小公倍数

题目、示例与约束

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。

正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。

返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。

示例 1：

输入：p = 2, q = 1
输出：2
解释：这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。

示例 2：

输入：p = 3, q = 1
输入：1

提示：

1 <= q <= p <= 1000

方法一：数学 · Go 实现

思考

光线在正方形房间内反射，可展成网格上的直线，首次碰到的受体对应「横向奇数/偶数个房间、纵向奇数/偶数个房间」。

约去 $p, q$ 的最大公因数后看二者奇偶：同奇则受体 $1$ ，横奇纵偶为 $0$ ，横偶纵奇为 $2$ 。

根据题意，光线在每次反射时，都会向上或向下移动 $q$ 的距离，向右移动 $p$ 的距离。而由于光线最后一定会遇到接收器，因此，我们需要找到一个最小的 $k$ ，使得 $k \times q$ 是 $p$ 的倍数。

同时，根据 $k$ 的奇偶性，我们可以确定光线最终到达了西侧还是东侧。如果 $k$ 是偶数，那么光线最终到达的是西侧，否则光线最终到达的是东侧。

另外，根据 $k \times q$ 除以 $p$ 的结果的奇偶性，我们可以确定光线最终到达的是北侧还是南侧。如果 $k \times q$ 是 $p$ 的偶数倍，那么光线最终到达的是南侧，否则光线最终到达的是北侧。

时间复杂度 $O (\log p)$ ，空间复杂度 $O (1)$ 。

go

func mirrorReflection(p int, q int) int {
	g := gcd(p, q)
	p = (p / g) % 2
	q = (q / g) % 2
	if p == 1 && q == 1 {
		return 1
	}
	if p == 1 {
		return 0
	}
	return 2
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

力扣原题 · Doocs 题解来源

866. 回文质数

中等1 种解法

标签：数学、数论、素性测试

题目、示例与约束

给你一个整数 n ，返回大于或等于 n 的最小 回文质数。

一个整数如果恰好有两个除数：1 和它本身，那么它是质数。注意，1 不是质数。

例如，2、3、5、7、11 和 13 都是质数。

一个整数如果从左向右读和从右向左读是相同的，那么它是 回文数 。

例如，101 和 12321 都是回文数。

测试用例保证答案总是存在，并且在 [2, 2 * 10⁸] 范围内。

示例 1：

输入：n = 6
输出：7

示例 2：

输入：n = 8
输出：11

示例 3：

输入：n = 13
输出：101

提示：

1 <= n <= 10⁸

方法一 · Go 实现

思考

求不小于 $n$ 的最小回文素数。 $n$ 达 $10^{8}$ ，从 $n$ 起逐个判断素数在最坏情况下偏慢，但偶数位数回文必被 $11$ 整除。

因此在 $(10^{7}, 10^{8})$ 直接跳到 $10^{8}$ 。其余情况递增并同时检测回文与素性，保证找到的第一个即答案。

go

func primePalindrome(n int) int {
	isPrime := func(x int) bool {
		if x < 2 {
			return false
		}
		for v := 2; v*v <= x; v++ {
			if x%v == 0 {
				return false
			}
		}
		return true
	}

	reverse := func(x int) int {
		res := 0
		for x != 0 {
			res = res*10 + x%10
			x /= 10
		}
		return res
	}
	for {
		if reverse(n) == n && isPrime(n) {
			return n
		}
		if n > 10000000 && n < 100000000 {
			n = 100000000
		}
		n++
	}
}

力扣原题 · Doocs 题解来源

869. 重新排序得到 2 的幂

中等1 种解法

标签：哈希表、数学、计数、枚举、排序

题目、示例与约束

给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

示例 1：

输入：n = 1
输出：true

示例 2：

输入：n = 10
输出：false

提示：

1 <= n <= 10⁹

方法一：枚举 · Go 实现

思考

判断 $n$ 的数位重排能否得到 $2$ 的幂。 $n \leq 10^{9}$ ，全排列最多 $10!$ 且有重复，而 $2^{0} \dots 2^{30}$ 只有三十余个。

比较 $n$ 与每个不超过 $10^{9}$ 的 $2$ 的幂的数位计数是否相同。有一组相同即成功。

我们可以在 $[1, 10^{9}]$ 的范围内枚举所有的 $2$ 的幂，判断它们的数字组成是否与给定的数字相同。

定义一个函数 $f (x)$ ，表示数字 $x$ 的数字组成。我们可以将数字 $x$ 转换为一个长度为 $10$ 的数组，或者一个按数字大小排序的字符串。

首先，我们计算给定数字 $n$ 的数字组成 $target = f (n)$ 。然后，我们枚举 $i$ 从 1 开始，每次将 $i$ 左移一位（相当于乘以 $2$ ），直到 $i$ 超过 $10^{9}$ 。对于每个 $i$ ，我们计算它的数字组成，并与 $target$ 进行比较。如果相同，则返回 $true$ ；如果枚举结束仍未找到相同的数字组成，则返回 $false$ 。

时间复杂度 $O (\log^{2} M)$ ，空间复杂度 $O (\log M)$ 。其中 $M$ 是本题的输入范围上限 $10^{9}$ 。

go

func reorderedPowerOf2(n int) bool {
	target := f(n)
	for i := 1; i <= 1000000000; i <<= 1 {
		if bytes.Equal(target, f(i)) {
			return true
		}
	}
	return false
}

func f(x int) []byte {
	cnt := make([]byte, 10)
	for x > 0 {
		cnt[x%10]++
		x /= 10
	}
	return cnt
}

力扣原题 · Doocs 题解来源

883. 三维形体投影面积

简单1 种解法

标签：几何、数组、数学、矩阵

题目、示例与约束

在 n x n 的网格 grid 中，我们放置了一些与 x，y，z 三轴对齐的 1 x 1 x 1 立方体。

每个值 v = grid[i][j] 表示有一列 v 个正方体叠放在格子 (i, j) 上。

现在，我们查看这些立方体在 xy 、yz 和 zx 平面上的投影。

投影就像影子，将三维形体映射到一个二维平面上。从顶部、前面和侧面看立方体时，我们会看到“影子”。

返回 所有三个投影的总面积 。

示例 1：

输入：[[1,2],[3,4]]
输出：17
解释：这里有该形体在三个轴对齐平面上的三个投影(“阴影部分”)。

示例 2:

输入：grid = [[2]]
输出：5

示例 3：

输入：[[1,0],[0,2]]
输出：8

提示：

n == grid.length == grid[i].length
1 <= n <= 50
0 <= grid[i][j] <= 50

方法一：数学 · Go 实现

思考

三个投影分别是俯视非零格数、每行最大值之和、每列最大值之和。 $n \leq 50$ ，一次遍历即可算出三项。

俯视对 $v > 0$ 计数，正视取每行之最大，侧视取每列之最大，三者相加。

我们可以分别计算三个投影的面积。

xy 平面的投影面积：每个非零值都会投影到 xy 平面，所以 xy 的投影面积为非零值的个数。
yz 平面的投影面积：每一行的最大值。
zx 平面的投影面积：每一列的最大值。

最后将三个面积相加即可。

时间复杂度 $O (n^{2})$ ，其中 $n$ 为网格 grid 的边长。空间复杂度 $O (1)$ 。

go

func projectionArea(grid [][]int) int {
	xy, yz, zx := 0, 0, 0
	for i, row := range grid {
		maxYz, maxZx := 0, 0
		for j, v := range row {
			if v > 0 {
				xy++
			}
			maxYz = max(maxYz, v)
			maxZx = max(maxZx, grid[j][i])
		}
		yz += maxYz
		zx += maxZx
	}
	return xy + yz + zx
}

力扣原题 · Doocs 题解来源

891. 子序列宽度之和

困难1 种解法

标签：数组、数学、排序

题目、示例与约束

一个序列的宽度定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 10⁹ + 7 取余后的结果。

子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。

示例 1：

输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。

示例 2：

输入：nums = [2]
输出：0

提示：

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

方法一：排序 + 枚举元素计算贡献 · Go 实现

思考

所有子序列宽度之和。子序列达 $2^{n}$ ， $n \leq 10^{5}$ ，不能枚举。宽度只依赖最大最小值，排序后第 $i$ 个数作为最大（最小）的子序列个数是 $2^{i}$ （ $2^{n - 1 - i}$ ）。

排序后一次扫描，用 $v \cdot 2^{i} - nums [n - 1 - i] \cdot 2^{i}$ 累加贡献并滚动幂次，最后取模。

题目求解的是数组 nums 中所有子序列中最大值与最小值差值之和，注意到“子序列”，并且涉及到“最大值”与“最小值”，我们考虑先对数组 nums 进行排序。

然后我们枚举数组 nums 中的每个元素 $n u m s [i]$ ，该元素左侧的元素个数为 $i$ ，右侧的元素个数为 $n - i - 1$ 。

如果我们将元素 $n u m s [i]$ 作为子序列的最大值，总共有多少个满足条件的子序列呢？显然，子序列的其他元素应该从左侧的 $i$ 个元素中选取，每个元素有两种选择，即选或不选，因此总共有 $2^{i}$ 个子序列。同理，如果我们将元素 $n u m s [i]$ 作为子序列的最小值，那么总共有 $2^{n - i - 1}$ 个满足条件的子序列。因此 $n u m s [i]$ 对答案的贡献为：

\begin{array}{r} n u m s [i] \times (2^{i} - 2^{n - i - 1}) \end{array}

我们将数组 nums 中所有元素的贡献累加，即为答案：

\begin{array}{r} \sum_{i = 0}^{n - 1} n u m s [i] \times (2^{i} - 2^{n - i - 1}) \end{array}

我们将上式展开，可以得到：

\begin{array}{r} n u m s [0] \times (2^{0} - 2^{n - 1}) + n u m s [1] \times (2^{1} - 2^{n - 2}) + . . . + n u m s [n - 1] \times (2^{n - 1} - 2^{0}) \end{array}

再将式子中相同的幂次项合并，可以得到：

\begin{array}{r} (n u m s [0] - n u m s [n - 1]) \times 2^{0} + (n u m s [1] - n u m s [n - 2]) \times 2^{1} + . . . + (n u m s [n - 1] - n u m s [0]) \times 2^{n - 1} \end{array}

即：

\begin{array}{r} \sum_{i = 0}^{n - 1} (n u m s [i] - n u m s [n - i - 1]) \times 2^{i} \end{array}

因此我们只需要对数组 nums 进行排序，然后计算上述的贡献即可。注意答案的取模操作。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 为数组 nums 的长度。

go

func sumSubseqWidths(nums []int) (ans int) {
	const mod int = 1e9 + 7
	sort.Ints(nums)
	p, n := 1, len(nums)
	for i, v := range nums {
		ans = (ans + (v-nums[n-i-1])*p + mod) % mod
		p = (p << 1) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

892. 三维形体的表面积

简单1 种解法

标签：几何、数组、数学、矩阵

题目、示例与约束

给你一个 n * n 的网格 grid ，上面放置着一些 1 x 1 x 1 的正方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。

放置好正方体后，任何直接相邻的正方体都会互相粘在一起，形成一些不规则的三维形体。

请你返回最终这些形体的总表面积。

注意：每个形体的底面也需要计入表面积中。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：34

示例 2：

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

示例 3：

输入：grid = [[2,2,2],[2,1,2],[2,2,2]]
输出：46

提示：

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] <= 50

方法一：遍历，逐个累加 · Go 实现

思考

堆叠立方体后求外表面。 $n \leq 50$ ，对每个格子独立加 $2 + 4 v$ ，再减去与左、上邻居贴合的面积。

贴合面数为 $2 \cdot min (v, neighbor)$ 。空格子不加表面积。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (1)$ 。

go

func surfaceArea(grid [][]int) int {
	ans := 0
	for i, row := range grid {
		for j, v := range row {
			if v > 0 {
				ans += 2 + v*4
				if i > 0 {
					ans -= min(v, grid[i-1][j]) * 2
				}
				if j > 0 {
					ans -= min(v, grid[i][j-1]) * 2
				}
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

899. 有序队列

困难1 种解法

标签：数学、字符串、排序、最小表示法

题目、示例与约束

给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。

返回 在应用上述步骤的任意数量的移动后，字典序最小的字符串 。

示例 1：

输入：s = "cba", k = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。

示例 2：

输入：s = "baaca", k = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。

提示：

1 <= k <= s.length <= 1000
s 只由小写字母组成。

方法一：分情况判断 · Go 实现

思考

每次把前 $k$ 个字符之一移到末尾，求能得到的最小串。 $k = 1$ 时只能旋转，枚举所有旋转取最小即可。

$k \geq 2$ 时任意相邻交换都可通过移动实现，因而可以任意重排，答案即排序后的串。

若 $k = 1$ ，我们每次只能将字符串首字符移动到字符串末尾，总共有 $| s |$ 种不同的状态，我们返回其中字典序最小的字符串即可。

若 $k > 1$ ，对于形如 $a b c [x y] d e f$ 的字符串，可以依次将 $a$ , $b$ , $c$ 移动到最后，得到 $[x y] d e f a b c$ ，然后将 $y$ , $x$ 移动到最后，得到 $d e f a b c [y x]$ ，最后将 $d$ , $e$ , $f$ 移动到最后，得到 $a b c [y x] d e f$ ，这样就实现了对 $y$ , $x$ 的交换。

因此，只要 $k > 1$ ，我们就能够交换字符串中的任何两个相邻字符，最终得到一个升序排列的字符串。

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

go

func orderlyQueue(s string, k int) string {
	if k == 1 {
		ans := s
		for i := 0; i < len(s)-1; i++ {
			s = s[1:] + s[:1]
			if s < ans {
				ans = s
			}
		}
		return ans
	}
	t := []byte(s)
	sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
	return string(t)
}

力扣原题 · Doocs 题解来源

906. 超级回文数

困难1 种解法

标签：数学、字符串、枚举

题目、示例与约束

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为 超级回文数 。

现在，给你两个以字符串形式表示的正整数 left 和 right ，统计并返回区间 [left, right] 中的 超级回文数 的数目。

示例 1：

输入：left = "4", right = "1000"
输出：4
解释：4、9、121 和 484 都是超级回文数。
注意 676 不是超级回文数：26 * 26 = 676 ，但是 26 不是回文数。

示例 2：

输入：left = "1", right = "2"
输出：1

提示：

1 <= left.length, right.length <= 18
left 和 right 仅由数字（0 - 9）组成。
left 和 right 不含前导零。
left 和 right 表示的整数在区间 [1, 10¹⁸ - 1] 内。
left 小于等于 right 。

方法一：预处理 + 枚举 · Go 实现

思考

超级回文数 $x = p^{2}$ 落在 $[L, R] \subseteq [1, 10^{18})$ 。若枚举区间内每个平方再判回文，范围过大。 $p$ 本身必须是回文且 $p < 10^{9}$ ，其前半部分至多 $10^{5}$ 量级。

预处理所有由前半拼接（含或不含中间位）得到的回文 $p$ ，再检验 $p^{2}$ 是否落在 $[L, R]$ 且为回文。

根据题目描述，我们假设超级回文数 $x = p^{2} \in [1, 10^{18})$ ，其中 $p$ 是回文数，那么 $p \in [1, 10^{9})$ 。我们可以枚举回文数 $p$ 的前半部分，然后将其翻转后拼接，得到所有的回文数，记录在数组 $p s$ 中。

接下来，我们遍历数组 $p s$ ，对于每个 $p$ ，我们计算 $p^{2}$ ，判断是否在区间 $[L, R]$ 中，同时判断 $p^{2}$ 是否是回文数，若是，答案加一。

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

时间复杂度 $O (M^{\frac{1}{4}} \times \log M)$ ，空间复杂度 $O (M^{\frac{1}{4}})$ 。其中 $M$ 是 $L$ 和 $R$ 的上界，本题中 $M \leq 10^{18}$ 。

相似题目：

2967. 使数组成为等数数组的最小代价

go

var ps [2 * 100000]int64

func init() {
	for i := 1; i <= 100000; i++ {
		s := strconv.Itoa(i)
		t1 := reverseString(s)
		t2 := reverseString(s[:len(s)-1])
		ps[2*i-2], _ = strconv.ParseInt(s+t1, 10, 64)
		ps[2*i-1], _ = strconv.ParseInt(s+t2, 10, 64)
	}
}

func reverseString(s string) string {
	cs := []rune(s)
	for i, j := 0, len(cs)-1; i < j; i, j = i+1, j-1 {
		cs[i], cs[j] = cs[j], cs[i]
	}
	return string(cs)
}

func superpalindromesInRange(left string, right string) (ans int) {
	l, _ := strconv.ParseInt(left, 10, 64)
	r, _ := strconv.ParseInt(right, 10, 64)
	isPalindrome := func(x int64) bool {
		var y int64
		for t := x; t > 0; t /= 10 {
			y = y*10 + int64(t%10)
		}
		return x == y
	}
	for _, p := range ps {
		x := p * p
		if x >= l && x <= r && isPalindrome(x) {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

908. 最小差值 I

简单1 种解法

标签：数组、数学

题目、示例与约束

给你一个整数数组 nums，和一个整数 k 。

在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多只能应用一次此操作。

nums 的分数是 nums 中最大和最小元素的差值。

在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低分数 。

示例 1：

输入：nums = [1], k = 0
输出：0
解释：分数是 max(nums) - min(nums) = 1 - 1 = 0。

示例 2：

输入：nums = [0,10], k = 2
输出：6
解释：将 nums 改为 [2,8]。分数是 max(nums) - min(nums) = 8 - 2 = 6。

示例 3：

输入：nums = [1,3,6], k = 3
输出：0
解释：将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。

提示：

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁴
0 <= k <= 10⁴

方法一：数学 · Go 实现

思考

每个数可加减不超过 $k$ 的整数，最终极差由变换后的最大、最小决定。全体加上同一偏移不改变极差；最优是把最大值尽量减小、最小值尽量增大，即 $max (0, max (n u m s) - min (n u m s) - 2 k)$ 。

根据题目描述，我们可以将数组中的最大值减去 $k$ ，最小值加上 $k$ ，这样可以使得数组中的最大值和最小值之差变小。

因此，最终的答案就是 $max (nums) - min (nums) - 2 \times k$ 和 $0$ 之间的较大值。

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

go

func smallestRangeI(nums []int, k int) int {
	mi, mx := slices.Min(nums), slices.Max(nums)
	return max(0, mx-mi-k*2)
}

力扣原题 · Doocs 题解来源

914. 卡牌分组

简单1 种解法

标签：数组、哈希表、数学、计数、最大公约数、数论、欧几里得算法

题目、示例与约束

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

每组都有 X 张牌。
组内所有的牌上都写着相同的整数。

仅当你可选的 X >= 2 时返回 true。

示例 1：

输入：deck = [1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

示例 2：

输入：deck = [1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

提示：

1 <= deck.length <= 10⁴
0 <= deck[i] < 10⁴

方法一：最大公约数 · Go 实现

思考

要把牌分成若干组，每组张数相同且组内牌面相同，组大小 $X \geq 2$ 。 $X$ 必须整除每一种牌的张数，故 $X$ 是所有频次的公约数。求这些频次的 $gcd$ ，判断是否不小于 $2$ 。

我们先用数组或哈希表 cnt 统计每个数字出现的次数，只有当 $X$ 是所有数字出现次数的约数时，即 $X$ 是所有 cnt[i] 的最大公约数的约数时，才能满足题意。

因此，我们求出所有数字出现次数的最大公约数 $g$ ，然后判断其是否大于等于 $2$ 即可。

时间复杂度 $O (n \times \log M)$ ，空间复杂度 $O (n + \log M)$ 。其中 $n$ 和 $M$ 分别是数组 deck 的长度和数组 deck 中的最大值。

go

func hasGroupsSizeX(deck []int) bool {
	cnt := map[int]int{}
	for _, x := range deck {
		cnt[x]++
	}
	g := cnt[deck[0]]
	for _, x := range cnt {
		g = gcd(g, x)
	}
	return g >= 2
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

力扣原题 · Doocs 题解来源

927. 三等分

困难1 种解法

标签：数组、数学

题目、示例与约束

给定一个由 0 和 1 组成的数组 arr ，将数组分成 3 个非空的部分 ，使得所有这些部分表示相同的二进制值。

如果可以做到，请返回任何 [i, j]，其中 i+1 < j，这样一来：

arr[0], arr[1], ..., arr[i] 为第一部分；
arr[i + 1], arr[i + 2], ..., arr[j - 1] 为第二部分；
arr[j], arr[j + 1], ..., arr[arr.length - 1] 为第三部分。
这三个部分所表示的二进制值相等。

如果无法做到，就返回 [-1, -1]。

注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，[1,1,0] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的，所以 [0,1,1] 和 [1,1] 表示相同的值。

示例 1：

输入：arr = [1,0,1,0,1]
输出：[0,3]

示例 2：

输入：arr = [1,1,0,1,1]
输出：[-1,-1]

示例 3:

输入：arr = [1,1,0,0,1]
输出：[0,2]

提示：

3 <= arr.length <= 3 * 10⁴
arr[i] 是 0 或 1

方法一：计数 + 三指针 · Go 实现

思考

把二进制数组切成三段，使其表示的数值相等。前导零不影响数值，真正对齐的是 $1$ 的个数与其后的比特。若 $1$ 的总数不能被 $3$ 整除则无解；全零则任意切。

每份应含 $c n t / 3$ 个 $1$ ，定位三段第一个 $1$ 后同步后移，直到第三段走到末尾。比特全程相等则切分合法。

我们记数组的长度为 $n$ ，数组中 $1$ 的数量为 $c n t$ 。

显然 $c n t$ 必须是 $3$ 的倍数，否则无法将数组三等分，可以提前返回 $[- 1, - 1]$ 。如果 $c n t$ 为 $0$ ，那么意味着数组中所有元素都为 $0$ ，直接返回 $[0, n - 1]$ 即可。

我们将 $c n t$ 除以 $3$ ，得到每一份中 $1$ 的数量，然后找到每一份的第一个 $1$ 在数组 arr 中的位置（参考以下代码中的 $f i n d (x)$ 函数），分别记为 $i$ , $j$ , $k$ 。

bash

0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0
  ^         ^             ^
  i         j             k

接着我们从 $i$ , $j$ , $k$ 开始往后同时遍历每一部分，判断三部分对应的值是否相等，是则继续遍历，直至 $k$ 到达 $a r r$ 末尾。

bash

0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0
          ^         ^             ^
          i         j             k

遍历结束时，若 $k = n$ ，说明满足三等分，返回此时的 $[i - 1, j]$ 作为答案，否则返回 $[- 1, - 1]$ 。

时间复杂度 $O (n)$ ，其中 $n$ 表示 arr 的长度。空间复杂度 $O (1)$ 。

相似题目：

1573. 分割字符串的方案数

go

func threeEqualParts(arr []int) []int {
	find := func(x int) int {
		s := 0
		for i, v := range arr {
			s += v
			if s == x {
				return i
			}
		}
		return 0
	}
	n := len(arr)
	cnt := 0
	for _, v := range arr {
		cnt += v
	}
	if cnt%3 != 0 {
		return []int{-1, -1}
	}
	if cnt == 0 {
		return []int{0, n - 1}
	}
	cnt /= 3
	i, j, k := find(1), find(cnt+1), find(cnt*2+1)
	for ; k < n && arr[i] == arr[j] && arr[j] == arr[k]; i, j, k = i+1, j+1, k+1 {
	}
	if k == n {
		return []int{i - 1, j}
	}
	return []int{-1, -1}
}

力扣原题 · Doocs 题解来源

932. 漂亮数组

中等1 种解法

标签：数组、数学、分治

题目、示例与约束

如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个 漂亮数组 ：

nums 是由范围 [1, n] 的整数组成的一个排列。
对于每个 0 <= i < j < n ，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j] 。

给你整数 n ，返回长度为 n 的任一 漂亮数组 。本题保证对于给定的 n 至少存在一个有效答案。

示例 1 ：

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

示例 2 ：

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

提示：

1 <= n <= 1000

方法一：分治 · Go 实现

思考

漂亮数组禁止 $2 A_{k} = A_{i} + A_{j}$ 。左侧为偶数，故只要 $A_{i}$ 与 $A_{j}$ 奇偶不同，中间任意 $k$ 都安全。把较小规模的漂亮数组仿射成全奇、全偶两段再拼接，仿射保持漂亮性，分治即可构造 $1. . n$ 。

根据题意，漂亮数组 $A$ 需要满足对于任意 $i < k < j$ , $A_{k} * 2 \neq A_{i} + A_{j}$ 。

我们可以发现，不等式左侧一定是偶数，那么我们只要保证不等式右侧 $A_{i}$ 和 $A_{j}$ 分别是一奇一偶，那么不等式就恒成立。

利用分治，我们将 $n$ 缩小规模为原来的一半，递归调用，可以得到两个漂亮数组 $l e f t$ , $r i g h t$ 。我们将 $l e f t$ 中每个元素 $x_{i}$ 变为 $x_{i} * 2 - 1$ 可以得到一个奇数数组；将 $r i g h t$ 中每个元素 $x_{i}$ 变为 $x_{i} * 2$ ，可以得到一个偶数数组。这两个数组仍然是漂亮数组。

基于一个性质，将漂亮数组中的每个元素 $x_{i}$ 变换为 $k x_{i} + b$ ，得到的数组仍然是漂亮数组。

将这两个漂亮数组合并在一起，由于满足一奇一偶，那么合并后的数组也是漂亮数组，从而得到了答案。

时间复杂度 $O (n l o g n)$ 。

go

func beautifulArray(n int) []int {
	if n == 1 {
		return []int{1}
	}
	left := beautifulArray((n + 1) >> 1)
	right := beautifulArray(n >> 1)
	var ans []int
	for _, x := range left {
		ans = append(ans, x*2-1)
	}
	for _, x := range right {
		ans = append(ans, x*2)
	}
	return ans
}

力扣原题 · Doocs 题解来源

939. 最小面积矩形

中等1 种解法

标签：几何、数组、哈希表、数学、排序

题目、示例与约束

给你一个 X-Y 平面上的点数组 points，其中 points[i] = [x_i, y_i]。

返回由这些点形成的矩形的最小面积，矩形的边与 X 轴和 Y 轴平行。如果不存在这样的矩形，则返回 0。

示例 1：

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

示例 2：

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

提示：

1 <= points.length <= 500
points[i].length == 2
0 <= x_i, y_i <= 4 * 10⁴
所有给定的点都是唯一的。

方法一：哈希表 + 排序 + 枚举 · Go 实现

思考

轴对齐矩形由两对相同纵坐标撑开。 $n \leq 500$ ，枚举四个点不可行，枚举同一竖线上的点对则可以。按 $x$ 分组并排序，从左向右扫；对当前竖线上的每一对 $(y_{1}, y_{2})$ ，若该对曾在更左的竖线出现，即可用两次出现的 $x$ 差计算面积。哈希表记下每对纵坐标最近一次的 $x$ 。

对于每个点，我们将其横坐标作为键，纵坐标作为值存入哈希表 $d$ 中。对于哈希表中的每个键，我们将其对应的纵坐标按照从小到大的顺序排序。

然后我们从小到大枚举横坐标，对于每个横坐标，我们枚举其对应的纵坐标中的所有点对 $(y_{1}, y_{2})$ ，其中 $y_{1} < y_{2}$ 。如果我们之前已经遇到过点对 $(y_{1}, y_{2})$ ，那么就可以用当前的横坐标和之前的横坐标计算出一个矩形的面积。我们用哈希表 $p o s$ 记录每个点对 $(y_{1}, y_{2})$ 第一次出现的横坐标，这样我们就可以在常数时间内找到这个横坐标。

最后，我们返回所有矩形的面积中的最小值。

时间复杂度 $O (n^{2} \times \log n)$ ，空间复杂度 $O (n^{2})$ 。其中 $n$ 是点的数量。

go

func minAreaRect(points [][]int) int {
	d := map[int][]int{}
	xs := []int{}
	for _, p := range points {
		x, y := p[0], p[1]
		d[x] = append(d[x], y)
	}
	for x := range d {
		xs = append(xs, x)
	}
	sort.Ints(xs)
	type pair struct{ x, y int }
	pos := map[pair]int{}
	ans := 1 << 30
	for _, x := range xs {
		ys := d[x]
		sort.Ints(ys)
		for i, y1 := range ys {
			for _, y2 := range ys[i+1:] {
				p := pair{y1, y2}
				if x1, ok := pos[p]; ok {
					ans = min(ans, (x-x1)*(y2-y1))
				}
				pos[p] = x
			}
		}
	}
	if ans == 1<<30 {
		return 0
	}
	return ans
}

力扣原题 · Doocs 题解来源

963. 最小面积矩形 II

中等1 种解法

标签：几何、数组、哈希表、数学

题目、示例与约束

给你一个 X-Y 平面上的点数组 points，其中 points[i] = [x_i, y_i]。

返回由这些点形成的任意矩形的最小面积，矩形的边 不一定 平行于 X 轴和 Y 轴。如果不存在这样的矩形，则返回 0。

答案只需在10^-5 的误差范围内即可被视作正确答案。

示例 1：

输入： points = [[1,2],[2,1],[1,0],[0,1]]
输出： 2.00000
解释： 最小面积矩形由 [1,2]、[2,1]、[1,0]、[0,1] 组成，其面积为 2。

示例 2：

输入： points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
输出： 1.00000
解释： 最小面积矩形由 [1,0]、[1,1]、[2,1]、[2,0] 组成，其面积为 1。

示例 3：

输入： points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
输出： 0
解释： 无法由这些点组成任何矩形。

提示：

1 <= points.length <= 50
points[i].length == 2
0 <= x_i, y_i <= 4 * 10⁴
所有给定的点都是唯一的。

方法一：哈希表 + 枚举 · Go 实现

思考

求任意方向矩形的最小面积， $n \leq 50$ ，枚举三个顶点即可。以 $p_{1}$ 为直角顶点时，第四个顶点由两条边的向量和确定。

打包键 $x \times 40001 + y$ 在坐标越出 $[0, 4 \times 10^{4}]$ 后会与范围内的点重合，两条边的平方和也会超过 $2^{31} - 1$ 。

坐标落在这个正方形内时键是唯一的，平方和放进 64 位整数才不会回绕。

因此第四点要同时落在范围内且键已存在，再用 64 位整数累加两条边的平方，最后开方得到面积。

我们用哈希表存放所有的点，然后枚举三个点 $p_{1} = (x_{1}, y_{1})$ , $p_{2} = (x_{2}, y_{2})$ , $p_{3} = (x_{3}, y_{3})$ 。若 $\vec{p_{1} p_{2}}$ 与 $\vec{p_{1} p_{3}}$ 垂直，第四个顶点为 $(x_{4}, y_{4}) = (x_{2} - x_{1} + x_{3}, y_{2} - y_{1} + y_{3})$ 。坐标落在 $[0, 4 \times 10^{4}]$ 内，打包键 $x \times 40001 + y$ 只在这个正方形里唯一，因此该点要同时落在范围内且键已存在。两条边的平方和可能超过 $2^{31} - 1$ ，用 64 位整数累加后再开方，得到面积并更新答案。

最后，如果找到满足条件的矩形，返回其中面积的最小值。否则，返回 $0$ 。

时间复杂度 $O (n^{3})$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $points$ 的长度。

go

func minAreaFreeRect(points [][]int) float64 {
	n := len(points)
	f := func(x, y int) int {
		return x*40001 + y
	}
	s := map[int]bool{}
	for _, p := range points {
		s[f(p[0], p[1])] = true
	}
	ans := 1e20
	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]
		for j := 0; j < n; j++ {
			if j != i {
				x2, y2 := points[j][0], points[j][1]
				for k := j + 1; k < n; k++ {
					if k != i {
						x3, y3 := points[k][0], points[k][1]
						x4, y4 := x2-x1+x3, y2-y1+y3
						if x4 >= 0 && x4 <= 40000 && y4 >= 0 && y4 <= 40000 && s[f(x4, y4)] {
							if (x2-x1)*(x3-x1)+(y2-y1)*(y3-y1) == 0 {
								ww := (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)
								hh := (x3-x1)*(x3-x1) + (y3-y1)*(y3-y1)
								ans = math.Min(ans, math.Sqrt(float64(ww*hh)))
							}
						}
					}
				}
			}
		}
	}
	if ans == 1e20 {
		return 0
	}
	return ans
}

力扣原题 · Doocs 题解来源

970. 强整数

中等1 种解法

标签：哈希表、数学、枚举

题目、示例与约束

给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。

如果某一整数可以表示为 xⁱ + y^j ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。

你可以按 任何顺序 返回答案。在你的回答中，每个值最多出现一次。

示例 1：

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释： 
2 = 2⁰ + 3⁰
3 = 2¹ + 3⁰
4 = 2⁰ + 3¹
5 = 2¹ + 3¹
7 = 2² + 3¹
9 = 2³ + 3⁰
10 = 2⁰ + 3²

示例 2：

输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]

提示：

1 <= x, y <= 100
0 <= bound <= 10⁶

方法一：哈希表 + 枚举 · Go 实现

思考

强整数为 $x^{i} + y^{j} \leq b o u n d$ 。 $b o u n d \leq 10^{6}$ ，底数 $\geq 2$ 时指数不超过约 $20$ 。双重循环枚举幂次，和放入集合去重； $x = 1$ 或 $y = 1$ 时对应幂不再增长，循环只跑一轮。

根据题目描述，一个强整数可以表示成 $x^{i} + y^{j}$ ，其中 $i \geq 0$ , $j \geq 0$ 。

题目需要我们找出所有不超过 $b o u n d$ 的强整数，我们注意到 $b o u n d$ 的取值范围不超过 $10^{6}$ ，而 $2^{20} = 1048576 > 10^{6}$ 。因此，如果 $x \geq 2$ ，那么 $i$ 最大不超过 $20$ ，才有可能使得 $x^{i} + y^{j} \leq b o u n d$ 成立。同理，如果 $y \geq 2$ ，那么 $j$ 最大不超过 $20$ 。

因此我们可以使用双重循环，枚举所有可能的 $x^{i}$ 和 $y^{j}$ ，分别记为 $a$ 和 $b$ ，并保证 $a + b \leq b o u n d$ ，此时 $a + b$ 即为一个强整数。我们使用哈希表存储所有满足条件的强整数，最后将哈希表中的所有元素转换成答案列表返回即可。

注意，如果 $x = 1$ 或者 $y = 1$ ，那么 $a$ 或者 $b$ 的值恒等于 $1$ ，对应的循环只需要执行一次即可退出。

时间复杂度 $O (\log^{2} b o u n d)$ ，空间复杂度 $O (\log^{2} b o u n d)$ 。

go

func powerfulIntegers(x int, y int, bound int) (ans []int) {
	s := map[int]struct{}{}
	for a := 1; a <= bound; a *= x {
		for b := 1; a+b <= bound; b *= y {
			s[a+b] = struct{}{}
			if y == 1 {
				break
			}
		}
		if x == 1 {
			break
		}
	}
	for x := range s {
		ans = append(ans, x)
	}
	return ans
}

力扣原题 · Doocs 题解来源

972. 相等的有理数

困难1 种解法

标签：数学、字符串

题目、示例与约束

给定两个字符串 s 和 t ，每个字符串代表一个非负有理数，只有当它们表示相同的数字时才返回 true 。字符串中可以使用括号来表示有理数的重复部分。

有理数 最多可以用三个部分来表示：整数部分 <IntegerPart>、小数非重复部分 <NonRepeatingPart> 和小数重复部分 <(><RepeatingPart><)>。数字可以用以下三种方法之一来表示：

<IntegerPart>
- 例： 0 ,12 和 123
<IntegerPart><.><NonRepeatingPart>
- 例： 0.5 , 1. , 2.12 和 123.0001
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>
- 例： 0.1(6) ， 1.(9)， 123.00(1212)

十进制展开的重复部分通常在一对圆括号内表示。例如：

1 / 6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66)

示例 1：

输入：s = "0.(52)", t = "0.5(25)"
输出：true
解释：因为 "0.(52)" 代表 0.52525252...，而 "0.5(25)" 代表 0.52525252525.....，则这两个字符串表示相同的数字。

示例 2：

输入：s = "0.1666(6)", t = "0.166(66)"
输出：true

示例 3：

输入：s = "0.9(9)", t = "1."
输出：true
解释："0.9(9)" 代表 0.999999999... 永远重复，等于 1 。[有关说明，请参阅此链接]
"1." 表示数字 1，其格式正确：(IntegerPart) = "1" 且 (NonRepeatingPart) = "" 。

提示：

每个部分仅由数字组成。
整数部分 <IntegerPart> 不会以零开头。（零本身除外）
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

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

Doocs 参考题解 · CC BY-SA 4.0

根据题意整理：本地 Doocs 实现围栏为空，采用思考中建议的精确分数。设整数部分为 I，非循环小数部分数字为 A、长度为 a，循环部分为 B、长度为 b。有限小数为 (I·10ᵃ+A)/10ᵃ；有循环节时分子为 (I·10ᵃ+A)(10ᵇ−1)+B，分母为 10ᵃ(10ᵇ−1)。分别用最大公约数约分后比较分子与分母，因此循环 9 进位、不同循环节写法都能精确处理。

变量与复杂度：L 为字符串长度，D 为分母；解析 O(L)，欧几里得约分 O(log D)，辅助空间 O(L)（切分子串描述符及字符串引用）。各部分最多 4 位，分子小于 10¹²、分母小于 10⁸，int64 足够；不做可能溢出的分数交叉相乘。

平台接口：isRationalEqual(s string, t string) bool，无平台依赖。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

go

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/0900-0999/0972.Equal%20Rational%20Numbers/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

import (
	"strconv"
	"strings"
)

func isRationalEqual(s string, t string) bool {
	parse := func(s string) (int64, int64) {
		parts := strings.SplitN(s, ".", 2)
		integer, _ := strconv.ParseInt(parts[0], 10, 64)
		tail := ""
		if len(parts) == 2 {
			tail = parts[1]
		}
		repeat := ""
		if i := strings.IndexByte(tail, '('); i >= 0 {
			repeat = tail[i+1 : len(tail)-1]
			tail = tail[:i]
		}
		digits := func(x string) int64 { v, _ := strconv.ParseInt(x, 10, 64); return v }
		power := func(n int) int64 {
			p := int64(1)
			for ; n > 0; n-- {
				p *= 10
			}
			return p
		}
		denominator := power(len(tail))
		numerator := integer*denominator + digits(tail)
		if repeat != "" {
			factor := power(len(repeat)) - 1
			numerator = numerator*factor + digits(repeat)
			denominator *= factor
		}
		a, b := numerator, denominator
		for b != 0 {
			a, b = b, a%b
		}
		return numerator / a, denominator / a
	}
	a, b := parse(s)
	c, d := parse(t)
	return a == c && b == d
}

力扣原题 · Doocs 题解来源

989. 数组形式的整数加法

简单1 种解法

标签：数组、数学

题目、示例与约束

整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。

例如，对于 num = 1321 ，数组形式是 [1,3,2,1] 。

给定 num ，整数的 数组形式 ，和整数 k ，返回整数 num + k 的 数组形式 。

示例 1：

输入：num = [1,2,0,0], k = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例 2：

输入：num = [2,7,4], k = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：

输入：num = [2,1,5], k = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021

提示：

1 <= num.length <= 10⁴
0 <= num[i] <= 9
num 不包含任何前导零，除了零本身
1 <= k <= 10⁴

方法一：模拟 · Go 实现

思考

数组表示的整数加上 $k$ ，需处理进位。从最低位起把 $k$ 加到当前位，用除法留下进位继续，直到数组与 $k$ 都耗尽。结果先低后高，最后反转。

我们可以从数组的最后一位开始，将数组的每一位与 $k$ 相加，然后将 $k$ 除以 $10$ ，并将余数作为当前位的值，将商作为进位。一直循环，直到数组遍历完并且 $k = 0$ 。最后将答案数组反转即可。

时间复杂度 $O (n)$ ，其中 $n$ 表示 $num$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

go

func addToArrayForm(num []int, k int) (ans []int) {
	for i := len(num) - 1; i >= 0 || k > 0; i-- {
		if i >= 0 {
			k += num[i]
		}
		ans = append(ans, k%10)
		k /= 10
	}
	slices.Reverse(ans)
	return
}

力扣原题 · Doocs 题解来源

1015. 可被 K 整除的最小整数

中等1 种解法

标签：哈希表、数学、抽屉原理

题目、示例与约束

给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最小正整数 n 的长度。

返回 n 的长度。如果不存在这样的 n ，就返回-1。

注意： n 可能不符合 64 位带符号整数。

示例 1：

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。

示例 2：

输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。

示例 3：

输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。

提示：

1 <= k <= 10⁵

方法一：数学 · Go 实现

思考

构造 $1, 11, 111, \dots$ 直到整除 $k$ ，数值本身会超出整型范围，且 $k \leq 10^{5}$ 时不能无界地加位数。可整除性只依赖对 $k$ 的余数。

$(10 n + 1) mod k$ 由 $n mod k$ 决定。余数只有 $k$ 种，若连续 $k$ 次都未出现 $0$ ，则以后只会在已见余数中循环，不存在这样的数。

从 $1 mod k$ 出发迭代至多 $k$ 步，第一次余数为 $0$ 时的步数即位数；否则返回 $- 1$ 。

我们注意到，正整数 $n$ 初始值为 $1$ ，每次乘以 $10$ 后再加 $1$ ，即 $n = n \times 10 + 1$ ，而 $(n \times 10 + 1) mod k = ((n mod k) \times 10 + 1) mod k$ ，因此我们可以通过计算 $n mod k$ 来判断 $n$ 是否能被 $k$ 整除。

我们从 $n = 1$ 开始，每次计算 $n mod k$ ，直到 $n mod k = 0$ ，此时 $n$ 就是我们要求的最小正整数，其长度即为 $n$ 的位数。否则，我们更新 $n = (n \times 10 + 1) mod k$ 。如果循环 $k$ 次后，仍然没有找到 $n mod k = 0$ ，则说明不存在这样的 $n$ ，返回 $- 1$ 。

时间复杂度 $O (k)$ ，空间复杂度 $O (1)$ 。其中 $k$ 为给定的正整数。

go

func smallestRepunitDivByK(k int) int {
	n := 1 % k
	for i := 1; i <= k; i++ {
		if n == 0 {
			return i
		}
		n = (n*10 + 1) % k
	}
	return -1
}

力扣原题 · Doocs 题解来源

1017. 负二进制转换

中等1 种解法

标签：数学

题目、示例与约束

给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。

注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。

示例 1：

输入：n = 2
输出："110"
解释：(-2)² + (-2)¹ = 2

示例 2：

输入：n = 3
输出："111"
解释：(-2)² + (-2)¹ + (-2)⁰ = 3

示例 3：

输入：n = 4
输出："100"
解释：(-2)² = 4

提示：

0 <= n <= 10⁹

方法一：模拟 · Go 实现

思考

普通正基转换对 $- 2$ 会得到负余数，不能直接套用「除基取余」。 $n \leq 10^{9}$ ，位数约为 $O (\log n)$ ，按位模拟足够。

当前最低位为 $n mod 2$ 。若该位为 $1$ ，减去这一位的权值 $k$ （在奇数位为 $- 1$ 的幂）才能使剩余部分仍能被 $2$ 整除，然后再除以 $2$ 并翻转 $k$ 的符号。

从低到高收集 $0 / 1$ ，最后反转；若 $n$ 一开始就是 $0$ ，则答案为 $0$ 。

我们可以判断 $n$ 从低位到高位的每一位，如果该位为 $1$ ，那么答案的该位为 $1$ ，否则为 $0$ 。如果该位为 $1$ ，那么我们需要将 $n$ 减去 $k$ 。接下来我们更新 $n = ⌊ n / 2 ⌋$ , $k = - k$ 。继续判断下一位。

最后，我们将答案反转后返回即可。

时间复杂度 $O (\log n)$ ，其中 $n$ 为给定的整数。忽略答案的空间消耗，空间复杂度 $O (1)$ 。

相似题目：

1073. 负二进制数相加

go

func baseNeg2(n int) string {
	if n == 0 {
		return "0"
	}
	ans := []byte{}
	k := 1
	for n != 0 {
		if n%2 != 0 {
			ans = append(ans, '1')
			n -= k
		} else {
			ans = append(ans, '0')
		}
		k *= -1
		n /= 2
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1030. 距离顺序排列矩阵单元格

简单1 种解法

标签：几何、数组、数学、矩阵、排序

题目、示例与约束

给定四个整数 rows , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。

返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的距离从最小到最大的顺序排。你可以按任何满足此条件的顺序返回答案。

单元格(r1, c1) 和 (r2, c2) 之间的距离为|r1 - r2| + |c1 - c2|。

示例 1：

输入：rows = 1, cols = 2, rCenter = 0, cCenter = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

输入：rows = 2, cols = 2, rCenter = 0, cCenter = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

输入：rows = 2, cols = 3, rCenter = 1, cCenter = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

1 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols

方法一：BFS · Go 实现

思考

按曼哈顿距离对 $r o w s \times c o l s$ 个格子排序即可， $r, c \leq 100$ 时 $O (r c \log (r c))$ 可过。距离为 $d$ 的格子恰好组成以中心为原点的菱形，按层扩展不必比较距离。

从 $(r C e n t e r, c C e n t e r)$ 做广度优先，每一层的格子距离比上一层恰好多 $1$ ，出队顺序就是题目要求的顺序。

用队列与访问标记避免重复入队，扫完所有格子即得答案。

我们定义一个队列 $q$ ，初始时将坐标点 $(r C e n t e r, c C e n t e r)$ 入队，用一个二维布尔数组 $v i s$ 记录已经访问过的点，初始时 $v i s [r C e n t e r] [c C e n t e r]$ 为 $t r u e$ 。

接下来，我们不断地从队列中取出一个点，将其加入答案数组，然后将其上下左右四个相邻点加入队列，注意要判断这些点是否已经访问过，如果没有访问过，就将其标记为已访问，并将其加入队列。一直重复这个过程，直到队列为空，此时答案数组中的点就是按照距离从小到大的顺序排列的。

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

go

func allCellsDistOrder(rows int, cols int, rCenter int, cCenter int) (ans [][]int) {
	q := [][]int{{rCenter, cCenter}}
	vis := make([][]bool, rows)
	for i := range vis {
		vis[i] = make([]bool, cols)
	}
	vis[rCenter][cCenter] = true
	dirs := [5]int{-1, 0, 1, 0, -1}
	for len(q) > 0 {
		for n := len(q); n > 0; n-- {
			p := q[0]
			q = q[1:]
			ans = append(ans, p)
			for k := 0; k < 4; k++ {
				x, y := p[0]+dirs[k], p[1]+dirs[k+1]
				if x >= 0 && x < rows && y >= 0 && y < cols && !vis[x][y] {
					vis[x][y] = true
					q = append(q, []int{x, y})
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1033. 移动石子直到连续

中等1 种解法

标签：脑筋急转弯、数学

题目、示例与约束

三枚石子放置在数轴上，位置分别为 a，b，c。

每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]

示例 1：

输入：a = 1, b = 2, c = 5
输出：[1, 2]
解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。

示例 2：

输入：a = 4, b = 3, c = 2
输出：[0, 0]
解释：我们无法进行任何移动。

提示：

1 <= a <= 100
1 <= b <= 100
1 <= c <= 100
a != b, b != c, c != a

方法一：分类讨论 · Go 实现

思考

三枚石子位置互异，状态空间虽可搜索，但每一步的最优选择只取决于排序后的间距，不必模拟过程。

记 $x < y < z$ 。三点已相邻则无需移动。否则若 $y$ 与某一端间隔不超过 $2$ ，一次即可填入空隙；其余情况两端各靠一次，最少为 $2$ 。最多步数是两端逐步向中间空位移动，共 $z - x - 2$ 次。

排序后按上述分类直接给出 $[mi, mx]$ 。

我们先将 $a, b, c$ 排序，记为 $x, y, z$ ，即 $x < y < z$ 。

接下来分情况讨论：

如果 $z - x \leq 2$ ，说明 $3$ 个数已经相邻，不用移动，结果为 $[0, 0]$ ；
否则，如果 $y - x < 3$ ，或者 $z - y < 3$ ，说明有两个数只间隔一个位置，我们只需要把另一个数移动到这两个数的中间，最小移动次数为 $1$ ；其他情况，最小移动次数为 $2$ ；
最大移动次数就是两边的数字逐个往中间靠，最多移动 $z - x - 2$ 次。

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

go

func numMovesStones(a int, b int, c int) []int {
	x := min(a, min(b, c))
	z := max(a, max(b, c))
	y := a + b + c - x - z
	mi, mx := 0, 0
	if z-x > 2 {
		mi = 2
		if y-x < 3 || z-y < 3 {
			mi = 1
		}
		mx = z - x - 2
	}
	return []int{mi, mx}
}

力扣原题 · Doocs 题解来源

1037. 有效的回旋镖

简单1 种解法

标签：几何、数组、数学

题目、示例与约束

给定一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点，如果这些点构成一个 回旋镖 则返回 true 。

回旋镖 定义为一组三个点，这些点 各不相同 且 不在一条直线上 。

示例 1：

输入：points = [[1,1],[2,3],[3,2]]
输出：true

示例 2：

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

提示：

points.length == 3
points[i].length == 2
0 <= x_i, y_i <= 100

方法一：斜率比较 · Go 实现

思考

三点构成回旋镖当且仅当互不重合且不共线。斜率相减会遇到竖直边与浮点误差。

两段斜率不等写成叉积 $(y_{2} - y_{1}) (x_{3} - x_{2}) \neq (y_{3} - y_{2}) (x_{2} - x_{1})$ ，竖直边与重合点都包含在该式中。

对三个坐标做一次乘法比较即可。

设三点分别为 $(x_{1}, y_{1})$ , $(x_{2}, y_{2})$ , $(x_{3}, y_{3})$ 。两点之间斜率计算公式为 $\frac{y_{2} - y_{1}}{x_{2} - x_{1}}$ 。

要使得三点不共线，需要满足 $\frac{y_{2} - y_{1}}{x_{2} - x_{1}} \neq \frac{y_{3} - y_{2}}{x_{3} - x_{2}}$ ，我们将式子变形得到 $(y_{2} - y_{1}) \cdot (x_{3} - x_{2}) \neq (y_{3} - y_{2}) \cdot (x_{2} - x_{1})$ 。

注意：

当两点之间斜率不存在，即 $x_{1} = x_{2}$ ，上述变式仍然成立；
若斜率除法运算比较存在精度问题，同样可以变换为乘法。

时间复杂度 $O (1)$ 。

go

func isBoomerang(points [][]int) bool {
	x1, y1 := points[0][0], points[0][1]
	x2, y2 := points[1][0], points[1][1]
	x3, y3 := points[2][0], points[2][1]
	return (y2-y1)*(x3-x2) != (y3-y2)*(x2-x1)
}

力扣原题 · Doocs 题解来源

1041. 困于环中的机器人

中等1 种解法

标签：数学、字符串、模拟

题目、示例与约束

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:

北方向 是y轴的正方向。
南方向 是y轴的负方向。
东方向 是x轴的正方向。
西方向 是x轴的负方向。

机器人可以接受下列三条指令之一：

"G"：直走 1 个单位
"L"：左转 90 度
"R"：右转 90 度

机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

示例 1：

输入：instructions = "GGLLGG"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
“L”:逆时针旋转90度。位置:(0,2).方向:西。
“L”:逆时针旋转90度。位置:(0,2)方向:南。
“G”:移动一步。位置:(0,1)方向:南。
“G”:移动一步。位置:(0,0)方向:南。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(0,2)——>(0,1)——>(0,0)。
在此基础上，我们返回true。

示例 2：

输入：instructions = "GG"
输出：false
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
重复这些指示，继续朝北前进，不会进入循环。
在此基础上，返回false。

示例 3：

输入：instructions = "GL"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“L”:逆时针旋转90度。位置:(0,1).方向:西。
“G”:移动一步。位置:(- 1,1)方向:西。
“L”:逆时针旋转90度。位置:(- 1,1)方向:南。
“G”:移动一步。位置:(- 1,0)方向:南。
“L”:逆时针旋转90度。位置:(- 1,0)方向:东方。
“G”:移动一步。位置:(0,0)方向:东方。
“L”:逆时针旋转90度。位置:(0,0)方向:北。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(- 1,1)——>(- 1,0)——>(0,0)。
在此基础上，我们返回true。

提示：

1 <= instructions.length <= 100
instructions[i] 仅包含 'G', 'L', 'R'

方法一：模拟 · Go 实现

思考

指令可无限重复，不能真的走无限步。一轮之后机器人的位移与朝向完全决定以后是否循环：若已回到原点，或朝向不再向北，则反复执行会在平面上转圈。

用 $k \in [0, 3]$ 表示北南西东，数组 $dist$ 记录四个方向走了多少步。左加一、右加三，前进累加当前方向。

一轮结束时南北相等且东西相等，或 $k \neq 0$ ，即判定为有界。

我们可以模拟机器人的行走过程，用一个变量 $k$ 表示机器人的方向，初始值为 $0$ ，表示机器人面向北方。变量 $k$ 的取值范围为 $[0, 3]$ ，分别表示机器人面向北、西、南、东。另外，我们用一个长度为 $4$ 的数组 $d i s t$ 记录机器人在四个方向上行走的距离，初始值为 $[0, 0, 0, 0]$ 。

遍历指令字符串 $instructions$ ，如果当前指令为 'L'，那么机器人转向西方，即 $k = (k + 1) mod 4$ ；如果当前指令为 'R'，那么机器人转向东方，即 $k = (k + 3) mod 4$ ；否则，机器人在当前方向上行走一步，即 $d i s t [k] + +$ 。

如果给定的指令字符串 $instructions$ 执行一遍后，使得机器人最终回到原点，即 $d i s t [0] = d i s t [2]$ 且 $d i s t [1] = d i s t [3]$ ，那么机器人一定会进入循环。因为无论重复多少次指令，机器人都回到了原点，所以机器人一定会进入循环。

如果给定的指令字符串 $instructions$ 执行一遍后，机器人没回到原点，不妨假设此时机器人位于 $(x, y)$ ，且方向为 $k$ 。

若 $k = 0$ ，即机器人面向北方，那么执行第二遍指令后，坐标变化量是 $(x, y)$ ；继续执行第三遍指令后，坐标变化量还是 $(x, y)$ ...累加这些变化量，机器人最终会到 $(n \times x, n \times y)$ ，其中 $n$ 是一个正整数。由于机器人最终没有回到原点，即 $x \neq 0$ 或 $y \neq 0$ ，所以 $n \times x \neq 0$ 或 $n \times y \neq 0$ ，因此机器人不会进入循环；
若 $k = 1$ ，即机器人面向西方，那么机器人执行第二遍指令后，坐标变化量是 $(- y, x)$ ；继续执行第三遍执行后，坐标变化量是 $(- x, - y)$ ；继续执行第四遍指令后，坐标变化量是 $(y, - x)$ 。累加这些坐标变化量，我们可以发现，机器人最终会回到原点 $(0, 0)$ ；
若 $k = 2$ ，即机器人面向南方，那么执行第二遍指令后，坐标变化量是 $(- x, - y)$ ，累加这两次坐标变化量，我们可以发现，机器人最终会回到原点 $(0, 0)$ ；
若 $k = 3$ ，即机器人面向东方，那么执行第二遍指令后，坐标变化量是 $(y, - x)$ ；继续执行第三遍指令后，坐标变化量是 $(- x, - y)$ ；继续执行第四遍指令后，坐标变化量是 $(- y, x)$ 。累加这些坐标变化量，我们可以发现，机器人最终会回到原点 $(0, 0)$ 。

综上所述，如果给定的指令字符串 $instructions$ 执行一遍后，机器人回到了原点，或者机器人的方向与初始方向不同，那么机器人一定会进入循环。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为指令字符串 $instructions$ 的长度。

go

func isRobotBounded(instructions string) bool {
	dist := [4]int{}
	k := 0
	for _, c := range instructions {
		if c == 'L' {
			k = (k + 1) % 4
		} else if c == 'R' {
			k = (k + 3) % 4
		} else {
			dist[k]++
		}
	}
	return (dist[0] == dist[2] && dist[1] == dist[3]) || k != 0
}

力扣原题 · Doocs 题解来源

1056. 易混淆数 🔒

简单1 种解法

标签：数学

题目、示例与约束

给定一个数字 N，当它满足以下条件的时候返回 true：

原数字旋转 180° 以后可以得到新的数字。

如 0, 1, 6, 8, 9 旋转 180° 以后，得到了新的数字 0, 1, 9, 8, 6 。

2, 3, 4, 5, 7 旋转 180° 后，得到的不是数字。

易混淆数 (confusing number) 在旋转180°以后，可以得到和原来不同的数，且新数字的每一位都是有效的。

示例 1：

输入：6
输出：true
解释： 
把 6 旋转 180° 以后得到 9，9 是有效数字且 9!=6 。

示例 2：

输入：89
输出：true
解释: 
把 89 旋转 180° 以后得到 68，68 是有效数字且 89!=68 。

示例 3：

输入：11
输出：false
解释：
把 11 旋转 180° 以后得到 11，11 是有效数字但是值保持不变，所以 11 不是易混淆数字。

示例 4：

输入：25
输出：false
解释：
把 25 旋转 180° 以后得到的不是数字。

提示：

0 <= N <= 10^9
可以忽略掉旋转后得到的前导零，例如，如果我们旋转后得到 0008 那么该数字就是 8 。

方法一 · Go 实现

思考

旋转后可得到合法数字的数位只有 $0, 1, 6, 8, 9$ ，且 $6$ 与 $9$ 互换。从低到高检查并同时构造旋转结果，即可判断是否「易混淆」。

映射表 $d$ 给出每位旋转后的值，非法位立即失败。把映射值从低到高拼成 $y$ ，相当于把原数旋转 $180^{\circ}$ 。

$y \neq n$ 时成立；前导零自然消在整数里。

go

func confusingNumber(n int) bool {
	d := []int{0, 1, -1, -1, -1, -1, 9, -1, 8, 6}
	x, y := n, 0
	for x > 0 {
		v := x % 10
		if d[v] < 0 {
			return false
		}
		y = y*10 + d[v]
		x /= 10
	}
	return y != n
}

力扣原题 · Doocs 题解来源

1071. 字符串的最大公因子

简单1 种解法

标签：数学、字符串、最大公约数、欧几里得算法

题目、示例与约束

对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。

给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

示例 1：

输入：str1 = "ABCABC", str2 = "ABC"

输出："ABC"

示例 2：

输入：str1 = "ABABAB", str2 = "ABAB"

输出："AB"

示例 3：

输入：str1 = "LEET", str2 = "CODE"

输出：""

示例 4：

输入：str1 = "AAAAAB", str2 = "AAA"

输出：""

提示：

1 <= str1.length, str2.length <= 1000
str1 和 str2 由大写英文字母组成

方法二：数学 · Go 实现

思考

枚举仍要按长度尝试多种前缀。若存在公因子，则 $s_{1} + s_{2} = s_{2} + s_{1}$ ，且最长因子长度恰为 $gcd (| s_{1} |, | s_{2} |)$ 。

先判断拼接交换是否相等，再直接取 $s_{1}$ 的前 $gcd$ 个字符，省去逐长度验证。

若存在公因子串，则 $s_{1} + s_{2} = s_{2} + s_{1}$ 。此时最长公因子串的长度等于 $gcd (| s_{1} |, | s_{2} |)$ 。

时间复杂度 $O (m + n)$ ，空间复杂度 $O (m + n)$ 。其中 $m$ 和 $n$ 分别为两个字符串的长度。

go

func gcdOfStrings(str1 string, str2 string) string {
	if str1+str2 != str2+str1 {
		return ""
	}
	n := gcd(len(str1), len(str2))
	return str1[:n]
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

力扣原题 · Doocs 题解来源

LeetCode Go · 数学与几何（3） ​

812. 最大三角形面积 ​

829. 连续整数求和 ​

836. 矩形重叠 ​

840. 矩阵中的幻方 ​

843. 猜猜这个单词 ​

858. 镜面反射 ​

866. 回文质数 ​

869. 重新排序得到 2 的幂 ​

883. 三维形体投影面积 ​

891. 子序列宽度之和 ​

892. 三维形体的表面积 ​

899. 有序队列 ​

906. 超级回文数 ​

908. 最小差值 I ​

914. 卡牌分组 ​

927. 三等分 ​

932. 漂亮数组 ​

939. 最小面积矩形 ​

963. 最小面积矩形 II ​

970. 强整数 ​

972. 相等的有理数 ​

989. 数组形式的整数加法 ​

1015. 可被 K 整除的最小整数 ​

1017. 负二进制转换 ​

1030. 距离顺序排列矩阵单元格 ​

1033. 移动石子直到连续 ​

1037. 有效的回旋镖 ​

1041. 困于环中的机器人 ​

1056. 易混淆数 🔒 ​

1071. 字符串的最大公因子 ​

继续阅读

LeetCode Go · 数学与几何（3）

812. 最大三角形面积

829. 连续整数求和

836. 矩形重叠

840. 矩阵中的幻方

843. 猜猜这个单词

858. 镜面反射

866. 回文质数

869. 重新排序得到 2 的幂

883. 三维形体投影面积

891. 子序列宽度之和

892. 三维形体的表面积

899. 有序队列

906. 超级回文数

908. 最小差值 I

914. 卡牌分组

927. 三等分

932. 漂亮数组

939. 最小面积矩形

963. 最小面积矩形 II

970. 强整数

972. 相等的有理数

989. 数组形式的整数加法

1015. 可被 K 整除的最小整数

1017. 负二进制转换

1030. 距离顺序排列矩阵单元格

1033. 移动石子直到连续

1037. 有效的回旋镖

1041. 困于环中的机器人

1056. 易混淆数 🔒

1071. 字符串的最大公因子