LeetCode Go · 数学与几何（7）

来源与许可

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

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

2447. 最大公因数等于 K 的子数组数目

中等1 种解法

标签：数组、数学、数论

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。

示例 1：

输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

示例 2：

输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。

提示：

1 <= nums.length <= 1000
1 <= nums[i], k <= 10⁹

方法一：直接枚举 · Go 实现

思考

$n \leq 10^{3}$ ，枚举左端 $i$ 并向右延伸，维护当前 GCD。GCD 单调不增且很快降到约数，双重循环加 $g c d$ 可过。每当 $g = k$ 则计一。

我们可以枚举 $n u m s [i]$ 作为子数组的左端点，然后枚举 $n u m s [j]$ 作为子数组的右端点，其中 $i \leq j$ 。在枚举右端点的过程中，我们可以用一个变量 $g$ 来维护当前子数组的最大公因数，每次枚举到一个新的右端点时，我们更新最大公因数 $g = gcd (g, n u m s [j])$ 。如果 $g = k$ ，那么当前子数组的最大公因数等于 $k$ ，我们就将答案增加 $1$ 。

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

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

func subarrayGCD(nums []int, k int) (ans int) {
	for i := range nums {
		g := 0
		for _, x := range nums[i:] {
			g = gcd(g, x)
			if g == k {
				ans++
			}
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

2450. 应用操作后不同二进制字符串的数量 🔒

中等1 种解法

标签：数学、字符串

题目、示例与约束

给定一个 二进制 字符串 s 和一个正整数 k。

你可以对字符串应用以下操作任意次数:

从 s 中选择任何大小为 k 的子字符串，将其所有字符翻转，即将所有 1 都变成 0，所有 0 都变成 1。

返回您可以获得的不同字符串的数量。因为答案可能太大，所以对 10⁹ + 7 取模后返回。

注意:

二进制字符串是仅由字符 0 和 1 组成的字符串。
子字符串是字符串的连续部分。

示例 1:

输入: s = "1001", k = 3
输出: 4
解释: 我们可以获得以下字符串:
- 对字符串不应用任何操作将得到 s = "1001"。
- 对从下标 0 开始的子字符串应用一个操作，得到 s = "0111"。
- 对从下标 1 开始的子字符串应用一个操作，得到 s = "1110"。
- 对从下标 0 和 1 开始的两个子字符串都应用一个操作，得到 s = "0000"。
可以证明，我们不能获得任何其他字符串，所以答案是 4。

示例 2:

输入: s = "10110", k = 5
输出: 2
解释: 我们可以获得以下字符串:
- 对字符串不执行任何操作，将得到 s = "10110"。
- 对整个字符串应用一个操作将得到 s = "01001"。
可以证明，我们不能获得任何其他字符串，所以答案是 2。

提示:

1 <= k <= s.length <= 10⁵
s[i] 是 0 或 1。

方法一：数学 · Go 实现

思考

长度为 $k$ 的窗口翻转 $0 / 1$ 互不影响最终可区分的串，每个窗口有选或不选两种。长度为 $n$ 时这样的窗口有 $n - k + 1$ 个，且不同翻转集合给出不同串，故答案为 $2^{n - k + 1}$ 取模。

假设字符串 $s$ 长度为 $n$ ，那么长度为 $k$ 的子串共有 $n - k + 1$ 个，每个子串都可以翻转，因此共有 $2^{n - k + 1}$ 种翻转方式。

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

func countDistinctStrings(s string, k int) int {
	const mod int = 1e9 + 7
	ans := 1
	for i := 0; i < len(s)-k+1; i++ {
		ans = (ans * 2) % mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

2455. 可被三整除的偶数的平均值

简单1 种解法

标签：数组、数学

题目、示例与约束

给你一个由正整数组成的整数数组 nums ，返回其中可被 3 整除的所有偶数的平均值。

注意：n 个元素的平均值等于 n 个元素求和再除以 n ，结果 向下取整 到最接近的整数。

示例 1：

输入：nums = [1,3,6,10,12,15]
输出：9
解释：6 和 12 是可以被 3 整除的偶数。(6 + 12) / 2 = 9 。

示例 2：

输入：nums = [1,2,4,7,10]
输出：0
解释：不存在满足题目要求的整数，所以返回 0 。

提示：

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

方法一：模拟 · Go 实现

思考

$n \leq 1000$ ，同时为偶数且整除 $3$ 即整除 $6$ 。累加这些数的和与个数，个数为 $0$ 则返回 $0$ ，否则整除平均。

我们注意到，可被 $3$ 整除的偶数一定是 $6$ 的倍数，因此我们只需要遍历数组，统计所有 $6$ 的倍数的和与个数，然后计算平均值即可。

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

func averageValue(nums []int) int {
	var s, n int
	for _, x := range nums {
		if x%6 == 0 {
			s += x
			n++
		}
	}
	if n == 0 {
		return 0
	}
	return s / n
}

力扣原题 · Doocs 题解来源

2469. 温度转换

简单1 种解法

标签：数学

题目、示例与约束

给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度，以 摄氏度（Celsius）为单位。

你需要将摄氏度转换为 开氏度（Kelvin）和 华氏度（Fahrenheit），并以数组 ans = [kelvin, fahrenheit] 的形式返回结果。

返回数组 ans 。与实际答案误差不超过 10^-5 的会视为正确答案。

注意：

开氏度 = 摄氏度 + 273.15
华氏度 = 摄氏度 * 1.80 + 32.00

示例 1 ：

输入：celsius = 36.50
输出：[309.65000,97.70000]
解释：36.50 摄氏度：转换为开氏度是 309.65 ，转换为华氏度是 97.70 。

示例 2 ：

输入：celsius = 122.11
输出：[395.26000,251.79800]
解释：122.11 摄氏度：转换为开氏度是 395.26 ，转换为华氏度是 251.798 。

提示：

0 <= celsius <= 1000

方法一：模拟 · Go 实现

思考

开氏与华氏都是摄氏的仿射变换，按公式各算一次即可。

直接根据题意模拟即可。

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

func convertTemperature(celsius float64) []float64 {
	return []float64{celsius + 273.15, celsius*1.8 + 32}
}

力扣原题 · Doocs 题解来源

2470. 最小公倍数等于 K 的子数组数目

中等1 种解法

标签：数组、数学、数论

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的最小公倍数 是可被所有数组元素整除的最小正整数。

示例 1 ：

输入：nums = [3,6,2,7,1], k = 6
输出：4
解释：以 6 为最小公倍数的子数组是：
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]

示例 2 ：

输入：nums = [3], k = 2
输出：0
解释：不存在以 2 为最小公倍数的子数组。

提示：

1 <= nums.length <= 1000
1 <= nums[i], k <= 1000

方法一：枚举 · Go 实现

思考

$n \leq 1000$ ，可以从每个左端点向右扫描。某个元素不能整除 $k$ 时，包含它的连续段的最小公倍数也不可能是 $k$ ，因此立刻停止。停止之前，运行中的最小公倍数始终整除 $k$ ，从而不超过 $k$ 。若先把两数相乘再除以最大公约数， $a \times b$ 会在真正的最小公倍数仍不超过 $2^{31} - 1$ 时溢出，把本不是 $k$ 的段误判为答案。

枚举每个下标作为左端点并向右延伸。遇到不能整除 $k$ 的元素就停止。延伸过程中运行的最小公倍数始终整除 $k$ ，等于 $k$ 时答案加一。

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

func subarrayLCM(nums []int, k int) (ans int) {
	for i := range nums {
		a := 1
		for _, b := range nums[i:] {
			if k%b != 0 {
				break
			}
			a = lcm(a, b)
			if a == k {
				ans++
			}
		}
	}
	return
}

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

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

力扣原题 · Doocs 题解来源

2481. 分割圆的最少切割次数

简单1 种解法

标签：几何、数学

题目、示例与约束

圆内一个 有效切割 ，符合以下二者之一：

该切割是两个端点在圆上的线段，且该线段经过圆心。
该切割是一端在圆心另一端在圆上的线段。

一些有效和无效的切割如下图所示。

给你一个整数 n ，请你返回将圆切割成相等的 n 等分的最少切割次数。

示例 1：

输入：n = 4
输出：2
解释：
上图展示了切割圆 2 次，得到四等分。

示例 2：

输入：n = 3
输出：3
解释：
最少需要切割 3 次，将圆切成三等分。
少于 3 次切割无法将圆切成大小相等面积相同的 3 等分。
同时可以观察到，第一次切割无法将圆切割开。

提示：

1 <= n <= 100

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

思考

一刀是一条过圆心的直径方向。一块扇形不需要切割； $n$ 为奇数时没有两条半径共线，需要 $n$ 刀； $n$ 为偶数时可两两共线，只需 $n / 2$ 刀。按奇偶分类即可。

当 $n = 1$ 时，不需要切割，即切割次数为 $0$ ；
当 $n$ 为奇数时，不存在共线的情况，最少需要 $n$ 次切割；
当 $n$ 为偶数时，可以两两共线，最少需要 $\frac{n}{2}$ 次切割。

综上，可以得到：

ans = {\begin{cases} n, & n > 1 且 n 为奇数 \\ \frac{n}{2}, & n 为其它 \end{cases}

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

func numberOfCuts(n int) int {
	if n > 1 && n%2 == 1 {
		return n
	}
	return n >> 1
}

力扣原题 · Doocs 题解来源

2507. 使用质因数之和替换后可以取到的最小值

中等1 种解法

标签：数学、数论、素性测试、筛法、模拟、素数筛法、质因数分解

题目、示例与约束

给你一个正整数 n 。

请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。

注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。

返回 n 可以取到的最小值。

示例 1：

输入：n = 15
输出：5
解释：最开始，n = 15 。
15 = 3 * 5 ，所以 n 替换为 3 + 5 = 8 。
8 = 2 * 2 * 2 ，所以 n 替换为 2 + 2 + 2 = 6 。
6 = 2 * 3 ，所以 n 替换为 2 + 3 = 5 。
5 是 n 可以取到的最小值。

示例 2：

输入：n = 3
输出：3
解释：最开始，n = 3 。
3 是 n 可以取到的最小值。

提示：

2 <= n <= 10⁵

方法一：暴力模拟 · Go 实现

思考

每次把 $n$ 替换为其全部质因数之和，直至不再变化。 $n \leq 10^{5}$ ，直接模拟即可；质因数之和在 $n$ 合数时严格变小，素数时等于自身，故过程必然终止。

对当前值做试除分解并累加因子，若和等于原值则已到达不动点，否则继续。单次分解 $O (\sqrt{n})$ ，迭代次数很少。

根据题意，我们可以得到一个质因数分解的过程，即将一个数不断地分解为质因数，分解不能分解。过程中将每次分解的质因数相加，递归或者迭代地进行即可。

时间复杂度 $O (\sqrt{n})$ 。

func smallestValue(n int) int {
	for {
		t, s := n, 0
		for i := 2; i <= n/i; i++ {
			for n%i == 0 {
				s += i
				n /= i
			}
		}
		if n > 1 {
			s += n
		}
		if s == t {
			return s
		}
		n = s
	}
}

力扣原题 · Doocs 题解来源

2514. 统计同位异构字符串数目

困难1 种解法

标签：哈希表、数学、字符串、组合数学、计数、费马小定理

题目、示例与约束

给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。

如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个排列，那么我们称字符串 t 是字符串 s 的同位异构字符串。

比方说，"acb dfe" 是 "abc def" 的同位异构字符串，但是 "def cab" 和 "adc bef" 不是。

请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 10⁹ + 7 取余后返回。

示例 1：

输入：s = "too hot"
输出：18
解释：输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。

示例 2：

输入：s = "aa"
输出：1
解释：输入字符串只有一个同位异构字符串。

提示：

1 <= s.length <= 10⁵
s 只包含小写英文字母和空格 ' ' 。
相邻单词之间由单个空格隔开。

方法一 · Go 实现

思考

原串按空格分成若干单词，答案是各单词变位词个数的乘积，对 $10^{9} + 7$ 取模。单词长度之和达 $10^{5}$ ，不能对每个单词枚举排列。

单词 $w$ 的变位词数为 $| w |! / \prod (c_{i}!)$ ，其中 $c_{i}$ 为各字母出现次数。从左到右扫描时， $ans$ 累乘当前位置下标（即阶乘）， $mul$ 累乘当前字母已出现次数（即分母）。最后乘 $mul$ 的模逆元即可一次算完所有单词。

const mod int = 1e9 + 7

func countAnagrams(s string) int {
	ans, mul := 1, 1
	for _, w := range strings.Split(s, " ") {
		cnt := [26]int{}
		for i, c := range w {
			i++
			cnt[c-'a']++
			ans = ans * i % mod
			mul = mul * cnt[c-'a'] % mod
		}
	}
	return ans * pow(mul, mod-2) % mod
}

func pow(x, n int) int {
	res := 1
	for ; n > 0; n >>= 1 {
		if n&1 > 0 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}

力扣原题 · Doocs 题解来源

2520. 统计能整除数字的位数

简单1 种解法

标签：数学

题目、示例与约束

给你一个整数 num ，返回 num 中能整除 num 的数位的数目。

如果满足 nums % val == 0 ，则认为整数 val 可以整除 nums 。

示例 1：

输入：num = 7
输出：1
解释：7 被自己整除，因此答案是 1 。

示例 2：

输入：num = 121
输出：2
解释：121 可以被 1 整除，但无法被 2 整除。由于 1 出现两次，所以返回 2 。

示例 3：

输入：num = 1248
输出：4
解释：1248 可以被它每一位上的数字整除，因此答案是 4 。

提示：

1 <= num <= 10⁹
num 的数位中不含 0

方法一：枚举 · Go 实现

思考

统计 $n u m$ 中能整除自身的数位个数。 $n u m$ 至多十位，枚举每一位即可。

用除十取余依次取出数位 $v a l$ ，判断 $n u m mod v a l = 0$ 。题目保证不含 $0$ ，故无需处理除零。

我们直接枚举整数 $n u m$ 的每一位上的数 $v a l$ ，若 $v a l$ 能够整除 $n u m$ ，那么答案加一。

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

时间复杂度 $O (\log n u m)$ ，空间复杂度 $O (1)$ 。

func countDigits(num int) (ans int) {
	for x := num; x > 0; x /= 10 {
		if num%(x%10) == 0 {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2521. 数组乘积中的不同质因数数目

中等1 种解法

标签：数组、哈希表、数学、最大公约数、数论、素性测试、筛法、素数筛法、质因数分解、欧几里得算法

题目、示例与约束

给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中 不同质因数 的数目。

注意：

质数是指大于 1 且仅能被 1 及自身整除的数字。
如果 val2 / val1 是一个整数，则整数 val1 是另一个整数 val2 的一个因数。

示例 1：

输入：nums = [2,4,3,7,10,6]
输出：4
解释：
nums 中所有元素的乘积是：2 * 4 * 3 * 7 * 10 * 6 = 10080 = 2⁵ * 3² * 5 * 7 。
共有 4 个不同的质因数，所以返回 4 。

示例 2：

输入：nums = [2,4,8,16]
输出：1
解释：
nums 中所有元素的乘积是：2 * 4 * 8 * 16 = 1024 = 2¹⁰ 。
共有 1 个不同的质因数，所以返回 1 。

提示：

1 <= nums.length <= 10⁴
2 <= nums[i] <= 1000

方法一：哈希表 + 质因数分解 · Go 实现

思考

所求是 $\prod n u m s [i]$ 的不同质因数个数。先算出乘积再分解， $m_{i} \leq 10^{3}$ 、 $n \leq 10^{4}$ 时乘积会溢出且无必要：乘积的质因数就是各元素质因数的并。

对每个 $n$ 试除分解，把因子放入集合，最后返回集合大小。单次分解 $O (\sqrt{m})$ 。

对于数组中的每个元素，先对其进行质因数分解，然后将分解出的质因数加入哈希表中。最后返回哈希表的大小即可。

时间复杂度 $O (n \times \sqrt{m})$ ，空间复杂度 $O (\frac{m}{\log m})$ ，其中 $n$ 和 $m$ 分别为数组的长度和数组中元素的最大值。

func distinctPrimeFactors(nums []int) int {
	s := map[int]bool{}
	for _, n := range nums {
		for i := 2; i <= n/i; i++ {
			if n%i == 0 {
				s[i] = true
				for n%i == 0 {
					n /= i
				}
			}
		}
		if n > 1 {
			s[n] = true
		}
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

2523. 范围内最接近的两个质数

中等1 种解法

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

题目、示例与约束

给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：

left <= nums1 < nums2 <= right 。
nums1 和 nums2 都是质数。
nums2 - nums1 是满足上述条件的质数对中的 最小值 。

请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。

示例 1：

输入：left = 10, right = 19
输出：[11,13]
解释：10 到 19 之间的质数为 11 ，13 ，17 和 19 。
质数对的最小差值是 2 ，[11,13] 和 [17,19] 都可以得到最小差值。
由于 11 比 17 小，我们返回第一个质数对。

示例 2：

输入：left = 4, right = 6
输出：[-1,-1]
解释：给定范围内只有一个质数，所以题目条件无法被满足。

提示：

1 <= left <= right <= 10⁶

方法一：线性筛 · Go 实现

思考

在 $[left, right]$ 中找差最小的相邻质数对。 $right \leq 10^{6}$ ，对区间内每个数单独判素会重复做试除。

线性筛一次求出 $[2, right]$ 的全部质数，再过滤落在区间内的部分，扫描相邻差并记录最小者。区间内质数不足两个则返回 $[- 1, - 1]$ 。

对于给定的范围 $[left, right]$ ，我们可以使用线性筛求出所有质数，然后从小到大遍历质数，找到相邻的两个质数，其差值最小的质数对即为答案。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n = right$ 。

func closestPrimes(left int, right int) []int {
	cnt := 0
	st := make([]bool, right+1)
	prime := make([]int, right+1)
	for i := 2; i <= right; i++ {
		if !st[i] {
			prime[cnt] = i
			cnt++
		}
		for j := 0; prime[j] <= right/i; j++ {
			st[prime[j]*i] = true
			if i%prime[j] == 0 {
				break
			}
		}
	}
	i, j := -1, -1
	for k := 0; k < cnt; k++ {
		if prime[k] >= left && prime[k] <= right {
			if i == -1 {
				i = k
			}
			j = k
		}
	}
	ans := []int{-1, -1}
	if i == j || i == -1 {
		return ans
	}
	mi := 1 << 30
	for k := i; k < j; k++ {
		d := prime[k+1] - prime[k]
		if d < mi {
			mi = d
			ans[0], ans[1] = prime[k], prime[k+1]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2525. 根据规则将箱子分类

简单2 种解法

标签：数学

题目、示例与约束

给你四个整数 length ，width ，height 和 mass ，分别表示一个箱子的三个维度和质量，请你返回一个表示箱子类别的字符串。

如果满足以下条件，那么箱子是 "Bulky" 的：
- 箱子 至少有一个 维度大于等于 10⁴ 。
- 或者箱子的体积大于等于 10⁹ 。
如果箱子的质量大于等于 100 ，那么箱子是 "Heavy" 的。
如果箱子同时是 "Bulky" 和 "Heavy" ，那么返回类别为 "Both" 。
如果箱子既不是 "Bulky" ，也不是 "Heavy" ，那么返回类别为 "Neither" 。
如果箱子是 "Bulky" 但不是 "Heavy" ，那么返回类别为 "Bulky" 。
如果箱子是 "Heavy" 但不是 "Bulky" ，那么返回类别为 "Heavy" 。

注意，箱子的体积等于箱子的长度、宽度和高度的乘积。

示例 1：

输入：length = 1000, width = 35, height = 700, mass = 300
输出："Heavy"
解释：
箱子没有任何维度大于等于 10⁴。
体积为 24500000 <= 10⁹。所以不能归类为 "Bulky" 。
但是质量 >= 100 ，所以箱子是 "Heavy" 的。
由于箱子不是 "Bulky" 但是是 "Heavy" ，所以我们返回 "Heavy" 。

示例 2：

输入：length = 200, width = 50, height = 800, mass = 50
输出："Neither"
解释：
箱子没有任何维度大于等于 10⁴ 。
体积为 8 * 10⁶ <= 10⁹ 。所以不能归类为 "Bulky" 。
质量小于 100 ，所以不能归类为 "Heavy" 。
由于不属于上述两者任何一类，所以我们返回 "Neither" 。

提示：

1 <= length, width, height <= 10⁵
1 <= mass <= 10³

方法一：模拟 · Go 实现

思考

箱子按边长、体积是否达到“笨重”阈值以及质量是否达到“沉重”阈值分成四类。判断条件均为常数次比较。

把 $bulky$ 、 $heavy$ 作成 $0 / 1$ ，用 $heavy ≪ 1 ∣ bulky$ 作为下标，在 $[Neither, Bulky, Heavy, Both]$ 中取值，避免多层分支。

根据题意模拟即可。

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

func categorizeBox(length int, width int, height int, mass int) string {
	v := length * width * height
	i := 0
	if length >= 10000 || width >= 10000 || height >= 10000 || v >= 1000000000 {
		i |= 1
	}
	if mass >= 100 {
		i |= 2
	}
	d := [4]string{"Neither", "Bulky", "Heavy", "Both"}
	return d[i]
}

方法二 · Go 实现

思考

方法一用位组合映射四类。若更看重可读性，则按“同时成立 / 仅笨重 / 仅沉重 / 皆否”依次判断，结果与映射表一致。

func categorizeBox(length int, width int, height int, mass int) string {
	v := length * width * height
	bulky := length >= 1e4 || width >= 1e4 || height >= 1e4 || v >= 1e9
	heavy := mass >= 100
	if bulky && heavy {
		return "Both"
	}
	if bulky {
		return "Bulky"
	}
	if heavy {
		return "Heavy"
	}
	return "Neither"
}

力扣原题 · Doocs 题解来源

2535. 数组元素和与数字和的绝对差

简单1 种解法

标签：数组、数学

题目、示例与约束

给你一个正整数数组 nums 。

元素和 是 nums 中的所有元素相加求和。
数字和 是 nums 中每一个元素的每一数位（重复数位需多次求和）相加求和。

返回 元素和 与 数字和 的绝对差。

注意：两个整数 x 和 y 的绝对差定义为 |x - y| 。

示例 1：

输入：nums = [1,15,6,3]
输出：9
解释：
nums 的元素和是 1 + 15 + 6 + 3 = 25 。
nums 的数字和是 1 + 1 + 5 + 6 + 3 = 16 。
元素和与数字和的绝对差是 |25 - 16| = 9 。

示例 2：

输入：nums = [1,2,3,4]
输出：0
解释：
nums 的元素和是 1 + 2 + 3 + 4 = 10 。
nums 的数字和是 1 + 2 + 3 + 4 = 10 。
元素和与数字和的绝对差是 |10 - 10| = 0 。

提示：

1 <= nums.length <= 2000
1 <= nums[i] <= 2000

方法一：模拟 · Go 实现

思考

元素和减去各位数字之和的绝对值。每个数拆位即可，无需额外结构。

遍历时累加原值到 $x$ ，同时除十取余累加到 $y$ 。元素和从不小于数字和，直接返回 $x - y$ 。

我们遍历数组 $nums$ ，计算元素和 $x$ 和数字和 $y$ ，最后返回 $| x - y |$ 即可。由于 $x$ 一定大于等于 $y$ ，所以我们也可以直接返回 $x - y$ 。

时间复杂度 $O (n \times \log_{10} M)$ ，其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度和数组中元素的最大值。空间复杂度 $O (1)$ 。

func differenceOfSum(nums []int) int {
	var x, y int
	for _, v := range nums {
		x += v
		for ; v > 0; v /= 10 {
			y += v % 10
		}
	}
	return x - y
}

力扣原题 · Doocs 题解来源

2539. 好子序列的个数 🔒

中等1 种解法

标签：哈希表、数学、字符串、组合数学、计数

题目、示例与约束

如果字符串的某个 子序列 不为空，且其中每一个字符出现的频率都相同，就认为该子序列是一个好子序列。

给你一个字符串 s ，请你统计并返回它的好子序列的个数。由于答案的值可能非常大，请返回对 10⁹ + 7 取余的结果作为答案。

字符串的 子序列 是指，通过删除一些（也可以不删除）字符且不改变剩余字符相对位置所组成的新字符串。

示例 1：

输入：s = "aabb"
输出：11
解释：s 的子序列的总数为 2⁴= 16 。其中，有 5 个子序列不是好子序列，分别是 "aabb"，"aabb"，"aabb"，"aabb" 以及空字符串。因此，好子序列的个数为 16 - 5 = 11 。

示例 2：

输入：s = "leet"
输出：12
解释：s 的子序列的总数为 2⁴= 16 。其中，有 4 个子序列不是好子序列，分别是 "leet"，"leet"，"leet" 以及空字符串。因此，好子序列的个数为 16 - 4 = 12 。

示例 3：

输入：s = "abcd"
输出：15
解释：s 所有非空子序列均为好子序列。因此，好子序列的个数为 16 - 1 = 15 。

提示：

1 <= s.length <= 10⁴
s 仅由小写英文字母组成

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

思考

好子序列要求其中出现过的每种字母次数相同且非空。子序列个数为 $2^{n}$ ，不能枚举；字母只有 $26$ 种，真正约束的是各字母频次。

枚举公共次数 $i = 1, \dots, m x$ 。对频次 $v \geq i$ 的字母，可选 $(\binom{v}{i})$ 种取法或完全不取，方案数为 $(\binom{v}{i}) + 1$ ；频次不足 $i$ 的字母必须不出现。各字母方案相乘后减去全不选，再对 $i$ 求和。阶乘与逆元预处理组合数。

由于题目说的是子序列中字母出现的次数，因此，我们可以先用一个数组 $c n t$ 统计字符串 $s$ 中每个字母出现的次数，记最大的次数为 $m x$ 。

接下来，我们在 $[1, 2. . m x]$ 范围内枚举子序列中字母出现的次数 $i$ ，然后枚举所有出现过的字母，如果该字母 $c$ 的出现次数 $c n t [c]$ 大于等于 $i$ ，那么我们可以从这 $c n t [c]$ 个相同字母中选择其中 $i$ 个，也可以一个都不选，那么当前字母的可选方案数就是 $c o m b (c n t [c], i) + 1$ ，将所有可选方案数相乘，可以得到当前次数的所有子序列次数，将次数减去 $1$ 累加到答案中。

那么问题的关键在于如何快速求出 $c o m b (n, k)$ ，我们可以用逆元来求解，具体实现见代码。

时间复杂度 $O (n \times C)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 是字符集的大小，本题中 $C = 26$ 。

const n = 1e4 + 1
const mod = 1e9 + 7

var f = make([]int, n)
var g = make([]int, n)

func qmi(a, k, p int) int {
	res := 1
	for k != 0 {
		if k&1 == 1 {
			res = res * a % p
		}
		k >>= 1
		a = a * a % p
	}
	return res
}

func init() {
	f[0], g[0] = 1, 1
	for i := 1; i < n; i++ {
		f[i] = f[i-1] * i % mod
		g[i] = qmi(f[i], mod-2, mod)
	}
}

func comb(n, k int) int {
	return (f[n] * g[k] % mod) * g[n-k] % mod
}

func countGoodSubsequences(s string) (ans int) {
	cnt := [26]int{}
	mx := 1
	for _, c := range s {
		cnt[c-'a']++
		mx = max(mx, cnt[c-'a'])
	}
	for i := 1; i <= mx; i++ {
		x := 1
		for _, v := range cnt {
			if v >= i {
				x = (x * (comb(v, i) + 1)) % mod
			}
		}
		ans = (ans + x - 1) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

2543. 判断一个点是否可以到达

困难1 种解法

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

题目、示例与约束

给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。

每一步 ，你可以从点 (x, y) 移动到以下点之一：

(x, y - x)
(x - y, y)
(2 * x, y)
(x, 2 * y)

给你两个整数 targetX 和 targetY ，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点，请你返回true ，否则返回 false 。

示例 1：

输入：targetX = 6, targetY = 9
输出：false
解释：没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。

示例 2：

输入：targetX = 4, targetY = 7
输出：true
解释：你可以按照以下路径到达：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。

提示：

1 <= targetX, targetY <= 10⁹

方法一：数学 · Go 实现

思考

从 $(1, 1)$ 出发，可把当前点变为 $(x + y, y)$ 、 $(x, x + y)$ 或把某一坐标翻倍。坐标可达 $10^{9}$ ，不能搜索。

前两种移动不改变 $gcd$ ，后两种只把 $gcd$ 乘上 $2$ 的幂，故终点的 $gcd$ 必须是 $2$ 的幂。反之，从终点反复除二并把较大奇数换成 $(x + y) / 2$ 可一直缩小到 $(1, 1)$ 。因此判断 $gcd (x, y)$ 是否为 $2$ 的幂即可，即 $x & (x - 1) = 0$ 。

我们注意到，前两种移动方式不会改变横、纵坐标的最大公约数，而后两种移动方式可以使得横、纵坐标的最大公约数乘上 $2$ 的幂次。也就是说，最后的横、纵坐标的最大公约数必须是 $2$ 的幂次。最大公约数不是 $2$ 的幂次，那么就无法到达。

接下来，我们证明，任意满足 $g c d (x, y) = 2^{k}$ 的 $(x, y)$ 均可达。

我们将移动方式反转一下，即从终点往回走，那么 $(x, y)$ 可以移动到 $(x, x + y)$ , $(x + y, y)$ , $(\frac{x}{2}, y)$ 和 $(x, \frac{y}{2})$ 。

只要 $x$ 或 $y$ 是偶数，我们就将其除以 $2$ ，直到 $x$ 和 $y$ 均为奇数。此时，若 $x \neq y$ ，不妨设 $x > y$ ，那么 $\frac{x + y}{2} < x$ 。由于 $x + y$ 是偶数，我们可以通过操作从 $(x, y)$ 移动到 $(x + y, y)$ ，再移动到 $(\frac{x + y}{2}, y)$ 。也就是说，我们总能让 $x$ 和 $y$ 不断变小。循环结束时，如果 $x = y = 1$ ，说明可以到达。

时间复杂度 $O (\log (min (t a r g e t X, t a r g e t Y)))$ ，空间复杂度 $O (1)$ 。

func isReachable(targetX int, targetY int) bool {
	x := gcd(targetX, targetY)
	return x&(x-1) == 0
}

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

力扣原题 · Doocs 题解来源

2544. 交替数字和

简单1 种解法

标签：数学

题目、示例与约束

给你一个正整数 n 。n 中的每一位数字都会按下述规则分配一个符号：

最高有效位 上的数字分配到正号。
剩余每位上数字的符号都与其相邻数字相反。

返回所有数字及其对应符号的和。

示例 1：

输入：n = 521
输出：4
解释：(+5) + (-2) + (+1) = 4

示例 2：

输入：n = 111
输出：1
解释：(+1) + (-1) + (+1) = 1

示例 3：

输入：n = 886996
输出：0
解释：(+8) + (-8) + (+6) + (-9) + (+9) + (-6) = 0

提示：

1 <= n <= 10⁹

方法一：模拟 · Go 实现

思考

从最高位起正负交替求和。位数很少，转成十进制字符串后按下标奇偶加权即可。

直接根据题目描述模拟即可。

我们定义一个初始符号 $s i g n = 1$ ，然后从最高有效位开始，每次取出一位数字 $x$ ，与 $s i g n$ 相乘，将结果加到答案中，然后将 $s i g n$ 取反，继续处理下一位数字，直到处理完所有数字。

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

func alternateDigitSum(n int) (ans int) {
	sign := 1
	for _, c := range strconv.Itoa(n) {
		x := int(c - '0')
		ans += sign * x
		sign *= -1
	}
	return
}

力扣原题 · Doocs 题解来源

2549. 统计桌面上的不同数字

简单1 种解法

标签：数组、哈希表、数学、模拟

题目、示例与约束

给你一个正整数 n ，开始时，它放在桌面上。在 10⁹ 天内，每天都要执行下述步骤：

对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
然后，将这些数字放在桌面上。

返回在 10⁹ 天之后，出现在桌面上的不同整数的数目。

注意：

一旦数字放在桌面上，则会一直保留直到结束。
% 表示取余运算。例如，14 % 3 等于 2 。

示例 1：

输入：n = 5
输出：4
解释：最开始，5 在桌面上。 
第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。 
再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。 
在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。

示例 2：

输入：n = 3 
输出：2
解释： 
因为 3 % 2 == 1 ，2 也出现在桌面上。 
在十亿天结束时，桌面上的不同数字只有两个：2 和 3 。

提示：

1 <= n <= 100

方法一：脑筋急转弯 · Go 实现

思考

每天若 $x$ 在黑板上且 $0 < y < x$ 、 $x mod y = 1$ ，则可写入 $y$ 。从 $n$ 出发， $n mod (n - 1) = 1$ （ $n > 1$ ），故 $n - 1$ 必然出现，进而 $n - 2, \dots, 2$ 都会出现， $1$ 永远写不上去。

不同数字个数因此为 $n - 1$ ，并在 $n = 1$ 时为 $1$ 。无需模拟过程。

由于每一次对桌面上的数字 $n$ 进行操作，会使得数字 $n - 1$ 也出现在桌面上，因此最终桌面上的数字为 $[2, . . . n]$ ，共 $n - 1$ 个数字。

注意到 $n$ 可能为 $1$ ，因此需要特判。

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

func distinctIntegers(n int) int {
	return max(1, n-1)
}

力扣原题 · Doocs 题解来源

2550. 猴子碰撞的方法数

中等1 种解法

标签：递归、数学

题目、示例与约束

现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。

每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是：

顺时针方向的顶点 (i + 1) % n ，或
逆时针方向的顶点 (i - 1 + n) % n 。

如果移动后至少有两只猴子停留在同一个顶点上或者相交在一条边上，则会发生碰撞。

返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 10⁹+7 取余后的结果。

注意，每只猴子只能移动一次。

示例 1：

输入：n = 3
输出：6
解释：共计 8 种移动方式。
下面列出两种会发生碰撞的方式：
- 猴子 1 顺时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 2 碰撞。
- 猴子 1 逆时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 3 碰撞。
可以证明，有 6 种让猴子碰撞的方法。

示例 2：

输入：n = 4
输出：14
解释：可以证明，有 14 种让猴子碰撞的方法。

提示：

3 <= n <= 10⁹

方法一：数学（快速幂） · Go 实现

思考

正多边形顶点上的猴子同时顺时针或逆时针走一步，求会发生碰撞的走法数。每只猴子两种方向，共 $2^{n}$ 种；仅全体同向的两种不会相遇。

$n$ 可达 $10^{9}$ ，不能枚举。快速幂求 $2^{n} mod (10^{9} + 7)$ 再减 $2$ ，注意减法借位。

根据题目描述，每一只猴子都有两种移动方式，即顺时针或逆时针。因此，一共有 $2^{n}$ 种移动方式。不碰撞的移动方式只有两种，即所有猴子都顺时针移动或所有猴子都逆时针移动。因此，碰撞的移动方式有 $2^{n} - 2$ 种。

我们可以用快速幂求出 $2^{n}$ 的值，然后用 $2^{n} - 2$ 求出碰撞的移动方式数，最后对 $10^{9} + 7$ 取余即可。

时间复杂度 $O (\log n)$ ，其中 $n$ 为猴子的数量。空间复杂度 $O (1)$ 。

func monkeyMove(n int) int {
	const mod = 1e9 + 7
	qpow := func(a, n int) int {
		ans := 1
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans = ans * a % mod
			}
			a = a * a % mod
		}
		return ans
	}
	return (qpow(2, n) - 2 + mod) % mod
}

力扣原题 · Doocs 题解来源

2575. 找出字符串的可整除数组

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

如果 word[0,...,i] 所表示的数值能被 m 整除，div[i] = 1
否则，div[i] = 0

返回 word 的可整除数组。

示例 1：

输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例 2：

输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

提示：

1 <= n <= 10⁵
word.length == n
word 由数字 0 到 9 组成
1 <= m <= 10⁹

方法一：遍历 + 取模 · Go 实现

思考

判断每个前缀表示的整数能否被 $m$ 整除。前缀长度达 $10^{5}$ ，不能真的构造大整数。

模运算可递推： $x \leftarrow (10 x + d) mod m$ 。当前余数为 $0$ 则该位记 $1$ ，否则记 $0$ 。

我们遍历字符串 word，用变量 $x$ 记录当前前缀与 $m$ 的取模结果，如果 $x$ 为 $0$ ，则当前位置的可整除数组值为 $1$ ，否则为 $0$ 。

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

func divisibilityArray(word string, m int) (ans []int) {
	x := 0
	for _, c := range word {
		x = (x*10 + int(c-'0')) % m
		if x == 0 {
			ans = append(ans, 1)
		} else {
			ans = append(ans, 0)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2579. 统计染色格子数

中等1 种解法

标签：数学

题目、示例与约束

有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数 n ，表示你需要执行以下步骤 n 分钟：

第一分钟，将任一格子染成蓝色。
之后的每一分钟，将与蓝色格子相邻的所有未染色格子染成蓝色。

下图分别是 1、2、3 分钟后的网格图。

请你返回 n 分钟之后 被染色的格子 数目。

示例 1：

输入：n = 1
输出：1
解释：1 分钟后，只有 1 个蓝色的格子，所以返回 1 。

示例 2：

输入：n = 2
输出：5
解释：2 分钟后，有 4 个在边缘的蓝色格子和 1 个在中间的蓝色格子，所以返回 5 。

提示：

1 <= n <= 10⁵

方法一：数学 · Go 实现

思考

第 $1$ 分钟涂一格，之后每分钟在已涂格子的四邻新涂一圈。模拟 $n$ 分钟在 $n \leq 10^{5}$ 时格子数量平方增长，不必落盘。

第 $n$ 分钟的图形是菱形，十字方向各有 $n$ 格，面积为 $1 + 4 (1 + 2 + \dots + (n - 1)) = 2 n (n - 1) + 1$ 。

我们观察发现，第 $n$ 分钟后，网格中共有 $2 \times n - 1$ 列，每一列上的数字分别为 $1, 3, 5, \dots, 2 \times n - 1, 2 \times n - 3, \dots, 3, 1$ 。左右两部分均为等差数列，求和可以得到答案 $2 \times n \times (n - 1) + 1$ 。

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

func coloredCells(n int) int64 {
	return int64(2*n*(n-1) + 1)
}

力扣原题 · Doocs 题解来源

2582. 递枕头

简单2 种解法

标签：数学、模拟

题目、示例与约束

n 个人站成一排，按从 1 到 n 编号。最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。

给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号。

示例 1：

输入：n = 4, time = 5
输出：2
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。
5 秒后，枕头传递到第 2 个人手中。

示例 2：

输入：n = 3, time = 2
输出：3
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 。
2 秒后，枕头传递到第 3 个人手中。

提示：

2 <= n <= 1000
1 <= time <= 1000

注意：本题与 3178.找出 K 秒后拿着球的孩子一致。

方法一：模拟 · Go 实现

思考

枕头在 $1. . n$ 上来回传递， $time$ 秒后落在谁手里。 $time \leq 1000$ ，按秒模拟方向翻转即可。

我们可以模拟枕头传递的过程，每次传递枕头时，如果枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

时间复杂度 $O (t i m e)$ ，空间复杂度 $O (1)$ 。其中 $t i m e$ 为给定的时间。

func passThePillow(n int, time int) int {
	ans, k := 1, 1
	for ; time > 0; time-- {
		ans += k
		if ans == 1 || ans == n {
			k *= -1
		}
	}
	return ans
}

方法二：数学 · Go 实现

思考

方法一随 $time$ 线性增长。一个来回是 $n - 1$ 步，用整除得到轮次与余步：偶数轮从 $1$ 往右走余步，奇数轮从 $n$ 往左走余步，常数时间可得。

我们注意到，每一轮有 $n - 1$ 次传递，因此我们可以将 $t i m e$ 除以 $n - 1$ 得到枕头传递的轮数 $k$ ，然后再将 $t i m e$ 对 $n - 1$ 取余得到枕头在当前轮的剩余传递次数 $m o d$ 。

接下来我们判断当前的轮数 $k$ ：

如果 $k$ 为奇数，那么枕头当前的传递方向是从队尾到队首，因此枕头会传递到编号为 $n - m o d$ 的人手中；
如果 $k$ 为偶数，那么枕头当前的传递方向是从队首到队尾，因此枕头会传递到编号为 $m o d + 1$ 的人手中。

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

func passThePillow(n int, time int) int {
	k, mod := time/(n-1), time%(n-1)
	if k&1 == 1 {
		return n - mod
	}
	return mod + 1
}

力扣原题 · Doocs 题解来源

2584. 分割数组使乘积互质

困难1 种解法

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

题目、示例与约束

给你一个长度为 n 的整数数组 nums ，下标从 0 开始。

如果在下标 i 处分割数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割有效。

例如，如果 nums = [2, 3, 3] ，那么在下标 i = 0 处的分割有效，因为 2 和 9 互质，而在下标 i = 1 处的分割无效，因为 6 和 3 不互质。在下标 i = 2 处的分割也无效，因为 i == n - 1 。

返回可以有效分割数组的最小下标 i ，如果不存在有效分割，则返回 -1 。

当且仅当 gcd(val1, val2) == 1 成立时，val1 和 val2 这两个值才是互质的，其中 gcd(val1, val2) 表示 val1 和 val2 的最大公约数。

示例 1：

输入：nums = [4,7,8,15,3,5]
输出：2
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2 。

示例 2：

输入：nums = [4,7,15,8,3,5]
输出：-1
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
不存在有效分割。

提示：

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

方法一：质因数分解 · Go 实现

思考

找最小下标 $i$ ，使前缀乘积与后缀乘积互质。直接算乘积会溢出，互质等价于两侧没有公共质因子。

每个质因子第一次出现的位置必须与它最后一次出现的位置落在切点同侧。记录每个因子首次下标，并把该下标的“必须覆盖到”更新为最后出现位置。从左扫描这些覆盖右端，若在到达某下标前覆盖已经结束，该处即可切开。

func findValidSplit(nums []int) int {
	first := map[int]int{}
	n := len(nums)
	last := make([]int, n)
	for i := range last {
		last[i] = i
	}
	for i, x := range nums {
		for j := 2; j <= x/j; j++ {
			if x%j == 0 {
				if k, ok := first[j]; ok {
					last[k] = i
				} else {
					first[j] = i
				}
				for x%j == 0 {
					x /= j
				}
			}
		}
		if x > 1 {
			if k, ok := first[x]; ok {
				last[k] = i
			} else {
				first[x] = i
			}
		}
	}
	mx := last[0]
	for i, x := range last {
		if mx < i {
			return mx
		}
		mx = max(mx, x)
	}
	return -1
}

力扣原题 · Doocs 题解来源

2613. 美数对 🔒

困难1 种解法

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

题目、示例与约束

给定两个长度相同的 下标从 0 开始 的整数数组 nums1 和 nums2 ，如果 |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| 在所有可能的下标对中是最小的，其中 i < j ，则称下标对 (i,j) 为美数对，

返回美数对。如果有多个美数对，则返回字典序最小的美数对。

注意：

|x| 表示 x 的绝对值。
一对索引 (i1, j1) 在字典序意义下小于 (i2, j2) ，当且仅当 i1 < i2 或 i1 == i2 且 j1 < j2 。

示例 1 ：

输入：nums1 = [1,2,3,2,4], nums2 = [2,3,1,2,3]
输出：[0,3]
解释：取下标为 0 和下标为 3 的数对，计算出 |nums1[0]-nums1[3]| + |nums2[0]-nums2[3]| 的值为 1 ，这是我们能够得到的最小值。

示例 2 ：

输入：nums1 = [1,2,4,3,2,5], nums2 = [1,4,2,3,5,1]
输出：[1,4]
解释：取下标为 1 和下标为 4 的数对，计算出 |nums1[1]-nums1[4]| + |nums2[1]-nums2[4]| 的值为 1，这是我们可以达到的最小值。

提示：

2 <= nums1.length, nums2.length <= 10⁵
nums1.length == nums2.length
0 <= nums1_i<= nums1.length
0 <= nums2_i <= nums2.length

方法一：排序 + 分治 · Go 实现

思考

要在平面上找曼哈顿距离最小的下标对，并列时取字典序最小。两两枚举 $n \leq 10^{5}$ 不可行。重合点距离为 $0$ ，若存在直接返回其最小下标对。

无重点时，经典最近点对分治适用：按 $x$ 排序后左右递归，再用宽 $d$ 的带状区域按 $y$ 扫描跨越中线的点对，同时用下标比较打破平局。

本题相当于找出平面中两个点，使得它们的曼哈顿距离最小，如果有多个点满足条件，则返回下标字典序最小的点。

我们先处理重复点的情况，找出每个点对应的下标列表，如果某个点的下标列表长度大于 $1$ ，那么它的前两个下标可作为候选答案，我们找出最小的下标对即可。

如果没有重复点，我们将所有点按照 $x$ 坐标排序，然后分治求解。

对于每个区间 $[l, r]$ ，我们先求出 $x$ 坐标的中位数 $m$ ，然后递归求解左右两个区间，分别得到 $d_{1}, (p i_{1}, p j_{1})$ 和 $d_{2}, (p i_{2}, p j_{2})$ ，其中 $d_{1}$ 和 $d_{2}$ 分别表示左右两个区间的最小曼哈顿距离，而 $(p i_{1}, p j_{1})$ 和 $(p i_{2}, p j_{2})$ 分别表示左右两个区间的最小曼哈顿距离的两个点的下标。我们取 $d_{1}$ 和 $d_{2}$ 中较小的一个，如果 $d_{1} = d_{2}$ ，则取下标字典序较小的一个，将其作为当前区间的最小曼哈顿距离，同时将对应的两个点的下标作为答案。

以上考虑的是两个点位于同一侧的情况，如果两个点位于不同侧，那么我们以中间点，即下标为 $m = ⌊ (l + r) / 2 ⌋$ 的点为标准，划分出一个新的区域，区域的范围为中间点向左右两侧分别扩展 $d_{1}$ 的范围。然后我们将这些范围内的点按照 $y$ 坐标排序，然后遍历排序后的每个点对，如果两个点的 $y$ 坐标之差大于当前的最小曼哈顿距离，那么后面的点对都不用考虑了，因为它们的 $y$ 坐标之差更大，所以曼哈顿距离更大，不会比当前的最小曼哈顿距离更小。否则，我们更新最小曼哈顿距离，同时更新答案。

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

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

func beautifulPair(nums1 []int, nums2 []int) []int {
	n := len(nums1)
	pl := map[[2]int][]int{}
	for i := 0; i < n; i++ {
		k := [2]int{nums1[i], nums2[i]}
		pl[k] = append(pl[k], i)
	}
	points := [][3]int{}
	for i := 0; i < n; i++ {
		k := [2]int{nums1[i], nums2[i]}
		if len(pl[k]) > 1 {
			return []int{pl[k][0], pl[k][1]}
		}
		points = append(points, [3]int{nums1[i], nums2[i], i})
	}
	sort.Slice(points, func(i, j int) bool { return points[i][0] < points[j][0] })

	var dfs func(l, r int) [3]int
	dfs = func(l, r int) [3]int {
		if l >= r {
			return [3]int{1 << 30, -1, -1}
		}
		m := (l + r) >> 1
		x := points[m][0]
		t1 := dfs(l, m)
		t2 := dfs(m+1, r)
		if t1[0] > t2[0] || (t1[0] == t2[0] && (t1[1] > t2[1] || (t1[1] == t2[1] && t1[2] > t2[2]))) {
			t1 = t2
		}
		t := [][3]int{}
		for i := l; i <= r; i++ {
			if abs(points[i][0]-x) <= t1[0] {
				t = append(t, points[i])
			}
		}
		sort.Slice(t, func(i, j int) bool { return t[i][1] < t[j][1] })
		for i := 0; i < len(t); i++ {
			for j := i + 1; j < len(t); j++ {
				if t[j][1]-t[i][1] > t1[0] {
					break
				}
				pi := min(t[i][2], t[j][2])
				pj := max(t[i][2], t[j][2])
				d := dist(t[i][0], t[i][1], t[j][0], t[j][1])
				if d < t1[0] || (d == t1[0] && (pi < t1[1] || (pi == t1[1] && pj < t1[2]))) {
					t1 = [3]int{d, pi, pj}
				}
			}
		}
		return t1
	}
	ans := dfs(0, n-1)
	return []int{ans[1], ans[2]}
}

func dist(x1, y1, x2, y2 int) int {
	return abs(x1-x2) + abs(y1-y2)
}

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

力扣原题 · Doocs 题解来源

2614. 对角线上的质数

简单1 种解法

标签：数组、数学、矩阵、数论

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 nums 。

返回位于 nums 至少一条 对角线 上的最大质数。如果任一对角线上均不存在质数，返回 0 。

注意：

如果某个整数大于 1 ，且不存在除 1 和自身之外的正整数因子，则认为该整数是一个质数。
如果存在整数 i ，使得 nums[i][i] = val 或者 nums[i][nums.length - i - 1]= val ，则认为整数 val 位于 nums 的一条对角线上。

在上图中，一条对角线是 [1,5,9] ，而另一条对角线是 [3,5,7] 。

示例 1：

输入：nums = [[1,2,3],[5,6,7],[9,10,11]]
输出：11
解释：数字 1、3、6、9 和 11 是所有 "位于至少一条对角线上" 的数字。由于 11 是最大的质数，故返回 11 。

示例 2：

输入：nums = [[1,2,3],[5,17,7],[9,11,10]]
输出：17
解释：数字 1、3、9、10 和 17 是所有满足"位于至少一条对角线上"的数字。由于 17 是最大的质数，故返回 17 。

提示：

1 <= nums.length <= 300
nums.length == nums_i.length
1 <= nums[i][j] <= 4*10⁶

方法一：数学 + 模拟 · Go 实现

思考

只需考察主、副对角线上的数，矩阵阶不超过 $300$ ，每个数不超过 $4 \times 10^{6}$ 。对对角元做试除判断质数，复杂度约 $O (n \sqrt{M})$ ，足以通过。

小于 $2$ 的数不是质数；其余试除到平方根。遍历时同时更新两条对角线上的最大质数。

我们实现一个函数 is_prime，判断一个数是否为质数。

然后遍历数组，判断对角线上的数是否为质数，如果是，更新答案。

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

func diagonalPrime(nums [][]int) (ans int) {
	n := len(nums)
	for i, row := range nums {
		if isPrime(row[i]) {
			ans = max(ans, row[i])
		}
		if isPrime(row[n-i-1]) {
			ans = max(ans, row[n-i-1])
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

2647. 把三角形染成红色 🔒

困难1 种解法

标签：数组、数学

题目、示例与约束

现给定你一个整数 n 。考虑一个边长为 n 的等边三角形，被分成 n² 个单位等边三角形。这个三角形有 n 个 从 1 开始编号 的行，其中第 i 行有 2i - 1 个单位等边三角形。

第 i 行的三角形也是 从 1 开始编号 的，其坐标从 (i, 1) 到 (i, 2i - 1) 。下面的图像显示了一个边长为 4 的三角形及其三角形的索引。

如果两个三角形 共享一条边 ，则它们是相邻的。例如：

三角形 (1,1) 和 (2,2) 是相邻的。
三角形 (3,2) 和 (3,3) 是相邻的。
三角形 (2,2) 和 (3,3) 不相邻，因为它们没有共享任何边。

初始时，所有单位三角形都是白色的。你想选择 k 个三角形并将它们涂成红色。然后我们将运行以下算法：

选择一个 至少有两个 红色相邻三角形的白色三角形。
- 如果没有这样的三角形，请停止算法。
将该三角形涂成红色。
回到步骤 1。

选择最小的 k 并在运行此算法之前将 k 个三角形涂成红色，使得在算法停止后，所有单元三角形都被涂成红色。

返回一个二维列表，其中包含你要最初涂成红色的三角形的坐标。答案必须尽可能小。如果有多个有效的解决方案，请返回其中任意一个。

示例 1 ：

输入：n = 3
输出：[[1,1],[2,1],[2,3],[3,1],[3,5]]
解释：初始时，我们选择展示的5个三角形染成红色。然后，我们运行以下算法：
- 选择(2,2)，它有三个红色相邻的三角形，并将其染成红色。
- 选择(3,2)，它有两个红色相邻的三角形，并将其染成红色。
- 选择(3,4)，它有三个红色相邻的三角形，并将其染成红色。
- 选择(3,3)，它有三个红色相邻的三角形，并将其染成红色。 
可以证明，选择任何4个三角形并运行算法都无法将所有三角形都染成红色。

示例 2 ：

输入：n = 2
输出：[[1,1],[2,1],[2,3]]
解释：初始时，我们选择图中所示的 3 个三角形为红色。然后，我们运行以下算法： 
-选择有三个红色相邻的 (2,2) 三角形并将其染成红色。 
可以证明，选择任意 2 个三角形并运行该算法都不能使所有三角形变为红色。

提示：

1 <= n <= 1000

方法一：找规律 · Go 实现

思考

要涂尽可能少的红格使每个白三角形恰有两边被红格挡住。穷举涂色在 $n \leq 1000$ 下格子数为 $O (n^{2})$ ，搜索不可行。

作图可见：顶行必涂，其余自底向上每四行循环一种稀疏涂法。按该周期从第 $n$ 行走到第 $2$ 行输出坐标即可。

我们画图观察，可以发现，第一行只有一个三角形，一定要涂色，而从最后一行开始，到第二行结束，每四行的涂色方案是一样的：

最后一行涂色坐标为 $(n, 1)$ , $(n, 3)$ , ..., $(n, 2 n - 1)$ 。
第 $n - 1$ 行涂色坐标为 $(n - 1, 2)$ 。
第 $n - 2$ 行涂色坐标为 $(n - 2, 3)$ , $(n - 2, 5)$ , ..., $(n - 2, 2 n - 5)$ 。
第 $n - 3$ 行涂色坐标为 $(n - 3, 1)$ 。

因此，我们可以按照上述规律，先给第一行涂色，然后从最后一行开始，每四行涂色一次，直到第二行结束。

时间复杂度 $O (n^{2})$ ，其中 $n$ 为题目给定的参数。忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

func colorRed(n int) (ans [][]int) {
	ans = append(ans, []int{1, 1})
	for i, k := n, 0; i > 1; i, k = i-1, (k+1)%4 {
		if k == 0 {
			for j := 1; j < i<<1; j += 2 {
				ans = append(ans, []int{i, j})
			}
		} else if k == 1 {
			ans = append(ans, []int{i, 2})
		} else if k == 2 {
			for j := 3; j < i<<1; j += 2 {
				ans = append(ans, []int{i, j})
			}
		} else {
			ans = append(ans, []int{i, 1})
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2651. 计算列车到站时间

简单1 种解法

标签：数学

题目、示例与约束

给你一个正整数 arrivalTime 表示列车正点到站的时间（单位：小时），另给你一个正整数 delayedTime 表示列车延误的小时数。

返回列车实际到站的时间。

注意，该问题中的时间采用 24 小时制。

示例 1：

输入：arrivalTime = 15, delayedTime = 5 
输出：20 
解释：列车正点到站时间是 15:00 ，延误 5 小时，所以列车实际到站的时间是 15 + 5 = 20（20:00）。

示例 2：

输入：arrivalTime = 13, delayedTime = 11
输出：0
解释：列车正点到站时间是 13:00 ，延误 11 小时，所以列车实际到站的时间是 13 + 11 = 24（在 24 小时制中表示为 00:00 ，所以返回 0）。

提示：

1 <= arrivaltime < 24
1 <= delayedTime <= 24

方法一：数学 · Go 实现

思考

到站时刻在二十四小时制下循环。直接相加可能超过 $23$ ，对 $24$ 取模即回到合法钟面，无需枚举进位。

我们直接计算列车实际到站的时间，即为 $a r r i v a l T i m e + d e l a y e d T i m e$ ，但是由于时间采用 24 小时制，所以我们需要对结果取模，即 $(a r r i v a l T i m e + d e l a y e d T i m e) mod 24$ 。

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

func findDelayedArrivalTime(arrivalTime int, delayedTime int) int {
	return (arrivalTime + delayedTime) % 24
}

力扣原题 · Doocs 题解来源

2652. 倍数求和

简单2 种解法

标签：数学

题目、示例与约束

给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。

返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。

示例 1：

输入：n = 7
输出：21
解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21。

示例 2：

输入：n = 10
输出：40
解释：在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40。

示例 3：

输入：n = 9
输出：30
解释：在 [1, 9] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9 。数字之和为 30。

提示：

1 <= n <= 10³

方法一：枚举 · Go 实现

思考

求和 $[1, n]$ 中能被 $3$ 、 $5$ 或 $7$ 整除的数。 $n \leq 1000$ ，枚举每个 $x$ 判断整除即可，实现最直接。

我们直接枚举 $[1, . . n]$ 中的每一个数 $x$ ，如果 $x$ 能被 $3$ , $5$ , $7$ 整除，那么就将 $x$ 累加到答案中。

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

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

func sumOfMultiples(n int) (ans int) {
	for x := 1; x <= n; x++ {
		if x%3 == 0 || x%5 == 0 || x%7 == 0 {
			ans += x
		}
	}
	return
}

方法二：数学（容斥原理） · Go 实现

思考

方法一线性扫过 $n$ 。能被 $x$ 整除的数构成等差数列，其和有闭式；容斥去掉重复倍数后可 $O (1)$ 求值。

即 $f (3) + f (5) + f (7) - f (15) - f (21) - f (35) + f (105)$ 。

我们定义函数 $f (x)$ 表示 $[1, . . n]$ 中能被 $x$ 整除的数之和，那么一共有 $m = ⌊ \frac{n}{x} ⌋$ 个数能被 $x$ 整除，这些数字分别为 $x$ , $2 x$ , $3 x$ , $\dots$ , $m x$ ，构成一个等差数列，首项为 $x$ ，末项为 $m x$ ，项数为 $m$ ，因此 $f (x) = \frac{(x + m x) \times m}{2}$ 。

根据容斥原理，我们可以得到答案为：

f (3) + f (5) + f (7) - f (3 \times 5) - f (3 \times 7) - f (5 \times 7) + f (3 \times 5 \times 7)

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

func sumOfMultiples(n int) int {
	f := func(x int) int {
		m := n / x
		return (x + m*x) * m / 2
	}
	return f(3) + f(5) + f(7) - f(3*5) - f(3*7) - f(5*7) + f(3*5*7)
}

力扣原题 · Doocs 题解来源

2654. 使数组所有元素变成 1 的最少操作次数

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的正整数数组 nums 。你可以对数组执行以下操作任意次：

选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的最少操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

示例 1：

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。

示例 2：

输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。

提示：

2 <= nums.length <= 50
1 <= nums[i] <= 10⁶

方法一：数学 · Go 实现

思考

一次操作用相邻 gcd 覆盖其中一个数。若已有 $1$ ，其余位置各需一次覆盖，共 $n - c n t$ 。否则须先在某处制造 $1$ 。

gcd 具有区间递降性质，最短能得到 $1$ 的子数组长度 $m i$ 即制造 $1$ 的最少步数 $m i - 1$ ，再把这个 $1$ 扩到其余 $n - 1$ 个位置。

$n \leq 50$ ，枚举区间累计 gcd 即可；若全局 gcd 大于 $1$ 则无解。

我们先统计数组 $n u m s$ 中 $1$ 的个数 $c n t$ ，如果 $c n t > 0$ ，那么只需要 $n - c n t$ 次操作，就可以将整个数组变成 $1$ 。

否则，我们需要首先将数组中的一个元素变成 $1$ ，然后剩余的最小操作次数就是 $n - 1$ 。

考虑如何将数组中的一个元素变成 $1$ ，并且使得操作次数尽可能小。实际上，我们只需要找到一个最小的连续子数组区间 $n u m s [i, . . j]$ ，使得子数组中所有元素的最大公约数为 $1$ ，子数组区间长度为 $m i = min (m i, j - i + 1)$ 。最后我们总的操作次数就是 $n - 1 + m i - 1$ 。

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

func minOperations(nums []int) int {
	n := len(nums)
	cnt := 0
	for _, x := range nums {
		if x == 1 {
			cnt++
		}
	}
	if cnt > 0 {
		return n - cnt
	}
	mi := n + 1
	for i := 0; i < n; i++ {
		g := 0
		for j := i; j < n; j++ {
			g = gcd(g, nums[j])
			if g == 1 {
				mi = min(mi, j-i+1)
			}
		}
	}
	if mi > n {
		return -1
	}
	return n - 1 + mi - 1
}

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

力扣原题 · Doocs 题解来源

2729. 判断一个数是否迷人

简单1 种解法

标签：哈希表、数学

题目、示例与约束

给你一个三位数整数 n 。

如果经过以下修改得到的数字恰好包含数字 1 到 9 各一次且不包含任何 0 ，那么我们称数字 n 是 迷人的 ：

将 n 与数字 2 * n 和 3 * n 连接。

如果 n 是迷人的，返回 true，否则返回 false 。

连接两个数字表示把它们首尾相接连在一起。比方说 121 和 371 连接得到 121371 。

示例 1：

输入：n = 192
输出：true
解释：我们将数字 n = 192 ，2 * n = 384 和 3 * n = 576 连接，得到 192384576 。这个数字包含 1 到 9 恰好各一次。

示例 2：

输入：n = 100
输出：false
解释：我们将数字 n = 100 ，2 * n = 200 和 3 * n = 300 连接，得到 100200300 。这个数字不符合上述条件。

提示：

100 <= n <= 999

方法一：模拟 · Go 实现

思考

判定 $n$ 、 $2 n$ 、 $3 n$ 拼接后是否恰好为 $1$ 到 $9$ 各一次。 $n$ 为三位数，拼接长度固定，枚举每一种排列并无必要。

拼成字符串后排序，与 $123456789$ 比较即可同时排除缺数字、重复与出现 $0$ 。

我们根据题目描述，将数字 $n$ 与 $2 \times n$ 和 $3 \times n$ 连接，得到字符串 $s$ ，然后判断 $s$ 是否包含数字 $1$ 到 $9$ 各一次且不包含任何 $0$ 即可。

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

func isFascinating(n int) bool {
	s := strconv.Itoa(n) + strconv.Itoa(n*2) + strconv.Itoa(n*3)
	cnt := [10]int{}
	for _, c := range s {
		cnt[c-'0']++
		if cnt[c-'0'] > 1 {
			return false
		}
	}
	return cnt[0] == 0 && len(s) == 9
}

力扣原题 · Doocs 题解来源

2739. 总行驶距离

简单1 种解法

标签：数学、模拟

题目、示例与约束

卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。

该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。

返回卡车可以行驶的最大距离。

注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。

示例 1：

输入：mainTank = 5, additionalTank = 10
输出：60
解释：
在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。
在用掉剩下的 1 升燃料后，没有新的燃料注入到主油箱中，主油箱变为空。
总行驶距离为 60km 。

示例 2：

输入：mainTank = 1, additionalTank = 2
输出：10
解释：
在用掉 1 升燃料后，主油箱变为空。
总行驶距离为 10km 。

提示：

1 <= mainTank, additionalTank <= 100

方法一：模拟 · Go 实现

思考

主油箱每消耗 $5$ 升且副油箱非空时补 $1$ 升，每升行驶 $10$ 公里。油量上限有限，模拟每次消耗一升即可，不必推导闭式。

循环消耗主油箱：里程加 $10$ ，每第五次且副箱仍有油时把一升移入主箱，直到主箱为空。

我们可以模拟卡车的行驶过程，每次消耗 $1$ 升主油箱中的燃料，行驶 $10$ 公里。每当主油箱中的燃料消耗 $5$ 升时，如果副油箱中有燃料，则将副油箱中的 $1$ 升燃料转移到主油箱中。一直模拟到主油箱中的燃料消耗完为止。

时间复杂度 $O (n + m)$ ，其中 $n$ 和 $m$ 分别是主油箱和副油箱中的燃料数量。空间复杂度 $O (1)$ 。

func distanceTraveled(mainTank int, additionalTank int) (ans int) {
	cur := 0
	for mainTank > 0 {
		cur++
		ans += 10
		mainTank--
		if cur%5 == 0 && additionalTank > 0 {
			additionalTank--
			mainTank++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

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

2447. 最大公因数等于 K 的子数组数目 ​

2450. 应用操作后不同二进制字符串的数量 🔒 ​

2455. 可被三整除的偶数的平均值 ​

2469. 温度转换 ​

2470. 最小公倍数等于 K 的子数组数目 ​

2481. 分割圆的最少切割次数 ​

2507. 使用质因数之和替换后可以取到的最小值 ​

2514. 统计同位异构字符串数目 ​

2520. 统计能整除数字的位数 ​

2521. 数组乘积中的不同质因数数目 ​

2523. 范围内最接近的两个质数 ​

2525. 根据规则将箱子分类 ​

2535. 数组元素和与数字和的绝对差 ​

2539. 好子序列的个数 🔒 ​

2543. 判断一个点是否可以到达 ​

2544. 交替数字和 ​

2549. 统计桌面上的不同数字 ​

2550. 猴子碰撞的方法数 ​

2575. 找出字符串的可整除数组 ​

2579. 统计染色格子数 ​

2582. 递枕头 ​

2584. 分割数组使乘积互质 ​

2613. 美数对 🔒 ​

2614. 对角线上的质数 ​

2647. 把三角形染成红色 🔒 ​

2651. 计算列车到站时间 ​

2652. 倍数求和 ​

2654. 使数组所有元素变成 1 的最少操作次数 ​

2729. 判断一个数是否迷人 ​

2739. 总行驶距离 ​

继续阅读

LeetCode Go · 数学与几何（7）

2447. 最大公因数等于 K 的子数组数目

2450. 应用操作后不同二进制字符串的数量 🔒

2455. 可被三整除的偶数的平均值

2469. 温度转换

2470. 最小公倍数等于 K 的子数组数目

2481. 分割圆的最少切割次数

2507. 使用质因数之和替换后可以取到的最小值

2514. 统计同位异构字符串数目

2520. 统计能整除数字的位数

2521. 数组乘积中的不同质因数数目

2523. 范围内最接近的两个质数

2525. 根据规则将箱子分类

2535. 数组元素和与数字和的绝对差

2539. 好子序列的个数 🔒

2543. 判断一个点是否可以到达

2544. 交替数字和

2549. 统计桌面上的不同数字

2550. 猴子碰撞的方法数

2575. 找出字符串的可整除数组

2579. 统计染色格子数

2582. 递枕头

2584. 分割数组使乘积互质

2613. 美数对 🔒

2614. 对角线上的质数

2647. 把三角形染成红色 🔒

2651. 计算列车到站时间

2652. 倍数求和

2654. 使数组所有元素变成 1 的最少操作次数

2729. 判断一个数是否迷人

2739. 总行驶距离