LeetCode Go · 数学与几何（8）

2748. 美丽下标对的数目

简单1 种解法

标签：数组、哈希表、数学、计数、数论

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。

返回 nums 中 美丽下标对 的总数目。

对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 y 的 最大公因数 。

示例 1：

输入：nums = [2,5,1,4]
输出：5
解释：nums 中共有 5 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[2] 的最后一个数字是 1 。2 和 1 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。5 和 1 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。5 和 4 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。1 和 4 互质，因此 gcd(1,4) == 1 。
因此，返回 5 。

示例 2：

输入：nums = [11,21,12]
输出：2
解释：共有 2 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[2] 的最后一个数字是 2 。gcd(1,2) == 1 。
因此，返回 2 。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 9999
nums[i] % 10 != 0

方法一：计数 · Go 实现

思考

统计满足首位与末位互质的下标对。双重循环在 $n \leq 100$ 下可通过，但对每个左端点重复取首位。

从左到右扫描：用长度为 $10$ 的计数器记录已经出现过的首位，对当前数的末位枚举 $0. .9$ 中与之互质的计数并累加，再把当前首位写入计数器。

我们可以用一个长度为 $10$ 的数组 $cnt$ 来记录每个数字的第一个数字出现的次数。

遍历数组 $nums$ ，对于每个数字 $x$ ，我们枚举 $0$ 到 $9$ 的每个数字 $y$ ，如果 $cnt [y]$ 不为 $0$ 且 $gcd (x b \mod 10, y) = 1$ ，则答案加上 $cnt [y]$ 。然后，我们将 $x$ 的第一个数字出现的次数加 $1$ 。

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

时间复杂度 $O (n \times (k + \log M))$ ，空间复杂度 $O (k + \log M)$ 。其中 $n$ 为数组 $nums$ 的长度，而 $k$ 和 $M$ 分别表示数组 $nums$ 中的数字的种类以及最大值。

go

func countBeautifulPairs(nums []int) (ans int) {
	cnt := [10]int{}
	for _, x := range nums {
		for y := 0; y < 10; y++ {
			if cnt[y] > 0 && gcd(x%10, y) == 1 {
				ans += cnt[y]
			}
		}
		for x > 9 {
			x /= 10
		}
		cnt[x]++
	}
	return
}

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

力扣原题 · Doocs 题解来源

2761. 和等于目标值的质数对

中等1 种解法

标签：数组、数学、枚举、数论

题目、示例与约束

给你一个整数 n 。如果两个整数 x 和 y 满足下述条件，则认为二者形成一个质数对：

1 <= x <= y <= n
x + y == n
x 和 y 都是质数

请你以二维有序列表的形式返回符合题目要求的所有 [x_i, y_i] ，列表需要按 x_i 的 非递减顺序 排序。如果不存在符合要求的质数对，则返回一个空数组。

注意：质数是大于 1 的自然数，并且只有两个因子，即它本身和 1 。

示例 1：

输入：n = 10
输出：[[3,7],[5,5]]
解释：在这个例子中，存在满足条件的两个质数对。 
这两个质数对分别是 [3,7] 和 [5,5]，按照题面描述中的方式排序后返回。

示例 2：

输入：n = 2
输出：[]
解释：可以证明不存在和为 2 的质数对，所以返回一个空数组。

提示：

1 <= n <= 10⁶

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

思考

找出所有 $x + y = n$ 且两者皆质、 $x \leq y$ 的数对。对每个 $x$ 试除判断质数，在 $n \leq 10^{6}$ 时偏慢。

先用埃氏筛标记 $[2, n)$ 中的质数，再枚举 $x \in [2, n / 2]$ ，若 $x$ 与 $n - x$ 都为质则输出。

我们先预处理出 $n$ 范围内的所有质数，记录在数组 $p r i m e s$ 中，其中 $p r i m e s [i]$ 为 true 表示 $i$ 是一个质数。

接下来，我们在 $[2, \frac{n}{2}]$ 的范围内枚举 $x$ ，那么 $y = n - x$ ，如果 $p r i m e s [x]$ 和 $p r i m e s [y]$ 均为 true，那么 $(x, y)$ 是一个质数对，添加到答案中。

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

时间复杂度 $O (n \log \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是题目给定的数字。

go

func findPrimePairs(n int) (ans [][]int) {
	primes := make([]bool, n)
	for i := range primes {
		primes[i] = true
	}
	for i := 2; i < n; i++ {
		if primes[i] {
			for j := i + i; j < n; j += i {
				primes[j] = false
			}
		}
	}
	for x := 2; x <= n/2; x++ {
		y := n - x
		if primes[x] && primes[y] {
			ans = append(ans, []int{x, y})
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2769. 找出最大的可达成数字

简单1 种解法

标签：数学

题目、示例与约束

给你两个整数 num 和 t 。如果整数 x 可以在执行下述操作 不超过 t 次的情况下变为与 num 相等，则称其为 可达成数字 ：

每次操作将 x 的值增加或减少 1 ，同时可以选择将 num 的值增加或减少 1 。

返回所有可达成数字中的最大值 x。

示例 1：

输入：num = 4, t = 1

输出：6

解释：

执行下述操作可以使最大可达成数字等于 num ：

最大可达成数字减少 1 ，同时 num 增加 1 。

示例 2：

输入：num = 3, t = 2

输出：7

解释：

执行两次下述操作可以使最大可达成数字等于 num ：

最大可达成数字减少 1 ，同时 num 增加 1。

提示：

1 <= num, t <= 50

方法一：数学 · Go 实现

思考

一次操作让 $x$ 与 $n u m$ 朝相反方向各走 $1$ ，最多 $t$ 次，求能与 $n u m$ 相等的最大 $x$ 。模拟逐步逼近没有必要。

每次操作把 $x - n u m$ 缩小 $2$ ，故最大可行的 $x$ 为 $n u m + 2 t$ 。

我们注意到，每次操作可以将 $x$ 减少 $1$ ，同时将 $n u m$ 增加 $1$ ，这样 $x$ 和 $n u m$ 的差值就会减少 $2$ ，而最多可以操作 $t$ 次，所以最大可达成数字为 $n u m + t \times 2$ 。

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

go

func theMaximumAchievableX(num int, t int) int {
	return num + t*2
}

力扣原题 · Doocs 题解来源

2806. 取整购买后的账户余额

简单1 种解法

标签：数学

题目、示例与约束

一开始，你的银行账户里有 100 块钱。

给你一个整数purchaseAmount ，它表示你在一次购买中愿意支出的金额。

在一个商店里，你进行一次购买，实际支出的金额会向最近的 10 的倍数取整。换句话说，你实际会支付一个非负金额 roundedAmount ，满足 roundedAmount 是 10 的倍数且 abs(roundedAmount - purchaseAmount) 的值最小。

如果存在多于一个最接近的 10 的倍数，较大的倍数 是你的实际支出金额。

请你返回一个整数，表示你在愿意支出金额为 purchaseAmount 块钱的前提下，购买之后剩下的余额。

注意： 0 也是 10 的倍数。

示例 1：

输入：purchaseAmount = 9
输出：90
解释：这个例子中，最接近 9 的 10 的倍数是 10 。所以你的账户余额为 100 - 10 = 90 。

示例 2：

输入：purchaseAmount = 15
输出：80
解释：这个例子中，有 2 个最接近 15 的 10 的倍数：10 和 20，较大的数 20 是你的实际开销。
所以你的账户余额为 100 - 20 = 80 。

提示：

0 <= purchaseAmount <= 100

方法一：枚举 + 模拟 · Go 实现

思考

购买额在 $[0, 100]$ ，须四舍五入到最近的 $10$ 的倍数（距离相等时取较大者），余额为 $100$ 减去该值。十一个候选均可枚举。自 $100$ 递减并仅在距离严格更小时更新，从而在平局时保留较大的倍数。

我们在 $[0, 100]$ 的范围内枚举所有的 $10$ 的倍数，然后找到与 purchaseAmount 最接近的那个数，记为 $x$ ，那么答案就是 $100 - x$ 。

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

go

func accountBalanceAfterPurchase(purchaseAmount int) int {
	diff, x := 100, 0
	for y := 100; y >= 0; y -= 10 {
		t := abs(y - purchaseAmount)
		if t < diff {
			diff = t
			x = y
		}
	}
	return 100 - x
}

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

力扣原题 · Doocs 题解来源

2843. 统计对称整数的数目

简单1 种解法

标签：数学、枚举

题目、示例与约束

给你两个正整数 low 和 high 。

对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。

返回在 [low, high] 范围内的 对称整数的数目 。

示例 1：

输入：low = 1, high = 100
输出：9
解释：在 1 到 100 范围内共有 9 个对称整数：11、22、33、44、55、66、77、88 和 99 。

示例 2：

输入：low = 1200, high = 1230
输出：4
解释：在 1200 到 1230 范围内共有 4 个对称整数：1203、1212、1221 和 1230 。

提示：

1 <= low <= high <= 10⁴

方法一：枚举 · Go 实现

思考

$h i g h \leq 10^{4}$ ，枚举区间内每个整数并判断位数为偶数且左右半段数字和相等即可。无需数位 DP。

我们枚举 $[l o w, h i g h]$ 中的每个整数 $x$ ，判断其是否是对称整数。如果是，那么答案 $a n s$ 增加 $1$ 。

时间复杂度 $O (n \times \log m)$ ，空间复杂度 $O (\log m)$ 。其中 $n$ 是 $[l o w, h i g h]$ 中整数的个数，而 $m$ 是题目中给出的最大整数。

go

func countSymmetricIntegers(low int, high int) (ans int) {
	f := func(x int) int {
		s := strconv.Itoa(x)
		n := len(s)
		if n&1 == 1 {
			return 0
		}
		a, b := 0, 0
		for i := 0; i < n/2; i++ {
			a += int(s[i] - '0')
			b += int(s[n/2+i] - '0')
		}
		if a == b {
			return 1
		}
		return 0
	}
	for x := low; x <= high; x++ {
		ans += f(x)
	}
	return
}

力扣原题 · Doocs 题解来源

2849. 判断能否在给定时间到达单元格

中等1 种解法

标签：数学

题目、示例与约束

给你四个整数 sx、sy、fx、fy 以及一个 非负整数 t 。

在一个无限的二维网格中，你从单元格 (sx, sy) 开始出发。每一秒，你必须移动到任一与之前所处单元格相邻的单元格中。

如果你能在恰好 t 秒后到达单元格 (fx, fy) ，返回 true ；否则，返回 false 。

单元格的 相邻单元格 是指该单元格周围与其至少共享一个角的 8 个单元格。你可以多次访问同一个单元格。

示例 1：

输入：sx = 2, sy = 4, fx = 7, fy = 7, t = 6
输出：true
解释：从单元格 (2, 4) 开始出发，穿过上图标注的单元格，可以在恰好 6 秒后到达单元格 (7, 7) 。

示例 2：

输入：sx = 3, sy = 1, fx = 7, fy = 3, t = 3
输出：false
解释：从单元格 (3, 1) 开始出发，穿过上图标注的单元格，至少需要 4 秒后到达单元格 (7, 3) 。 因此，无法在 3 秒后到达单元格 (7, 3) 。

提示：

1 <= sx, sy, fx, fy <= 10⁹
0 <= t <= 10⁹

方法一：分情况讨论 · Go 实现

思考

每秒可走相邻八个方向，最短时间是切比雪夫距离 $max (| d x |, | d y |)$ 。起点与终点重合时， $t = 1$ 会走出再无法在下一秒回到原处（除非再花时间），故仅当 $t \neq 1$ 可达；其余情形只要 $t$ 不小于该距离即可，多出的时间可在附近迂回。

如果起点和终点相同，那么只有当 $t \neq 1$ 时，才能在给定时间到达终点。

否则，我们可以计算出起点和终点的横纵坐标之差，然后取最大值，如果最大值小于等于给定时间，那么就可以在给定时间到达终点。

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

go

func isReachableAtTime(sx int, sy int, fx int, fy int, t int) bool {
	if sx == fx && sy == fy {
		return t != 1
	}
	dx := abs(sx - fx)
	dy := abs(sy - fy)
	return max(dx, dy) <= t
}

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

力扣原题 · Doocs 题解来源

2862. 完全子集的最大元素和

困难1 种解法

标签：数组、数学、数论

题目、示例与约束

给你一个下标从 1 开始、由 n 个整数组成的数组。你需要从 nums 选择一个 完全集，其中每对元素下标的乘积都是一个完全平方数，例如选择 a_i 和 a_j ，i * j 一定是完全平方数。

返回 完全子集 所能取到的 最大元素和 。

示例 1：

输入：nums = [8,7,3,5,7,2,4,9]

输出：16

解释：

我们选择下标为 2 和 8 的元素，并且 2 * 8 是一个完全平方数。

示例 2：

输入：nums = [8,10,3,8,1,13,7,9,4]

输出：20

解释：

我们选择下标为 1, 4, 9 的元素。1 * 4, 1 * 9, 4 * 9 是完全平方数。

提示：

1 <= n == nums.length <= 10⁴
1 <= nums[i] <= 10⁹

方法一：枚举 · Go 实现

思考

下标集合完全当且仅当任意两下标之积为完全平方数，即它们除去平方因子后的核相同。枚举核 $k$ ，累加所有形如 $k \cdot j^{2}$ 的下标对应的值，取最大和。

我们注意到，如果一个数字可以表示成 $k \times j^{2}$ 的形式，那么所有该形式的数字的 $k$ 是相同的。

因此，我们可以在 $[1, . . n]$ 范围内枚举 $k$ ，然后从 $1$ 开始枚举 $j$ ，每一次累加 $n u m s [k \times j^{2} - 1]$ 的值到 $t$ 中，直到 $k \times j^{2} > n$ 。此时更新答案为 $a n s = max (a n s, t)$ 。

最后返回答案 $a n s$ 即可。

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

go

func maximumSum(nums []int) (ans int64) {
	n := len(nums)
	for k := 1; k <= n; k++ {
		var t int64
		for j := 1; k*j*j <= n; j++ {
			t += int64(nums[k*j*j-1])
		}
		ans = max(ans, t)
	}
	return
}

力扣原题 · Doocs 题解来源

2894. 分类求和并作差

简单1 种解法

标签：数学

题目、示例与约束

给你两个正整数 n 和 m 。

现定义两个整数 num1 和 num2 ，如下所示：

num1：范围 [1, n] 内所有 无法被 m 整除的整数之和。
num2：范围 [1, n] 内所有 能够被 m 整除的整数之和。

返回整数 num1 - num2 。

示例 1：

输入：n = 10, m = 3
输出：19
解释：在这个示例中：
- 范围 [1, 10] 内无法被 3 整除的整数为 [1,2,4,5,7,8,10] ，num1 = 这些整数之和 = 37 。
- 范围 [1, 10] 内能够被 3 整除的整数为 [3,6,9] ，num2 = 这些整数之和 = 18 。
返回 37 - 18 = 19 作为答案。

示例 2：

输入：n = 5, m = 6
输出：15
解释：在这个示例中：
- 范围 [1, 5] 内无法被 6 整除的整数为 [1,2,3,4,5] ，num1 = 这些整数之和 =  15 。
- 范围 [1, 5] 内能够被 6 整除的整数为 [] ，num2 = 这些整数之和 = 0 。
返回 15 - 0 = 15 作为答案。

示例 3：

输入：n = 5, m = 1
输出：-15
解释：在这个示例中：
- 范围 [1, 5] 内无法被 1 整除的整数为 [] ，num1 = 这些整数之和 = 0 。 
- 范围 [1, 5] 内能够被 1 整除的整数为 [1,2,3,4,5] ，num2 = 这些整数之和 = 15 。
返回 0 - 15 = -15 作为答案。

提示：

1 <= n, m <= 1000

方法一：模拟 · Go 实现

思考

$n$ 不大，遍历 $[1, n]$ ：能被 $m$ 整除则从答案中减去，否则加上，即 $n u m_{1} - n u m_{2}$ 。

我们遍历区间 $[1, n]$ 中的每一个数，如果它能被 $m$ 整除，那么答案就减去这个数，否则答案就加上这个数。

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

时间复杂度 $O (n)$ ，其中 $n$ 是题目给定的整数。空间复杂度 $O (1)$ 。

go

func differenceOfSums(n int, m int) (ans int) {
	for i := 1; i <= n; i++ {
		if i%m == 0 {
			ans -= i
		} else {
			ans += i
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2927. 给小朋友们分糖果 III 🔒

困难1 种解法

标签：数学、组合数学

题目、示例与约束

你被给定两个正整数 n 和 limit。

返回 在每个孩子得到不超过 limit 个糖果的情况下，将 n 个糖果分发给 3 个孩子的 总方法数。

示例 1:

输入：n = 5, limit = 2
输出：3
解释：有 3 种方式将 5 个糖果分发给 3 个孩子，使得每个孩子得到不超过 2 个糖果：(1, 2, 2), (2, 1, 2) 和 (2, 2, 1)。

示例 2:

输入：n = 3, limit = 3
输出：10
解释：有 10 种方式将 3 个糖果分发给 3 个孩子，使得每个孩子得到不超过 3 个糖果：(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) 和 (3, 0, 0)。

提示：

1 <= n <= 10⁸
1 <= limit <= 10⁸

方法一：组合数学 + 容斥原理 · Go 实现

思考

非负整数解 $x + y + z = n$ 且 $0 \leq x, y, z \leq l i m i t$ 。 $n$ 可达 $10^{18}$ 量级，三重循环不可用。无上界时隔板法给出 $C_{n + 2}^{2}$ ；再容斥减去某变量至少 $l i m i t + 1$ 的方案，并加回两个变量同时越界的方案。

若 $n > 3 \cdot l i m i t$ 则直接为 $0$ 。实现时对组合数自变量加判断，以免负数阶乘。公式为常数时间。

根据题目描述，我们需要将 $n$ 个糖果分给 $3$ 个小孩，每个小孩分到的糖果数在 $[0, l i m i t]$ 之间。

这实际上等价于把 $n$ 个球放入 $3$ 个盒子中。由于盒子可以为空，我们可以再增加 $3$ 个虚拟球，然后再利用隔板法，即一共有 $n + 3$ 个球，我们在其中 $n + 3 - 1$ 个位置插入 $2$ 个隔板，从而将实际的 $n$ 个球分成 $3$ 组，并且允许盒子为空，因此初始方案数为 $C_{n + 2}^{2}$ 。

我们需要在这些方案中，排除掉存在盒子分到的小球数超过 $l i m i t$ 的方案。考虑其中有一个盒子分到的小球数超过 $l i m i t$ ，那么剩下的球（包括虚拟球）最多有 $n + 3 - (l i m i t + 1) = n - l i m i t + 2$ 个，位置数为 $n - l i m i t + 1$ ，因此方案数为 $C_{n - l i m i t + 1}^{2}$ 。由于存在 $3$ 个盒子，因此这样的方案数为 $3 \times C_{n - l i m i t + 1}^{2}$ 。这样子算，我们会多排除掉同时存在两个盒子分到的小球数超过 $l i m i t$ 的方案，因此我们需要再加上这样的方案数，即 $3 \times C_{n - 2 \times l i m i t}^{2}$ 。

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

go

func distributeCandies(n int, limit int) int64 {
	comb2 := func(n int) int {
		return n * (n - 1) / 2
	}
	if n > 3*limit {
		return 0
	}
	ans := comb2(n + 2)
	if n > limit {
		ans -= 3 * comb2(n-limit+1)
	}
	if n-2 >= 2*limit {
		ans += 3 * comb2(n-2*limit)
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2928. 给小朋友们分糖果 I

简单1 种解法

标签：数学、组合数学、枚举

题目、示例与约束

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

提示：

1 <= n <= 50
1 <= limit <= 50

方法一：组合数学 + 容斥原理 · Go 实现

思考

与 III 相同的三点分配，仅 $n, l i m i t \leq 50$ 。三重枚举可行，但隔板加容斥仍是闭式： $C_{n + 2}^{2}$ 减去三个「某人超过 $l i m i t$ 」的情形，再加回两人同时越界。

$n > 3 \cdot l i m i t$ 时无解。约束很小，公式与较大数据版本共用，避免两套逻辑。

根据题目描述，我们需要将 $n$ 个糖果分给 $3$ 个小孩，每个小孩分到的糖果数在 $[0, l i m i t]$ 之间。

这实际上等价于把 $n$ 个球放入 $3$ 个盒子中。由于盒子可以为空，我们可以再增加 $3$ 个虚拟球，然后再利用隔板法，即一共有 $n + 3$ 个球，我们在其中 $n + 3 - 1$ 个位置插入 $2$ 个隔板，从而将实际的 $n$ 个球分成 $3$ 组，并且允许盒子为空，因此初始方案数为 $C_{n + 2}^{2}$ 。

我们需要在这些方案中，排除掉存在盒子分到的小球数超过 $l i m i t$ 的方案。考虑其中有一个盒子分到的小球数超过 $l i m i t$ ，那么剩下的球（包括虚拟球）最多有 $n + 3 - (l i m i t + 1) = n - l i m i t + 2$ 个，位置数为 $n - l i m i t + 1$ ，因此方案数为 $C_{n - l i m i t + 1}^{2}$ 。由于存在 $3$ 个盒子，因此这样的方案数为 $3 \times C_{n - l i m i t + 1}^{2}$ 。这样子算，我们会多排除掉同时存在两个盒子分到的小球数超过 $l i m i t$ 的方案，因此我们需要再加上这样的方案数，即 $3 \times C_{n - 2 \times l i m i t}^{2}$ 。

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

go

func distributeCandies(n int, limit int) int {
	comb2 := func(n int) int {
		return n * (n - 1) / 2
	}
	if n > 3*limit {
		return 0
	}
	ans := comb2(n + 2)
	if n > limit {
		ans -= 3 * comb2(n-limit+1)
	}
	if n-2 >= 2*limit {
		ans += 3 * comb2(n-2*limit)
	}
	return ans
}

力扣原题 · Doocs 题解来源

2929. 给小朋友们分糖果 II

中等1 种解法

标签：数学、组合数学、枚举

题目、示例与约束

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

提示：

1 <= n <= 10⁶
1 <= limit <= 10⁶

方法一：组合数学 + 容斥原理 · Go 实现

思考

约束升至 $n, l i m i t \leq 10^{6}$ ，枚举两个变量已达 $O (n)$ ，在部分语言中偏紧。容斥公式与 I、III 相同，组合数 $C_{m}^{2} = m (m - 1) / 2$ 可 $O (1)$ 计算。

因此仍先判 $n > 3 \cdot l i m i t$ ，再对无约束、单人越界、双人越界三项做加减。无需循环。

根据题目描述，我们需要将 $n$ 个糖果分给 $3$ 个小孩，每个小孩分到的糖果数在 $[0, l i m i t]$ 之间。

这实际上等价于把 $n$ 个球放入 $3$ 个盒子中。由于盒子可以为空，我们可以再增加 $3$ 个虚拟球，然后再利用隔板法，即一共有 $n + 3$ 个球，我们在其中 $n + 3 - 1$ 个位置插入 $2$ 个隔板，从而将实际的 $n$ 个球分成 $3$ 组，并且允许盒子为空，因此初始方案数为 $C_{n + 2}^{2}$ 。

我们需要在这些方案中，排除掉存在盒子分到的小球数超过 $l i m i t$ 的方案。考虑其中有一个盒子分到的小球数超过 $l i m i t$ ，那么剩下的球（包括虚拟球）最多有 $n + 3 - (l i m i t + 1) = n - l i m i t + 2$ 个，位置数为 $n - l i m i t + 1$ ，因此方案数为 $C_{n - l i m i t + 1}^{2}$ 。由于存在 $3$ 个盒子，因此这样的方案数为 $3 \times C_{n - l i m i t + 1}^{2}$ 。这样子算，我们会多排除掉同时存在两个盒子分到的小球数超过 $l i m i t$ 的方案，因此我们需要再加上这样的方案数，即 $3 \times C_{n - 2 \times l i m i t}^{2}$ 。

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

go

func distributeCandies(n int, limit int) int64 {
	comb2 := func(n int) int {
		return n * (n - 1) / 2
	}
	if n > 3*limit {
		return 0
	}
	ans := comb2(n + 2)
	if n > limit {
		ans -= 3 * comb2(n-limit+1)
	}
	if n-2 >= 2*limit {
		ans += 3 * comb2(n-2*limit)
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2946. 循环移位后的矩阵相似检查

简单1 种解法

标签：数组、数学、矩阵、模拟

题目、示例与约束

给你一个下标从 0 开始且大小为 m x n 的整数矩阵 mat 和一个整数 k 。矩阵行的下标是从 0 开始的。

进行下面操作 k 次：

偶数行（0, 2, 4, ...）循环向左移动。

奇数行（1, 3, 5, ...）循环向右移动。

如果经过 k 步后的最终修改矩阵与原始矩阵相同，则返回 true，否则返回 false。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 4

输出：false

解释：

在每一步中，行 0 和行 2（偶数下标）进行左移，行 1（奇数下标）进行右移。

示例 2：

输入：mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2

输出：true

解释：

示例 3：

输入：mat = [[2,2],[2,2]], k = 3

输出：true

解释：

矩阵中的所有值都相等，即使进行循环移位，矩阵也会保持不变。

提示：

1 <= mat.length <= 25
1 <= mat[i].length <= 25
1 <= mat[i][j] <= 25
1 <= k <= 50

方法一：模拟 · Go 实现

思考

奇数行右移 $k$ 、偶数行左移 $k$ 后须与原矩阵相同。 $k$ 可先对列数取模，但直接比较「移位后应对齐的格子」不必真的旋转。

对每个 $(i, j)$ ，奇数行看 $m a t [i] [(j + k) mod n]$ ，偶数行看 $m a t [i] [(j - k + n) mod n]$ ，有一处不等即否。矩阵不超过 $25 \times 25$ 。

我们遍历矩阵的每个元素，判断其在循环移位后的位置是否与原位置的元素相同。

对于奇数行，我们将元素向右移动 $k$ 个位置，因此元素 $(i, j)$ 在循环移位后的位置为 $(i, (j + k) mod n)$ ，其中 $n$ 是矩阵的列数。

对于偶数行，我们将元素向左移动 $k$ 个位置，因此元素 $(i, j)$ 在循环移位后的位置为 $(i, (j - k + n) mod n)$ 。

如果在遍历过程中发现有任何一个元素在循环移位后的位置与原位置的元素不同，则返回 $false$ 。如果遍历完成后所有元素都相同，则返回 $true$ 。

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

go

func areSimilar(mat [][]int, k int) bool {
	n := len(mat[0])
	k %= n
	for i, row := range mat {
		for j, x := range row {
			if i%2 == 1 && x != mat[i][(j+k)%n] {
				return false
			}
			if i%2 == 0 && x != mat[i][(j-k+n)%n] {
				return false
			}
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

2954. 统计感冒序列的数目

困难1 种解法

标签：数组、数学、组合数学、费马小定理

题目、示例与约束

给你一个整数 n 和一个下标从 0 开始的整数数组 sick ，数组按升序排序。

有 n 位小朋友站成一排，按顺序编号为 0 到 n - 1 。数组 sick 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i - 1 或者 i + 1 的小朋友，前提是被传染的小朋友存在且还没有得感冒。每一秒中， 至多一位 还没感冒的小朋友会被传染。

经过有限的秒数后，队列中所有小朋友都会感冒。感冒序列 指的是所有一开始没有感冒的小朋友最后得感冒的顺序序列。请你返回所有感冒序列的数目。

由于答案可能很大，请你将答案对 10⁹ + 7 取余后返回。

注意，感冒序列不包含一开始就得了感冒的小朋友的下标。

示例 1：

输入：n = 5, sick = [0,4]
输出：4
解释：一开始，下标为 1 ，2 和 3 的小朋友没有感冒。总共有 4 个可能的感冒序列：
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着有感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 2 的小朋友被传染。
最后，下标为 3 的小朋友被传染，因为他挨着感冒的小朋友 2 和 4 ，感冒序列为 [1,2,3] 。
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 3 的小朋友被传染。
最后，下标为 2 的小朋友被传染，因为他挨着感冒的小朋友 1 和 3 ，感冒序列为  [1,3,2] 。
- 感冒序列 [3,1,2] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。
- 感冒序列 [3,2,1] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。

示例 2：

输入：n = 4, sick = [1]
输出：3
解释：一开始，下标为 0 ，2 和 3 的小朋友没有感冒。总共有 3 个可能的感冒序列：
- 感冒序列 [0,2,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。
- 感冒序列 [2,0,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。
- 感冒序列 [2,3,0] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。

提示：

2 <= n <= 10⁵
1 <= sick.length <= n - 1
0 <= sick[i] <= n - 1
sick 按升序排列。

方法一：组合数学 + 乘法逆元 + 快速幂 · Go 实现

思考

已感染下标把未感染者切成若干间隙。全部间隙的感染顺序是多重集排列 $s! / \prod x_{i}!$ ，其中 $s$ 为未感染总数。两端的间隙只能从内侧单向推进，中间间隙每次可从左右两端选一侧，有 $2^{x - 1}$ 种。

预处理阶乘，除法用逆元，幂用快速幂。 $n \leq 10^{5}$ ，线性预处理即可。

根据题目描述，感冒的小朋友把还没有感冒的小朋友划分成了若干个连续段。我们可以用一个数组 $n u m s$ 记录每一段不感冒的小朋友的认识，不感冒人数一共有 $s = \sum_{i = 0}^{k} n u m s [k]$ 人。我们可以发现，感冒序列的数目就是 $s$ 个不同元素的全排列数，即 $s!$ 。

假设每一段不感冒小朋友只有一种传播方案，那么一共有 $\frac{s!}{\prod_{i = 0}^{k} n u m s [k]!}$ 种感冒序列。

接下来，我们再考虑每一段不感冒小朋友的传播方案。假设一段不感冒小朋友有 $x$ 个人，那么他们的传播方案有 $2^{x - 1}$ 种，因为每一次可以从一段的左右两端选择其中一端传播，即：两种选择，一共有 $x - 1$ 次传播。不过，如果是第一段或者最后一段，那么只有一种选择。

综上所述，总的感冒序列数目为：

\frac{s!}{\prod_{i = 0}^{k} n u m s [k]!} \prod_{i = 1}^{k - 1} 2^{n u m s [i] - 1}

最后，我们需要考虑到答案可能很大，需要对 $10^{9} + 7$ 取模。因此，我们需要预处理阶乘和乘法逆元。

时间复杂度 $O (m)$ ，其中 $m$ 是数组 $s i c k$ 的长度。忽略预处理数组的空间消耗，空间复杂度 $O (m)$ 。

go

const MX = 1e5
const MOD = 1e9 + 7

var fac [MX + 1]int

func init() {
	fac[0] = 1
	for i := 1; i <= MX; i++ {
		fac[i] = fac[i-1] * i % MOD
	}
}

func qpow(a, n int) int {
	ans := 1
	for n > 0 {
		if n&1 == 1 {
			ans = (ans * a) % MOD
		}
		a = (a * a) % MOD
		n >>= 1
	}
	return ans
}

func numberOfSequence(n int, sick []int) int {
	m := len(sick)
	nums := make([]int, m+1)

	nums[0] = sick[0]
	nums[m] = n - sick[m-1] - 1
	for i := 1; i < m; i++ {
		nums[i] = sick[i] - sick[i-1] - 1
	}

	s := 0
	for _, x := range nums {
		s += x
	}
	ans := fac[s]
	for _, x := range nums {
		if x > 0 {
			ans = ans * qpow(fac[x], MOD-2) % MOD
		}
	}
	for i := 1; i < len(nums)-1; i++ {
		if nums[i] > 1 {
			ans = ans * qpow(2, nums[i]-1) % MOD
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2961. 双模幂运算

中等1 种解法

标签：数组、数学、模拟

题目、示例与约束

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [a_i, b_i, c_i, m_i]，以及一个整数 target 。

如果满足以下公式，则下标 i 是 好下标：

0 <= i < variables.length
((a_i^b_i % 10)^c_i) % m_i == target

返回一个由 好下标 组成的数组，顺序不限 。

示例 1：

输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
输出：[0,2]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(2³ % 10)³ % 10 = 2 。
2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(3³ % 10)³ % 1 = 0 。
3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(6¹ % 10)¹ % 4 = 2 。
因此，返回 [0,2] 作为答案。

示例 2：

输入：variables = [[39,3,1000,1000]], target = 17
输出：[]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(39³ % 10)¹⁰⁰⁰ % 1000 = 1 。
因此，返回 [] 作为答案。

提示：

1 <= variables.length <= 100
variables[i] == [a_i, b_i, c_i, m_i]
1 <= a_i, b_i, c_i, m_i <= 10³
0 <= target <= 10³

方法一：模拟 + 快速幂 · Go 实现

思考

判断 $(a^{b} mod 10)^{c} mod m$ 是否等于 $t a r g e t$ 。指数与模均 $\leq 10^{3}$ ，直接快速幂两层即可，无需预处理。

外层枚举 $v a r i a b l e s$ 收集下标。

我们直接根据题目描述模拟即可。对于幂运算取模，我们可以使用快速幂来加速运算。

时间复杂度 $O (n \times \log M)$ ，其中 $n$ 为数组 $v a r i a b l e s$ 的长度；而 $M$ 为 $b_{i}$ 和 $c_{i}$ 中的最大值，本题中 $M \leq 10^{3}$ 。空间复杂度 $O (1)$ 。

go

func getGoodIndices(variables [][]int, target int) (ans []int) {
	qpow := func(a, n, mod int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	for i, e := range variables {
		a, b, c, m := e[0], e[1], e[2], e[3]
		if qpow(qpow(a, b, 10), c, m) == target {
			ans = append(ans, i)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2963. 统计好分割方案的数目

困难1 种解法

标签：数组、哈希表、数学、组合数学

题目、示例与约束

给你一个下标从 0 开始、由 正整数 组成的数组 nums。

将数组分割成一个或多个连续子数组，如果不存在包含了相同数字的两个子数组，则认为是一种 好分割方案 。

返回 nums 的 好分割方案 的数目。

由于答案可能很大，请返回答案对 10⁹ + 7 取余的结果。

示例 1：

输入：nums = [1,2,3,4]
输出：8
解释：有 8 种 好分割方案 ：([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]) 和 ([1,2,3,4]) 。

示例 2：

输入：nums = [1,1,1,1]
输出：1
解释：唯一的 好分割方案 是：([1,1,1,1]) 。

示例 3：

输入：nums = [1,2,1,3]
输出：2
解释：有 2 种 好分割方案 ：([1,2,1], [3]) 和 ([1,2,1,3]) 。

提示：

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

方法一：哈希表 + 分组 + 快速幂 · Go 实现

思考

好划分要求相同值落在同一段，故每个值的首次到末次必须覆盖在一段内。用最后出现下标 $l a s t$ 把数组切成若干不可再拆的块；块与块之间的切缝可以任选切或不切。

扫描时用 $j$ 维护当前块右端，每当 $i = j$ 则块数 $k$ 加一。 $k$ 块有 $k - 1$ 条可选缝，方案 $2^{k - 1}$ 取模。

根据题目描述，我们可以知道，相同的数字必须在同一个子数组中。因此，我们用一个哈希表 $l a s t$ 记录每个数字最后一次出现的下标。

接下来，我们用一个下标 $j$ 标识已经出现过的元素中最后一个元素的下标，用一个变量 $k$ 记录当前可以划分的子数组的个数。

然后，我们从左到右遍历数组 $n u m s$ ，对于当前遍历到的数字 $n u m s [i]$ ，我们获取其最后一次出现的下标，更新 $j = max (j, l a s t [n u m s [i]])$ 。如果 $i = j$ ，那么说明当前位置可以是一个子数组的结尾，我们将 $k$ 增加 $1$ 。继续遍历，直到遍历完整个数组。

最后，我们考虑 $k$ 个子数组的划分方案数。子数组数量为 $k$ ，有 $k - 1$ 个位置可以划分（拼接），因此方案数为 $2^{k - 1}$ 。由于答案可能很大，我们需要对 $10^{9} + 7$ 取模。这里我们可以使用快速幂来加速运算。

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

go

func numberOfGoodPartitions(nums []int) int {
	qpow := func(a, n, mod int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	last := map[int]int{}
	for i, x := range nums {
		last[x] = i
	}
	const mod int = 1e9 + 7
	j, k := -1, 0
	for i, x := range nums {
		j = max(j, last[x])
		if i == j {
			k++
		}
	}
	return qpow(2, k-1, mod)
}

力扣原题 · Doocs 题解来源

2965. 找出缺失和重复的数字

简单1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n²] 范围内。除了 a 出现两次，b 缺失之外，每个整数都 恰好出现一次 。

任务是找出重复的数字a 和缺失的数字 b 。

返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。

示例 1：

输入：grid = [[1,3],[2,2]]
输出：[2,4]
解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。

示例 2：

输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
输出：[9,5]
解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。

提示：

2 <= n == grid.length == grid[i].length <= 50
1 <= grid[i][j] <= n * n
对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。

方法一：计数 · Go 实现

思考

$n \times n$ 矩阵应含 $1 \dots n^{2}$ 各一次，却有一个重复、一个缺失。 $n \leq 50$ ，开 $n^{2} + 1$ 的计数数组扫两遍即可。

出现 $2$ 次者为重复， $0$ 次者为缺失。无需数学公式。

我们创建一个长度为 $n^{2} + 1$ 的数组 $c n t$ ，统计矩阵中每个数字出现的次数。

接下来遍历 $i \in [1, n^{2}]$ ，如果 $c n t [i] = 2$ ，则 $i$ 是重复的数字，我们将答案的第一个元素设为 $i$ ；如果 $c n t [i] = 0$ ，则 $i$ 是缺失的数字，我们将答案的第二个元素设为 $i$ 。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n^{2})$ 。其中 $n$ 是矩阵的边长。

go

func findMissingAndRepeatedValues(grid [][]int) []int {
	n := len(grid)
	ans := make([]int, 2)
	cnt := make([]int, n*n+1)
	for _, row := range grid {
		for _, x := range row {
			cnt[x]++
			if cnt[x] == 2 {
				ans[0] = x
			}
		}
	}
	for x := 1; ; x++ {
		if cnt[x] == 0 {
			ans[1] = x
			return ans
		}
	}
}

力扣原题 · Doocs 题解来源

3001. 捕获黑皇后需要的最少移动次数

中等1 种解法

标签：数学、枚举

题目、示例与约束

现有一个下标从 1 开始的 8 x 8 棋盘，上面有 3 枚棋子。

给你 6 个整数 a 、b 、c 、d 、e 和 f ，其中：

(a, b) 表示白色车的位置。
(c, d) 表示白色象的位置。
(e, f) 表示黑皇后的位置。

假定你只能移动白色棋子，返回捕获黑皇后所需的最少移动次数。

请注意：

车可以向垂直或水平方向移动任意数量的格子，但不能跳过其他棋子。
象可以沿对角线方向移动任意数量的格子，但不能跳过其他棋子。
如果车或象能移向皇后所在的格子，则认为它们可以捕获皇后。
皇后不能移动。

示例 1：

输入：a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
输出：2
解释：将白色车先移动到 (1, 3) ，然后移动到 (2, 3) 来捕获黑皇后，共需移动 2 次。
由于起始时没有任何棋子正在攻击黑皇后，要想捕获黑皇后，移动次数不可能少于 2 次。

示例 2：

输入：a = 5, b = 3, c = 3, d = 4, e = 5, f = 2
输出：1
解释：可以通过以下任一方式移动 1 次捕获黑皇后：
- 将白色车移动到 (5, 2) 。
- 将白色象移动到 (5, 2) 。

提示：

1 <= a, b, c, d, e, f <= 8
两枚棋子不会同时出现在同一个格子上。

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

思考

棋盘仅 $8 \times 8$ ，枚举车、象的走法并模拟阻挡在常数时间内可行。车与象各自最多走一步即可到达任意与自己共线的格子，因此答案至多为 $2$ 。

真正需要判定的是「一步能否直接吃到皇后」。车同行列、象同对角线时，只要中间没有另一枚己方棋子挡住，一步即可。

代码用乘积 $(d - b) (d - f) > 0$ 等判断挡子是否落在开区间外侧。四类共线均不成立时，车绕行两步总能吃到皇后。

根据题意，我们可以将捕获黑皇后的情况分为以下几种：

白色车和黑皇后在同一行，且中间没有其他棋子，此时只需要移动白色车 $1$ 一次；
白色车和黑皇后在同一列，且中间没有其他棋子，此时只需要移动白色车 $1$ 一次；
白色象和黑皇后在对角线 \ 上，且中间没有其他棋子，此时只需要移动白色象 $1$ 一次；
白色象和黑皇后在对角线 / 上，且中间没有其他棋子，此时只需要移动白色象 $1$ 一次；
其他情况，只需要移动两次。

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

go

func minMovesToCaptureTheQueen(a int, b int, c int, d int, e int, f int) int {
	if a == e && (c != a || (d-b)*(d-f) > 0) {
		return 1
	}
	if b == f && (d != b || (c-a)*(c-e) > 0) {
		return 1
	}
	if c-e == d-f && (a-e != b-f || (a-c)*(a-e) > 0) {
		return 1
	}
	if c-e == f-d && (a-e != f-b || (a-c)*(a-e) > 0) {
		return 1
	}
	return 2
}

力扣原题 · Doocs 题解来源

3021. Alice 和 Bob 玩鲜花游戏

中等2 种解法

标签：数学

题目、示例与约束

Alice 和 Bob 在一片田野上玩一个回合制游戏，他们之间有两排花。Alice 和 Bob 之间第一排有 x 朵花，第二排有 y 朵花。

游戏过程如下：

Alice 先行动。
每一次行动中，当前玩家必须选择其中一排，然后在这边摘一朵鲜花。
一次行动结束后，如果两排上都没有剩下鲜花，那么当前玩家抓住对手并赢得游戏的胜利。

给你两个整数 n 和 m ，你的任务是求出满足以下条件的所有 (x, y) 对：

按照上述规则，Alice 必须赢得游戏。
第一排的鲜花数目 x 必须在区间 [1,n] 之间。
第二排的鲜花数目 y 必须在区间 [1,m] 之间。

请你返回满足题目描述的数对 (x, y) 的数目。

示例 1：

输入：n = 3, m = 2
输出：3
解释：以下数对满足题目要求：(1,2) ，(3,2) ，(2,1) 。

示例 2：

输入：n = 1, m = 1
输出：0
解释：没有数对满足题目要求。

提示：

1 <= n, m <= 10⁵

方法一：数学 · Go 实现

思考

每步从某一行摘一朵，先手在 $x + y$ 为奇数时获胜。 $n, m \leq 10^{5}$ ，枚举格子不可行。

奇数对偶数、偶数对奇数各构成合法对。两侧奇数个数为 $⌈ n / 2 ⌉$ 等，乘积相加即得。

因此用整除直接计算四类奇偶个数再交叉相乘。

根据题目描述，每一次行动，玩家都会选择顺时针或者逆时针方向，然后摘一朵鲜花。由于 Alice 先行动，因此当 $x + y$ 为奇数时，Alice 一定会赢得游戏。

因此，鲜花数目 $x$ 和 $y$ 满足以下条件：

$x + y$ 为奇数；
$1 \leq x \leq n$ ；
$1 \leq y \leq m$ 。

若 $x$ 为奇数， $y$ 一定为偶数。此时 $x$ 的取值个数为 $⌈ \frac{n}{2} ⌉$ ， $y$ 的取值个数为 $⌊ \frac{m}{2} ⌋$ ，因此满足条件的数对个数为 $⌈ \frac{n}{2} ⌉ \times ⌊ \frac{m}{2} ⌋$ 。

若 $x$ 为偶数， $y$ 一定为奇数。此时 $x$ 的取值个数为 $⌊ \frac{n}{2} ⌋$ ， $y$ 的取值个数为 $⌈ \frac{m}{2} ⌉$ ，因此满足条件的数对个数为 $⌊ \frac{n}{2} ⌋ \times ⌈ \frac{m}{2} ⌉$ 。

因此，满足条件的数对个数为 $⌈ \frac{n}{2} ⌉ \times ⌊ \frac{m}{2} ⌋ + ⌊ \frac{n}{2} ⌋ \times ⌈ \frac{m}{2} ⌉$ ，即 $⌊ \frac{n + 1}{2} ⌋ \times ⌊ \frac{m}{2} ⌋ + ⌊ \frac{n}{2} ⌋ \times ⌊ \frac{m + 1}{2} ⌋$ 。

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

go

func flowerGame(n int, m int) int64 {
	a1, b1 := (n+1)/2, (m+1)/2
	a2, b2 := n/2, m/2
	return int64(a1*b2 + a2*b1)
}

方法二：数学（优化） · Go 实现

思考

方法一的交叉乘积按 $n, m$ 的奇偶展开后，四种情形均可写成 $⌊ n m / 2 ⌋$ 。

因此不必再分奇偶，一次整除乘法即可。

方法一得出的结果为 $⌊ \frac{n + 1}{2} ⌋ \times ⌊ \frac{m}{2} ⌋ + ⌊ \frac{n}{2} ⌋ \times ⌊ \frac{m + 1}{2} ⌋$ 。

如果 $n$ 和 $m$ 都是奇数，那么结果为 $\frac{n + 1}{2} \times \frac{m - 1}{2} + \frac{n - 1}{2} \times \frac{m + 1}{2}$ ，即 $\frac{n \times m - 1}{2}$ 。

如果 $n$ 和 $m$ 都是偶数，那么结果为 $\frac{n}{2} \times \frac{m}{2} + \frac{n}{2} \times \frac{m}{2}$ ，即 $\frac{n \times m}{2}$ 。

如果 $n$ 是奇数，且 $m$ 是偶数，那么结果为 $\frac{n + 1}{2} \times \frac{m}{2} + \frac{n - 1}{2} \times \frac{m}{2}$ ，即 $\frac{n \times m}{2}$ 。

如果 $n$ 是偶数，且 $m$ 是奇数，那么结果为 $\frac{n}{2} \times \frac{m - 1}{2} + \frac{n}{2} \times \frac{m + 1}{2}$ ，即 $\frac{n \times m}{2}$ 。

上面四种情况可以合并为 $⌊ \frac{n \times m}{2} ⌋$ 。

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

go

func flowerGame(n int, m int) int64 {
	return int64((n * m) / 2)
}

力扣原题 · Doocs 题解来源

3024. 三角形类型

简单1 种解法

标签：数组、数学、多边形、排序

题目、示例与约束

给你一个下标从 0 开始长度为 3 的整数数组 nums ，需要用它们来构造三角形。

如果一个三角形的所有边长度相等，那么这个三角形称为 equilateral 。
如果一个三角形恰好有两条边长度相等，那么这个三角形称为 isosceles 。
如果一个三角形三条边的长度互不相同，那么这个三角形称为 scalene 。

如果这个数组无法构成一个三角形，请你返回字符串 "none" ，否则返回一个字符串表示这个三角形的类型。

示例 1：

输入：nums = [3,3,3]
输出："equilateral"
解释：由于三条边长度相等，所以可以构成一个等边三角形，返回 "equilateral" 。

示例 2：

输入：nums = [3,4,5]
输出："scalene"
解释：
nums[0] + nums[1] = 3 + 4 = 7 ，大于 nums[2] = 5 。
nums[0] + nums[2] = 3 + 5 = 8 ，大于 nums[1] = 4 。
nums[1] + nums[2] = 4 + 5 = 9 ，大于 nums[0] = 3 。
由于任意两边之和都大于第三边，所以可以构成一个三角形，因为三条边的长度互不相等，所以返回 "scalene"。

提示：

nums.length == 3
1 <= nums[i] <= 100

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

思考

三边已给出且范围很小。先判定能否构成三角形，再区分等边、等腰与不等边。

排序后三角形不等式化为 $a + b > c$ ；等边即最小等于最大；等腰即相邻两边相等。

为此先排序再按上述顺序分支。

我们先对数组进行排序，然后根据三角形的定义进行分类讨论即可。

如果最小的两个数之和小于等于最大的数，那么无法构成三角形，返回 "none"。
如果最小的数等于最大的数，那么是等边三角形，返回 "equilateral"。
如果最小的数等于中间的数或者中间的数等于最大的数，那么是等腰三角形，返回 "isosceles"。
否则，返回 "scalene"。

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

go

func triangleType(nums []int) string {
	sort.Ints(nums)
	if nums[0]+nums[1] <= nums[2] {
		return "none"
	}
	if nums[0] == nums[2] {
		return "equilateral"
	}
	if nums[0] == nums[1] || nums[1] == nums[2] {
		return "isosceles"
	}
	return "scalene"
}

力扣原题 · Doocs 题解来源

3025. 人员站位的方案数 I

中等1 种解法

标签：几何、数组、数学、枚举、排序

题目、示例与约束

给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [x_i, y_i] 。

计算点对 (A, B) 的数量，其中

A 在 B 的左上角，并且
它们形成的长方形中（或直线上）没有其它点（包括边界），除了点 A 和点 B。

返回数量。

示例 1：

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

输出：0

解释：

没有办法选择 A 和 B，使得 A 在 B 的左上角。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]

输出：2

解释：

左边的是点对 (points[1], points[0])，其中 points[1] 在 points[0] 的左上角，并且形成的长方形内部是空的。
中间的是点对 (points[2], points[1])，和左边的一样是合法的点对。
右边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角，但 points[1] 在长方形内部，所以不是一个合法的点对。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]

输出：2

解释：

左边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角并且在它们形成的直线上没有其它点。注意两个点形成一条线的情况是合法的。
中间的是点对 (points[1], points[2])，和左边一样也是合法的点对。
右边的是点对 (points[1], points[0])，它不是合法的点对，因为 points[2] 在长方形的边上。

提示：

2 <= n <= 50
points[i].length == 2
0 <= points[i][0], points[i][1] <= 50
points[i] 点对两两不同。

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

思考

$n \leq 50$ ，枚举左上角与右下角后检查矩形内是否有其它点，最坏 $O (n^{3})$ 可过，但重复检查较多。

将点按 $x$ 升序、 $x$ 相同时按 $y$ 降序排列后，从左到右扫描时候选右下角的 $y$ 必须严格递增，否则会落入已形成的矩形内部。

为此对每个左上角维护已选用的最大 $y_{2}$ ，仅当 $maxY < y_{2} \leq y_{1}$ 时计一对并更新 $maxY$ 。

我们不妨考虑枚举矩形左上角的点 $(x_{1}, y_{1})$ ，那么根据题目，右下角的点 $(x_{2}, y_{2})$ 随着 $x$ 的增大，纵坐标 $y$ 也会要严格增大，才符合题意。

因此，我们对所有点按照 $x$ 坐标升序排序，如果 $x$ 坐标相同，按照 $y$ 坐标降序排序。

然后我们枚举左上角的点 $(x_{1}, y_{1})$ ，并且维护一个最大的 $y_{2}$ ，记为 $m a x Y$ ，表示所有右下角的点的纵坐标的最大值。然后我们枚举右下角的点 $(x_{2}, y_{2})$ ，如果 $y_{2}$ 大于 $m a x Y$ 并且小于等于 $y_{1}$ ，那么我们就找到了一个合法的方案，将答案加一，然后更新 $m a x Y$ 为 $y_{2}$ 。

枚举完所有的点对后，我们就得到了答案。

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

go

func numberOfPairs(points [][]int) (ans int) {
	sort.Slice(points, func(i, j int) bool {
		return points[i][0] < points[j][0] || points[i][0] == points[j][0] && points[j][1] < points[i][1]
	})
	for i, p1 := range points {
		y1 := p1[1]
		maxY := math.MinInt32
		for _, p2 := range points[i+1:] {
			y2 := p2[1]
			if maxY < y2 && y2 <= y1 {
				maxY = y2
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3027. 人员站位的方案数 II

困难1 种解法

标签：几何、数组、数学、枚举、排序

题目、示例与约束

给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [x_i, y_i] 。

我们定义 x 轴的正方向为右（x 轴递增的方向），x 轴的负方向为左（x 轴递减的方向）。类似的，我们定义 y 轴的正方向为上（y 轴递增的方向），y 轴的负方向为下（y 轴递减的方向）。

你需要安排这 n 个人的站位，这 n 个人中包括 Alice 和 Bob 。你需要确保每个点处恰好有一个人。同时，Alice 想跟 Bob 单独玩耍，所以 Alice 会以 Alice 的坐标为 左上角 ，Bob 的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能不包含任何区域，也就是说围栏可能是一条线段）。如果围栏的内部或者边缘上有任何其他人，Alice 都会难过。

请你在确保 Alice 不会难过的前提下，返回 Alice 和 Bob 可以选择的点对数目。

注意，Alice 建立的围栏必须确保 Alice 的位置是矩形的左上角，Bob 的位置是矩形的右下角。比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，给定下图的两个输入，Alice 都不能建立围栏，原因如下：

图一中，Alice 在 (3, 3) 且 Bob 在 (1, 1) ，Alice 的位置不是左上角且 Bob 的位置不是右下角。
图二中，Alice 在 (1, 3) 且 Bob 在 (1, 1)（如图所示，用矩形代替线条），Bob 的位置不是在围栏的右下角。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：0
解释：没有办法可以让 Alice 的围栏以 Alice 的位置为左上角且 Bob 的位置为右下角。所以我们返回 0 。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：
- Alice 站在 (4, 4) ，Bob 站在 (6, 2) 。
- Alice 站在 (2, 6) ，Bob 站在 (4, 4) 。
不能安排 Alice 站在 (2, 6) 且 Bob 站在 (6, 2) ，因为站在 (4, 4) 的人处于围栏内。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]
输出：2
解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：
- Alice 站在 (1, 1) ，Bob 站在 (3, 1) 。
- Alice 站在 (1, 3) ，Bob 站在 (1, 1) 。
不能安排 Alice 站在 (1, 3) 且 Bob 站在 (3, 1) ，因为站在 (1, 1) 的人处于围栏内。
注意围栏是可以不包含任何面积的，上图中第一和第二个围栏都是合法的。

提示：

2 <= n <= 1000
points[i].length == 2
-10⁹ <= points[i][0], points[i][1] <= 10⁹
points[i] 点对两两不同。

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

思考

题意与 I 相同，但 $n \leq 1000$ ，原先若采用 $O (n^{3})$ 检查矩形内部则会超时。

I 中「排序后 $y$ 严格递增」的观察与 $n$ 无关，枚举点对已是 $O (n^{2})$ ，恰好落在本约束可接受的范围内。

因此沿用同一排序与 $maxY$ 扫描，无需再检查矩形内部的其它点。

我们不妨考虑枚举矩形左上角的点 $(x_{1}, y_{1})$ ，那么根据题目，右下角的点 $(x_{2}, y_{2})$ 随着 $x$ 的增大，纵坐标 $y$ 也会要严格增大，才符合题意。

因此，我们对所有点按照 $x$ 坐标升序排序，如果 $x$ 坐标相同，按照 $y$ 坐标降序排序。

然后我们枚举左上角的点 $(x_{1}, y_{1})$ ，并且维护一个最大的 $y_{2}$ ，记为 $m a x Y$ ，表示所有右下角的点的纵坐标的最大值。然后我们枚举右下角的点 $(x_{2}, y_{2})$ ，如果 $y_{2}$ 大于 $m a x Y$ 并且小于等于 $y_{1}$ ，那么我们就找到了一个合法的方案，将答案加一，然后更新 $m a x Y$ 为 $y_{2}$ 。

枚举完所有的点对后，我们就得到了答案。

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

go

func numberOfPairs(points [][]int) (ans int) {
	sort.Slice(points, func(i, j int) bool {
		return points[i][0] < points[j][0] || points[i][0] == points[j][0] && points[j][1] < points[i][1]
	})
	for i, p1 := range points {
		y1 := p1[1]
		maxY := math.MinInt32
		for _, p2 := range points[i+1:] {
			y2 := p2[1]
			if maxY < y2 && y2 <= y1 {
				maxY = y2
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3044. 出现频率最高的质数

中等1 种解法

标签：数组、哈希表、数学、计数、枚举、矩阵、数论、素性测试、筛法、素数筛法

题目、示例与约束

给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字：

最多有 8 条路径可以选择：东，东南，南，西南，西，西北，北，东北。
选择其中一条路径，沿着这个方向移动，并且将路径上的数字添加到正在形成的数字后面。
注意，每一步都会生成数字，例如，如果路径上的数字是 1, 9, 1，那么在这个方向上会生成三个数字：1, 19, 191 。

返回在遍历矩阵所创建的所有数字中，出现频率最高的、大于 10的质数；如果不存在这样的质数，则返回 -1 。如果存在多个出现频率最高的质数，那么返回其中最大的那个。

注意：移动过程中不允许改变方向。

示例 1：


输入：mat = [[1,1],[9,9],[1,1]]
输出：19
解释： 
从单元格 (0,0) 出发，有 3 个可能的方向，这些方向上可以生成的大于 10 的数字有：
东方向: [11], 东南方向: [19], 南方向: [19,191] 。
从单元格 (0,1) 出发，所有可能方向上生成的大于 10 的数字有：[19,191,19,11] 。
从单元格 (1,0) 出发，所有可能方向上生成的大于 10 的数字有：[99,91,91,91,91] 。
从单元格 (1,1) 出发，所有可能方向上生成的大于 10 的数字有：[91,91,99,91,91] 。
从单元格 (2,0) 出发，所有可能方向上生成的大于 10 的数字有：[11,19,191,19] 。
从单元格 (2,1) 出发，所有可能方向上生成的大于 10 的数字有：[11,19,19,191] 。
在所有生成的数字中，出现频率最高的质数是 19 。

示例 2：

输入：mat = [[7]]
输出：-1
解释：唯一可以生成的数字是 7 。它是一个质数，但不大于 10 ，所以返回 -1 。

示例 3：

输入：mat = [[9,7,8],[4,6,5],[2,8,6]]
输出：97
解释： 
从单元格 (0,0) 出发，所有可能方向上生成的大于 10 的数字有: [97,978,96,966,94,942] 。
从单元格 (0,1) 出发，所有可能方向上生成的大于 10 的数字有: [78,75,76,768,74,79] 。
从单元格 (0,2) 出发，所有可能方向上生成的大于 10 的数字有: [85,856,86,862,87,879] 。
从单元格 (1,0) 出发，所有可能方向上生成的大于 10 的数字有: [46,465,48,42,49,47] 。
从单元格 (1,1) 出发，所有可能方向上生成的大于 10 的数字有: [65,66,68,62,64,69,67,68] 。
从单元格 (1,2) 出发，所有可能方向上生成的大于 10 的数字有: [56,58,56,564,57,58] 。
从单元格 (2,0) 出发，所有可能方向上生成的大于 10 的数字有: [28,286,24,249,26,268] 。
从单元格 (2,1) 出发，所有可能方向上生成的大于 10 的数字有: [86,82,84,86,867,85] 。
从单元格 (2,2) 出发，所有可能方向上生成的大于 10 的数字有: [68,682,66,669,65,658] 。
在所有生成的数字中，出现频率最高的质数是 97 。

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 6
1 <= mat[i][j] <= 9

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

思考

矩阵至多 $6 \times 6$ ，从每格沿 $8$ 个方向拼出的数个数很少。需要其中大于 $10$ 的质数的众数，并列时取较大者。

方向与步数均可枚举，对每个拼出的数做试除判定素性并计数。

最后扫描计数表，按频次、数值选取答案；若没有质数则返回 $- 1$ 。

我们可以使用哈希表来统计每个大于 10 的素数出现的次数。

对于每个单元格，我们可以从它出发，沿着 8 个方向之一生成数字，然后判断生成的数字是否是大于 $10$ 的素数，如果是的话，就将它加入到哈希表中。

最后，我们遍历哈希表，找到出现频率最高的质数，如果有多个出现频率最高的质数，那么返回其中最大的那个。

时间复杂度 $O (m \times n \times max (m, n) \times 10^{\frac{max (m, n)}{2}})$ ，空间复杂度 $O (m \times n \times max (m, n))$ 。其中 $m$ 和 $n$ 分别是 mat 的行数和列数。

go

func mostFrequentPrime(mat [][]int) int {
	m, n := len(mat), len(mat[0])
	cnt := make(map[int]int)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			for a := -1; a <= 1; a++ {
				for b := -1; b <= 1; b++ {
					if a == 0 && b == 0 {
						continue
					}
					x, y, v := i+a, j+b, mat[i][j]
					for x >= 0 && x < m && y >= 0 && y < n {
						v = v*10 + mat[x][y]
						if isPrime(v) {
							cnt[v]++
						}
						x += a
						y += b
					}
				}
			}
		}
	}
	ans, mx := -1, 0
	for v, x := range cnt {
		if mx < x || (mx == x && ans < v) {
			mx = x
			ans = v
		}
	}
	return ans
}

func isPrime(n int) bool {
	for i := 2; i <= n/i; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

3047. 求交集区域内的最大正方形面积

中等1 种解法

标签：几何、数组、数学

题目、示例与约束

在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight，两个数组的大小都是 n x 2 ，其中 bottomLeft[i] 和 topRight[i] 分别代表第 i 个矩形的 左下角 和 右上角 坐标。

我们定义向右的方向为 x 轴正半轴（x 坐标增加），向左的方向为 x 轴负半轴（x 坐标减少）。同样地，定义向上的方向为 y 轴正半轴（y 坐标增加），向下 的方向为 y 轴负半轴（y 坐标减少）。

你可以选择一个区域，该区域由两个矩形的交集形成。你需要找出能够放入该区域内的最大正方形面积，并选择最优解。

返回能够放入交集区域的正方形的最大可能面积，如果矩形之间不存在任何交集区域，则返回 0。

示例 1：

输入：bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1 的交集区域，或矩形 1 和矩形 2 的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。

示例 2：

输入：bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1，矩形 1 和矩形 2，或所有三个矩形的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。
请注意，区域可以由多于两个矩形的交集构成。

示例 3：

输入：bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]
输出：0
解释：不存在相交的矩形，因此，返回 0 。

提示：

n == bottomLeft.length == topRight.length
2 <= n <= 10³
bottomLeft[i].length == topRight[i].length == 2
1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10⁷
1 <= topRight[i][0], topRight[i][1] <= 10⁷
bottomLeft[i][0] < topRight[i][0]
bottomLeft[i][1] < topRight[i][1]

方法一：枚举 · Go 实现

思考

$n \leq 10^{3}$ 个矩形，正方形必须完全落在某两个矩形的交集内。边长受交集宽高的较小者限制。

两矩形交集的宽高可 $O (1)$ 算出，枚举所有矩形对并取 $min (w, h)^{2}$ 的最大值即可。

无正面积交集时贡献为 $0$ 。

我们可以枚举两个矩形，其中矩形 $1$ 的左下角和右上角坐标分别为 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$ ，矩形 $2$ 的左下角和右上角坐标分别为 $(x_{3}, y_{3})$ 和 $(x_{4}, y_{4})$ 。

如果矩形 $1$ 和矩形 $2$ 有交集，那么交集的坐标分别为：

左下角横坐标是两个矩形左下角横坐标的最大值，即 $max (x_{1}, x_{3})$ ；
左下角纵坐标是两个矩形左下角纵坐标的最大值，即 $max (y_{1}, y_{3})$ ；
右上角横坐标是两个矩形右上角横坐标的最小值，即 $min (x_{2}, x_{4})$ ；
右上角纵坐标是两个矩形右上角纵坐标的最小值，即 $min (y_{2}, y_{4})$ 。

那么交集的宽和高分别为 $w = min (x_{2}, x_{4}) - max (x_{1}, x_{3})$ 和 $h = min (y_{2}, y_{4}) - max (y_{1}, y_{3})$ 。我们取两者的最小值作为边长，即 $e = min (w, h)$ ，如果 $e > 0$ ，那么我们就可以得到一个正方形，其面积为 $e^{2}$ ，我们取所有正方形的最大面积即可。

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

go

func largestSquareArea(bottomLeft [][]int, topRight [][]int) (ans int64) {
	for i, b1 := range bottomLeft {
		t1 := topRight[i]
		x1, y1 := b1[0], b1[1]
		x2, y2 := t1[0], t1[1]
		for j := i + 1; j < len(bottomLeft); j++ {
			x3, y3 := bottomLeft[j][0], bottomLeft[j][1]
			x4, y4 := topRight[j][0], topRight[j][1]
			w := min(x2, x4) - max(x1, x3)
			h := min(y2, y4) - max(y1, y3)
			e := min(w, h)
			if e > 0 {
				ans = max(ans, int64(e)*int64(e))
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3079. 求出加密整数的和

简单1 种解法

标签：数组、数学

题目、示例与约束

给你一个整数数组 nums ，数组中的元素都是正整数。定义一个加密函数 encrypt ，encrypt(x) 将一个整数 x 中 每一个 数位都用 x 中的最大数位替换。比方说 encrypt(523) = 555 且 encrypt(213) = 333 。

请你返回数组中所有元素加密后的和。

示例 1：

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

输出：6

解释：加密后的元素位 [1,2,3] 。加密元素的和为 1 + 2 + 3 == 6 。

示例 2：

输入：nums = [10,21,31]

输出：66

解释：加密后的元素为 [11,22,33] 。加密元素的和为 11 + 22 + 33 == 66 。

提示：

1 <= nums.length <= 50
1 <= nums[i] <= 1000

方法一：模拟 · Go 实现

思考

加密是把每个数的所有数位换成其中的最大数位。 $n \leq 50$ 、 $x \leq 1000$ ，对每个数模拟即可。

一边取模得到各位并维护最大值，一边用 $p = 1, 11, 111, \dots$ 记录位数，加密结果为 $m x \cdot p$ 。

对数组求和即答案。

我们直接模拟加密的过程，定义一个函数 $e n c r y p t (x)$ ，将一个整数 $x$ 中每一个数位都用 $x$ 中的最大数位替换。函数的实现如下：

我们可以通过不断地对 $x$ 取模和整除 $10$ 来得到 $x$ 的每一位数，找到最大的数位，记为 $m x$ 。在循环的过程中，我们还可以用一个变量 $p$ 来记录 $m x$ 的基础底数，即 $p = 1, 11, 111, \dots$ 。最后返回 $m x \times p$ 即可。

时间复杂度 $O (n \times \log M)$ ，其中 $n$ 是数组的长度，而 $M$ 是数组中元素的最大值。空间复杂度 $O (1)$ 。

go

func sumOfEncryptedInt(nums []int) (ans int) {
	encrypt := func(x int) int {
		mx, p := 0, 0
		for ; x > 0; x /= 10 {
			mx = max(mx, x%10)
			p = p*10 + 1
		}
		return mx * p
	}
	for _, x := range nums {
		ans += encrypt(x)
	}
	return
}

力扣原题 · Doocs 题解来源

3084. 统计以给定字符开头和结尾的子字符串总数

中等1 种解法

标签：数学、字符串、计数

题目、示例与约束

给你一个字符串 s 和一个字符 c 。返回在字符串 s 中并且以 c 字符开头和结尾的非空子字符串的总数。

示例 1：

输入：s = "abada", c = "a"

输出：6

解释：以 "a" 开头和结尾的子字符串有： "abada"、"abada"、"abada"、"abada"、"abada"、"abada"。

示例 2：

输入：s = "zzz", c = "z"

输出：6

解释：字符串 s 中总共有 6 个子字符串，并且它们都以 "z" 开头和结尾。

提示：

1 <= s.length <= 10⁵
s 和 c 均由小写英文字母组成。

方法一：数学 · Go 实现

思考

子串须以同一给定字符起止。 $n \leq 10^{5}$ ，不能枚举两端。

每个 $c$ 都可作左端或右端：单独一个 $c$ 是合法子串，任意两个 $c$ 又确定唯一一段。

若 $c$ 出现 $cnt$ 次，答案为 $cnt + cnt (cnt - 1) / 2$ 。

我们可以先统计字符串 $s$ 中字符 $c$ 的个数，记为 $c n t$ 。

每个 $c$ 字符可以单独作为一个子字符串，所以有 $c n t$ 个子字符串满足条件。每个 $c$ 字符可以和其他 $c$ 字符组成一个满足条件的子字符串，所以有 $\frac{c n t \times (c n t - 1)}{2}$ 个子字符串满足条件。

所以答案为 $c n t + \frac{c n t \times (c n t - 1)}{2}$ 。

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

go

func countSubstrings(s string, c byte) int64 {
	cnt := int64(strings.Count(s, string(c)))
	return cnt + cnt*(cnt-1)/2
}

力扣原题 · Doocs 题解来源

3099. 哈沙德数

简单1 种解法

标签：数学

题目、示例与约束

如果一个整数能够被其各个数位上的数字之和整除，则称之为 哈沙德数（Harshad number）。给你一个整数 x 。如果 x 是 哈沙德数 ，则返回 x 各个数位上的数字之和，否则，返回 -1 。

示例 1：

输入： x = 18

输出： 9

解释：

x 各个数位上的数字之和为 9 。18 能被 9 整除。因此 18 是哈沙德数，答案是 9 。

示例 2：

输入： x = 23

输出： -1

解释：

x 各个数位上的数字之和为 5 。23 不能被 5 整除。因此 23 不是哈沙德数，答案是 -1 。

提示：

1 <= x <= 100

方法一：模拟 · Go 实现

思考

判断 $x$ 是否能被其数位和整除，是则返回该数位和。 $x \leq 100$ ，模拟取模即可。

用临时变量累加各位，再做一次整除判断，避免破坏原值。

我们可以通过模拟的方法，计算出 $x$ 的各个数位上的数字之和，记为 $s$ 。如果 $x$ 能被 $s$ 整除，则返回 $s$ ，否则返回 $- 1$ 。

时间复杂度 $O (\log x)$ ，其中 $x$ 是输入的整数。空间复杂度 $O (1)$ 。

go

func sumOfTheDigitsOfHarshadNumber(x int) int {
	s := 0
	for y := x; y > 0; y /= 10 {
		s += y % 10
	}
	if x%s == 0 {
		return s
	}
	return -1
}

力扣原题 · Doocs 题解来源

3100. 换水问题 II

中等1 种解法

标签：数学、模拟

题目、示例与约束

给你两个整数 numBottles 和 numExchange 。

numBottles 代表你最初拥有的满水瓶数量。在一次操作中，你可以执行以下操作之一：

喝掉任意数量的满水瓶，使它们变成空水瓶。
用 numExchange 个空水瓶交换一个满水瓶。然后，将 numExchange 的值增加 1 。

注意，你不能使用相同的 numExchange 值交换多批空水瓶。例如，如果 numBottles == 3 并且 numExchange == 1 ，则不能用 3 个空水瓶交换成 3 个满水瓶。

返回你最多可以喝到多少瓶水。

示例 1：

输入：numBottles = 13, numExchange = 6
输出：15
解释：上表显示了满水瓶的数量、空水瓶的数量、numExchange 的值，以及累计喝掉的水瓶数量。

示例 2：

输入：numBottles = 10, numExchange = 3
输出：13
解释：上表显示了满水瓶的数量、空水瓶的数量、numExchange 的值，以及累计喝掉的水瓶数量。

提示：

1 <= numBottles <= 100
1 <= numExchange <= 100

方法一：模拟 · Go 实现

思考

兑换阈值每次成功后都会加一，若试图用闭式公式一次算出总瓶数，需处理空瓶与递增阈值之间的二次关系，推导并不轻松。 $n$ 与 $numExchange$ 至多为 $100$ ，按规则逐步兑换的循环次数与 $\sqrt{n}$ 同阶，足以在时限内完成。

注意到满瓶可先全部喝掉，此后能否继续只取决于当前空瓶数是否不少于阈值。每换一瓶便喝掉它，空瓶净减 $numExchange - 1$ ，阈值同时加一。

因此先把 $numBottles$ 计入答案，再在空瓶不少于当前阈值时减去阈值、阈值加一、答案与空瓶各加一。循环结束时的累计瓶数即为最多能喝到的数量。

我们可以在一开始就喝掉所有的满水瓶，因此初始时我们喝到的水数量为 $numBottles$ 。然后我们不断地进行以下操作：

如果当前有 $numExchange$ 个空水瓶，我们就可以用它们换一瓶满水瓶，换完后， $numExchange$ 的值增加 $1$ 。然后，我们喝掉这瓶水，喝到的水数量增加 $1$ ，空水瓶数量增加 $1$ 。
如果当前没有 $numExchange$ 个空水瓶，那么我们就不能再换水了，此时我们就可以停止操作。

我们不断地进行上述操作，直到我们无法再换水为止。最终我们喝到的水的数量就是答案。

时间复杂度 $O (\sqrt{n})$ ，其中 $n$ 是初始的满水瓶数量。空间复杂度 $O (1)$ 。

go

func maxBottlesDrunk(numBottles int, numExchange int) int {
	ans := numBottles
	for numBottles >= numExchange {
		numBottles -= numExchange
		numExchange++
		ans++
		numBottles++
	}
	return ans
}

力扣原题 · Doocs 题解来源

3101. 交替子数组计数

中等1 种解法

标签：数组、数学

题目、示例与约束

给你一个二进制数组 nums 。

如果一个子数组中 不存在 两个相邻元素的值相同的情况，我们称这样的子数组为 交替子数组 。

返回数组 nums 中交替子数组的数量。

示例 1：

输入： nums = [0,1,1,1]

输出： 5

解释：

以下子数组是交替子数组：[0] 、[1] 、[1] 、[1] 以及 [0,1] 。

示例 2：

输入： nums = [1,0,1,0]

输出： 10

解释：

数组的每个子数组都是交替子数组。可以统计在内的子数组共有 10 个。

提示：

1 <= nums.length <= 10⁵
nums[i] 不是 0 就是 1 。

方法一：枚举 · Go 实现

思考

交替子数组要求相邻元素互异。若枚举全部 $O (n^{2})$ 个区间再逐段检查，大量相邻比较会被重复执行。

以 $i$ 结尾的交替子数组，要么只含 $n u m s [i]$ ，要么在 $n u m s [i] \neq n u m s [i - 1]$ 时把以 $i - 1$ 结尾的段整体延长一位。相等则此前的交替段无法越过 $i$ 。

为此维护以当前位置结尾的交替长度 $s$ ，相邻不同则加一，否则重置为 $1$ ，并累加到答案。一遍扫描即可统计全部合法子数组。

我们可以枚举以每个位置结尾的子数组，计算满足条件的子数组的数量，累加所有位置的满足条件的子数组的数量即可。

具体地，我们定义变量 $s$ 表示以元素 $n u m s [i]$ 结尾的满足条件的子数组的数量，初始时我们将 $s$ 置为 $1$ ，表示以第一个元素结尾的满足条件的子数组的数量为 $1$ 。

接下来，我们从第二个元素开始遍历数组，对于每个位置 $i$ ，我们根据 $n u m s [i]$ 和 $n u m s [i - 1]$ 的关系更新 $s$ 的值：

如果 $n u m s [i] \neq n u m s [i - 1]$ ，则 $s$ 的值增加 $1$ ，即 $s = s + 1$ ；
如果 $n u m s [i] = n u m s [i - 1]$ ，则 $s$ 的值重置为 $1$ ，即 $s = 1$ 。

然后，我们将 $s$ 的值累加到答案中，继续遍历数组的下一个位置，直到遍历完整个数组。

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

go

func countAlternatingSubarrays(nums []int) int64 {
	ans, s := int64(1), int64(1)
	for i, x := range nums[1:] {
		if x != nums[i] {
			s++
		} else {
			s = 1
		}
		ans += s
	}
	return ans
}

力扣原题 · Doocs 题解来源

3102. 最小化曼哈顿距离

困难1 种解法

标签：几何、数组、数学、有序集合、排序

题目、示例与约束

给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [x_i, y_i] 。

两点之间的距离定义为它们的曼哈顿距离。

请你恰好移除一个点，返回移除后任意两点之间的最大距离可能的最小值。

示例 1：

输入：points = [[3,10],[5,15],[10,2],[4,4]]
输出：12
解释：移除每个点后的最大距离如下所示：
- 移除第 0 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间，为 |5 - 10| + |15 - 2| = 18 。
- 移除第 1 个点后，最大距离在点 (3, 10) 和 (10, 2) 之间，为 |3 - 10| + |10 - 2| = 15 。
- 移除第 2 个点后，最大距离在点 (5, 15) 和 (4, 4) 之间，为 |5 - 4| + |15 - 4| = 12 。
- 移除第 3 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间的，为 |5 - 10| + |15 - 2| = 18 。
在恰好移除一个点后，任意两点之间的最大距离可能的最小值是 12 。

示例 2：

输入：points = [[1,1],[1,1],[1,1]]
输出：0
解释：移除任一点后，任意两点之间的最大距离都是 0 。

提示：

3 <= points.length <= 10⁵
points[i].length == 2
1 <= points[i][0], points[i][1] <= 10⁸

方法一：有序集合 · Go 实现

思考

删除一个点后，剩余点对的最大曼哈顿距离需要重新计算。若对每个被删点再两两扫描，时间为 $O (n^{3})$ ，在 $n$ 达到数千时不可接受。

曼哈顿距离 $| x_{1} - x_{2} | + | y_{1} - y_{2} |$ 可改写成 $x + y$ 与 $x - y$ 两组坐标差的最大值。全集的最大距离因此只取决于这两套坐标的两端极值。

将全部 $x + y$ 与 $x - y$ 放入有序集合后，枚举每个点并暂时移除它，用两端极值更新答案再放回。每次删除与插入为对数时间，从而在 $O (n \log n)$ 内得到最优删除。

对于两个点 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$ ，它们的曼哈顿距离为 $| x_{1} - x_{2} | + | y_{1} - y_{2} |$ 。我们可以将其转化为 $max (x_{1} - x_{2}, x_{2} - x_{1}) + max (y_{1} - y_{2}, y_{2} - y_{1})$ ，即：

| x_{1} - x_{2} | + | y_{1} - y_{2} | = max {\begin{cases} x_{1} - x_{2} + y_{1} - y_{2} \\ x_{2} - x_{1} + y_{2} - y_{1} \\ x_{1} - x_{2} + y_{2} - y_{1} \\ x_{2} - x_{1} + y_{1} - y_{2} \end{cases}

整理可得：

| x_{1} - x_{2} | + | y_{1} - y_{2} | = max {\begin{cases} (x_{1} + y_{1}) - (x_{2} + y_{2}) \\ (x_{2} + y_{2}) - (x_{1} + y_{1}) \\ (x_{1} - y_{1}) - (x_{2} - y_{2}) \\ (x_{2} - y_{2}) - (x_{1} - y_{1}) \end{cases}

其中，前两项可以表示为 $max (max (x_{1} + y_{1}, x_{2} + y_{2}) - min (x_{1} + y_{1}, x_{2} + y_{2}))$ ，后两项可以表示为 $max (max (x_{1} - y_{1}, x_{2} - y_{2}) - min (x_{1} - y_{1}, x_{2} - y_{2}))$ 。

因此，我们可以将所有点按照 $x + y$ 和 $x - y$ 的值分别存入两个有序集合中，然后枚举每个点，移除该点后，更新有序集合中的值，计算最大值和最小值的差值，取最小值即可。

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

go

func minimumDistance(points [][]int) int {
	st1 := redblacktree.New[int, int]()
	st2 := redblacktree.New[int, int]()
	merge := func(st *redblacktree.Tree[int, int], x, v int) {
		c, _ := st.Get(x)
		if c+v == 0 {
			st.Remove(x)
		} else {
			st.Put(x, c+v)
		}
	}
	for _, p := range points {
		x, y := p[0], p[1]
		merge(st1, x+y, 1)
		merge(st2, x-y, 1)
	}
	ans := math.MaxInt
	for _, p := range points {
		x, y := p[0], p[1]
		merge(st1, x+y, -1)
		merge(st2, x-y, -1)
		ans = min(ans, max(st1.Right().Key-st1.Left().Key, st2.Right().Key-st2.Left().Key))
		merge(st1, x+y, 1)
		merge(st2, x-y, 1)
	}
	return ans
}

力扣原题 · Doocs 题解来源

3115. 质数的最大距离

中等1 种解法

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

题目、示例与约束

给你一个整数数组 nums。

返回两个（不一定不同的）质数在 nums 中下标的 最大距离。

示例 1：

输入： nums = [4,2,9,5,3]

输出： 3

解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

示例 2：

输入： nums = [4,8,2,8]

输出： 0

解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

提示：

1 <= nums.length <= 3 * 10⁵
1 <= nums[i] <= 100
输入保证 nums 中至少有一个质数。

方法一：遍历 · Go 实现

思考

所求为最左质数与最右质数的下标差。若对每个质数对都计算距离，只是在重复取两端。

质数判定对单个值至多 $O (\sqrt{M})$ ，数组长度与值域都不大，找到两端即可。

因此从左找第一个质数下标 $i$ ，再从右找最后一个质数下标 $j$ ，返回 $j - i$ 。中间元素不必参与距离计算。

根据题目描述，我们需要找出第一个质数所在的下标 $i$ ，然后找出最后一个质数所在的下标 $j$ ，将 $j - i$ 作为答案返回即可。

因此，我们可以从左到右遍历数组，找到第一个质数所在的下标 $i$ ，然后从右到左遍历数组，找到最后一个质数所在的下标 $j$ ，答案即为 $j - i$ 。

时间复杂度 $O (n \times \sqrt{M})$ ，其中 $n$ 和 $M$ 分别是数组 $n u m s$ 的长度和数组中的最大值。空间复杂度 $O (1)$ 。

go

func maximumPrimeDifference(nums []int) int {
	for i := 0; ; i++ {
		if isPrime(nums[i]) {
			for j := len(nums) - 1; ; j-- {
				if isPrime(nums[j]) {
					return j - i
				}
			}
		}
	}
}

func isPrime(n int) bool {
	if n < 2 {
		return false
	}
	for i := 2; i <= n/i; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

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

2748. 美丽下标对的数目 ​

2761. 和等于目标值的质数对 ​

2769. 找出最大的可达成数字 ​

2806. 取整购买后的账户余额 ​

2843. 统计对称整数的数目 ​

2849. 判断能否在给定时间到达单元格 ​

2862. 完全子集的最大元素和 ​

2894. 分类求和并作差 ​

2927. 给小朋友们分糖果 III 🔒 ​

2928. 给小朋友们分糖果 I ​

2929. 给小朋友们分糖果 II ​

2946. 循环移位后的矩阵相似检查 ​

2954. 统计感冒序列的数目 ​

2961. 双模幂运算 ​

2963. 统计好分割方案的数目 ​

2965. 找出缺失和重复的数字 ​

3001. 捕获黑皇后需要的最少移动次数 ​

3021. Alice 和 Bob 玩鲜花游戏 ​

3024. 三角形类型 ​

3025. 人员站位的方案数 I ​

3027. 人员站位的方案数 II ​

3044. 出现频率最高的质数 ​

3047. 求交集区域内的最大正方形面积 ​

3079. 求出加密整数的和 ​

3084. 统计以给定字符开头和结尾的子字符串总数 ​

3099. 哈沙德数 ​

3100. 换水问题 II ​

3101. 交替子数组计数 ​

3102. 最小化曼哈顿距离 ​

3115. 质数的最大距离 ​

继续阅读

LeetCode Go · 数学与几何（8）

2748. 美丽下标对的数目

2761. 和等于目标值的质数对

2769. 找出最大的可达成数字

2806. 取整购买后的账户余额

2843. 统计对称整数的数目

2849. 判断能否在给定时间到达单元格

2862. 完全子集的最大元素和

2894. 分类求和并作差

2927. 给小朋友们分糖果 III 🔒

2928. 给小朋友们分糖果 I

2929. 给小朋友们分糖果 II

2946. 循环移位后的矩阵相似检查

2954. 统计感冒序列的数目

2961. 双模幂运算

2963. 统计好分割方案的数目

2965. 找出缺失和重复的数字

3001. 捕获黑皇后需要的最少移动次数

3021. Alice 和 Bob 玩鲜花游戏

3024. 三角形类型

3025. 人员站位的方案数 I

3027. 人员站位的方案数 II

3044. 出现频率最高的质数

3047. 求交集区域内的最大正方形面积

3079. 求出加密整数的和

3084. 统计以给定字符开头和结尾的子字符串总数

3099. 哈沙德数

3100. 换水问题 II

3101. 交替子数组计数

3102. 最小化曼哈顿距离

3115. 质数的最大距离