LeetCode Go · 数学与几何（4）

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

来源与许可

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

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

1073. 负二进制数相加

中等1 种解法

标签：数组、数学

题目、示例与约束

给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。

数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。

返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。

 

示例 1：

输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
输出：[1,0,0,0,0]
解释：arr1 表示 11，arr2 表示 5，输出表示 16 。

示例 2：

输入：arr1 = [0], arr2 = [0]
输出：[0]

示例 3：

输入：arr1 = [0], arr2 = [1]
输出：[1]

 

提示：

• 1 <= arr1.length, arr2.length <= 1000
• arr1[i] 和 arr2[i] 都是 0 或 1
• arr1 和 arr2 都没有前导0

方法一：模拟 · Go 实现

思考

负二进制加法与普通加法一样从低位进位，但基为 $-2$，进位规则不同： $2\times (-2{)}^i=-(-2{)}^{i+1}$， $-1\times (-2{)}^i=(-2{)}^i+(-2{)}^{i+1}$。长度 $\le 1000$，按位模拟即可。

从右往左取 $a+b+c$。和 $\ge 2$ 则减 $2$ 并向高位进 $-1$；和为 $-1$ 则写 $1$ 并进 $1$。

结果低位在前，去掉多余前导 $0$ 后反转。

我们遍历两个数组，从最低位开始，记两个数组当前位的数字为 $a$ 和 $b$，进位为 $c$，三个数相加的结果为 $x$。

• 先将进位 $c$ 置为 $0$。
• 如果 $x\ge 2$，由于 $(-2{)}^i+(-2{)}^i=-(-2{)}^{i+1}$，所以我们可以将 $x$ 减去 $2$，并向高位进位 $-1$。
• 如果 $x=-1$，由于 $-(-2{)}^i=(-2{)}^i+(-2{)}^{i+1}$，所以我们可以将 $x$ 置为 $1$，并向高位进位 $1$。

然后，我们将 $x$ 加入到答案数组中，然后继续处理下一位。

遍历结束后，去除答案数组中末尾的 $0$，并将数组反转，即可得到最终的答案。

时间复杂度 $O(max(n,m))$，其中 $n$ 和 $m$ 分别是两个数组的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

相似题目：

• 1017. 负二进制转换

func addNegabinary(arr1 []int, arr2 []int) (ans []int) {
	i, j := len(arr1)-1, len(arr2)-1
	for c := 0; i >= 0 || j >= 0 || c != 0; i, j = i-1, j-1 {
		x := c
		if i >= 0 {
			x += arr1[i]
		}
		if j >= 0 {
			x += arr2[j]
		}
		c = 0
		if x >= 2 {
			x -= 2
			c -= 1
		} else if x == -1 {
			x = 1
			c += 1
		}
		ans = append(ans, x)
	}
	for len(ans) > 1 && ans[len(ans)-1] == 0 {
		ans = ans[:len(ans)-1]
	}
	for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return ans
}

力扣原题 · Doocs 题解来源

1085. 最小元素各数位之和 🔒

简单1 种解法

标签：数组、数学

题目、示例与约束

给你一个正整数的数组 A。

然后计算 S，使其等于数组 A 当中最小的那个元素各个数位上数字之和。

最后，假如 S 所得计算结果是 奇数 ，返回 0 ；否则请返回 1。

 

示例 1:

输入：[34,23,1,24,75,33,54,8]
输出：0
解释：
最小元素为 1 ，该元素各个数位上的数字之和 S = 1 ，是奇数所以答案为 0 。

示例 2：

输入：[99,77,33,66,55]
输出：1
解释：
最小元素为 33 ，该元素各个数位上的数字之和 S = 3 + 3 = 6 ，是偶数所以答案为 1 。

 

提示：

• 1 <= A.length <= 100
• 1 <= A[i] <= 100

方法一：模拟 · Go 实现

思考

只需最小值的数位和的奇偶：和为偶数返回 $1$，奇数返回 $0$。先线性找最小，再按位取模累加。

数位和 $s$ 的最低位即奇偶， $s\mathrm{\&}1$ 为 $1$ 时返回 $0$，因此答案为 $s\mathrm{\&}1\oplus 1$。

不必把数字转成字符串。

我们先找到数组中的最小值，记为 $x$。然后计算 $x$ 的各个数位上的数字之和，记为 $s$。最后判断 $s$ 是否为奇数，若是则返回 $0$，否则返回 $1$。

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

func sumOfDigits(nums []int) int {
	s := 0
	for x := slices.Min(nums); x > 0; x /= 10 {
		s += x % 10
	}
	return s&1 ^ 1
}

力扣原题 · Doocs 题解来源

1093. 大样本统计

中等1 种解法

标签：数组、数学、概率与统计

题目、示例与约束

我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。

计算以下统计数据:

• minimum ：样本中的最小元素。
• maximum ：样品中的最大元素。
• mean ：样本的平均值，计算为所有元素的总和除以元素总数。
• median ：
  • 如果样本的元素个数是奇数，那么一旦样本排序后，中位数 median 就是中间的元素。
  • 如果样本中有偶数个元素，那么中位数median 就是样本排序后中间两个元素的平均值。
• mode ：样本中出现次数最多的数字。保众数是 唯一 的。

以浮点数数组的形式返回样本的统计信息 [minimum, maximum, mean, median, mode] 。与真实答案误差在 10-5 内的答案都可以通过。

 

示例 1：

输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,3.00000,2.37500,2.50000,3.00000]
解释：用count表示的样本为[1,2,2,2,3,3,3,3]。
最小值和最大值分别为1和3。
均值是(1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375。
因为样本的大小是偶数，所以中位数是中间两个元素2和3的平均值，也就是2.5。
众数为3，因为它在样本中出现的次数最多。

示例 2：

输入：count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,4.00000,2.18182,2.00000,1.00000]
解释：用count表示的样本为[1,1,1,1,2,2,3,3,3,4,4]。
最小值为1，最大值为4。
平均数是(1+1+1+1+2+2+2+3+3+4+4)/ 11 = 24 / 11 = 2.18181818…(为了显示，输出显示了整数2.18182)。
因为样本的大小是奇数，所以中值是中间元素2。
众数为1，因为它在样本中出现的次数最多。

 

提示：

• count.length == 256
• 0 <= count[i] <= 109
• 1 <= sum(count) <= 109
•  count 的众数是 唯一 的

方法一：模拟 · Go 实现

思考

样本以 $0..255$ 的频次给出，总数可达 ${10}^9$，不能展开。最小、最大、和、众数都可以在扫频次数组时得到；中位数则要按累计频次定位第 $k$ 个元素。

一遍扫描更新 $mi,mx,s,cnt$ 以及频次最大的 $\mathit{\text{mode}}$。find(i) 沿 count 累加直到达到第 $i$ 个样本。

总数为奇数取正中一个，偶数取中间两个的平均，再与均值 $s/cnt$ 一起返回。

我们直接根据题目描述模拟即可，定义以下变量：

• 变量 $mi$ 表示最小值；
• 变量 $mx$ 表示最大值；
• 变量 $s$ 表示总和；
• 变量 $cnt$ 表示总个数；
• 变量 $mode$ 表示众数。

我们遍历数组 $count$，对于当前遍历到的数字 $count[k]$，如果 $count[k]>0$，那么我们做以下更新操作：

• 更新 $mi=min(mi,k)$；
• 更新 $mx=max(mx,k)$；
• 更新 $s=s+k\times count[k]$；
• 更新 $cnt=cnt+count[k]$；
• 如果 $count[k]>count[mode]$，那么更新 $mode=k$。

遍历结束后，我们再根据 $cnt$ 的奇偶性来计算中位数 $median$，如果 $cnt$ 是奇数，那么中位数就是第 $\lfloor \frac{cnt}{2}\rfloor +1$ 个数字，如果 $cnt$ 是偶数，那么中位数就是第 $\lfloor \frac{cnt}{2}\rfloor$ 和第 $\lfloor \frac{cnt}{2}\rfloor +1$ 个数字的平均值。

这里我们通过一个简单的辅助函数 $find(i)$ 来找到第 $i$ 个数字，具体实现可以参考下面的代码。

最后，我们将 $mi,mx,\frac{s}{cnt},median,mode$ 放入答案数组中返回即可。

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

func sampleStats(count []int) []float64 {
	find := func(i int) int {
		for k, t := 0, 0; ; k++ {
			t += count[k]
			if t >= i {
				return k
			}
		}
	}
	mi, mx := 1<<30, -1
	s, cnt, mode := 0, 0, 0
	for k, x := range count {
		if x > 0 {
			mi = min(mi, k)
			mx = max(mx, k)
			s += k * x
			cnt += x
			if x > count[mode] {
				mode = k
			}
		}
	}
	var median float64
	if cnt&1 == 1 {
		median = float64(find(cnt/2 + 1))
	} else {
		median = float64(find(cnt/2)+find(cnt/2+1)) / 2
	}
	return []float64{float64(mi), float64(mx), float64(s) / float64(cnt), median, float64(mode)}
}

力扣原题 · Doocs 题解来源

1103. 分糖果 II

简单1 种解法

标签：数学、模拟

题目、示例与约束

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

 

示例 1：

输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：

输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。

 

提示：

• 1 <= candies <= 10^9
• 1 <= num_people <= 1000

方法一：模拟 · Go 实现

思考

第 $i$ 次（从 $0$ 计）应发给第 $imod\mathit{\text{num\_people}}$ 个人 $min(\mathit{\text{candies}},i+1)$ 颗糖。发放次数由三角数决定，约为 $\sqrt{2\cdot \mathit{\text{candies}}}$，直接模拟即可在约束内结束。

无需对整轮发放推导闭式：每次用剩余糖数截断，糖发完即停。

我们可以直接模拟每一个人分到糖果的过程，按照题目描述的规则模拟即可。

时间复杂度 $O(max(\sqrt{candies},num\mathrm{\_}people))$，空间复杂度 $O(num\mathrm{\_}people)$。其中 $candies$ 为糖果数量。

func distributeCandies(candies int, num_people int) []int {
	ans := make([]int, num_people)
	for i := 0; candies > 0; i++ {
		ans[i%num_people] += min(candies, i+1)
		candies -= min(candies, i+1)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1118. 一月有多少天 🔒

简单1 种解法

标签：数学

题目、示例与约束

指定年份 year 和月份 month，返回 该月天数 。

 

示例 1：

输入：year = 1992, month = 7
输出：31

示例 2：

输入：year = 2000, month = 2
输出：29

示例 3：

输入：year = 1900, month = 2
输出：28

 

提示：

• 1583 <= year <= 2100
• 1 <= month <= 12

方法一：判断闰年 · Go 实现

思考

各月天数固定，唯一随年份变化的是二月。用「能被 $4$ 整除但不能被 $100$ 整除，或能被 $400$ 整除」判定闰年，据此写入二月天数后查表即可，无需枚举该月每一天。

我们可以先判断给定的年份是否为闰年，如果年份能被 $4$ 整除但不能被 $100$ 整除，或者能被 $400$ 整除，那么这一年就是闰年。

闰年的二月有 $29$ 天，平年的二月有 $28$ 天。

我们可以用一个数组 $days$ 存储当前年份每个月的天数，其中 $days[0]=0$， $days[i]$ 表示当前年份第 $i$ 个月的天数。那么答案就是 $days[month]$。

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

func numberOfDays(year int, month int) int {
	leap := (year%4 == 0 && year%100 != 0) || (year%400 == 0)
	x := 28
	if leap {
		x = 29
	}
	days := []int{0, 31, x, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
	return days[month]
}

力扣原题 · Doocs 题解来源

1131. 绝对值表达式的最大值

中等1 种解法

标签：数组、数学

题目、示例与约束

给你两个长度相等的整数数组，返回下面表达式的最大值：

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

其中下标 i，j 满足 0 <= i, j < arr1.length。

 

示例 1：

输入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
输出：13

示例 2：

输入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
输出：20

 

提示：

• 2 <= arr1.length == arr2.length <= 40000
• -10^6 <= arr1[i], arr2[i] <= 10^6

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

思考

表达式含两层绝对值，直接枚举 $i,j$ 为平方级。去掉绝对值后， $|x_i-x_j|+|y_i-y_j|+|i-j|$ 化为四种符号组合下 $(ax+by+\mathit{\text{下标}})$ 的极差。

对 $a,b\in \{\pm 1\}$ 各扫一遍维护最大最小，答案取所有极差的最大者，线性即可。

我们不妨令 $x_i=arr1[i]$, $y_i=arr2[i]$，由于 $i$ 和 $j$ 的大小关系不影响表达式的值，我们不妨假设 $i\ge j$，那么表达式可以变为：

$$\begin{gathered} |x_i-x_j|+|y_i-y_j|+i-j=max\{\begin{array}{l}(x_i+y_i)-(x_j+y_j)\\ (x_i-y_i)-(x_j-y_j)\\ (-x_i+y_i)-(-x_j+y_j)\\ (-x_i-y_i)-(-x_j-y_j)\end{array}+i-j \\ =max\{\begin{array}{l}(x_i+y_i+i)-(x_j+y_j+j)\\ (x_i-y_i+i)-(x_j-y_j+j)\\ (-x_i+y_i+i)-(-x_j+y_j+j)\\ (-x_i-y_i+i)-(-x_j-y_j+j)\end{array} \end{gathered}$$

因此，我们只要求出 $a\times x_i+b\times y_i+i$ 的最大值 $mx$，以及最小值 $mi$，其中 $a,b\in \{-1,1\}$。那么答案就是所有 $mx-mi$ 中的最大值。

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

相似题目：

• 1330. 翻转子数组得到最大的数组值

func maxAbsValExpr(arr1 []int, arr2 []int) int {
	dirs := [5]int{1, -1, -1, 1, 1}
	const inf = 1 << 30
	ans := -inf
	for k := 0; k < 4; k++ {
		a, b := dirs[k], dirs[k+1]
		mx, mi := -inf, inf
		for i, x := range arr1 {
			y := arr2[i]
			mx = max(mx, a*x+b*y+i)
			mi = min(mi, a*x+b*y+i)
			ans = max(ans, mx-mi)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1134. 阿姆斯特朗数 🔒

简单1 种解法

标签：数学

题目、示例与约束

给你一个整数 n ，让你来判定他是否是 阿姆斯特朗数，是则返回 true，不是则返回 false。

假设存在一个 k 位数 n ，其每一位上的数字的 k 次幂的总和也是 n ，那么这个数是阿姆斯特朗数 。

 

示例 1：

输入：n = 153
输出：true
解释： 
153 是一个 3 位数，且 153 = 13 + 53 + 33。

示例 2：

输入：n = 123
输出：false
解释：123 是一个 3 位数，且 123 != 13 + 23 + 33 = 36。

 

提示：

• 1 <= n <= 108

方法一：模拟 · Go 实现

思考

阿姆斯壮数要求各位数字的 $k$ 次幂之和等于自身， $k$ 为位数。先由十进制长度得 $k$，再反复取模累加幂次并整除缩小，最后与原数比较。位数很少，直接模拟即可。

我们可以先计算出数字的位数 $k$，然后计算每一位上的数字的 $k$ 次幂的总和 $s$，最后判断 $s$ 是否等于 $n$ 即可。

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

func isArmstrong(n int) bool {
	k := 0
	for x := n; x > 0; x /= 10 {
		k++
	}
	s := 0
	for x := n; x > 0; x /= 10 {
		s += int(math.Pow(float64(x%10), float64(k)))
	}
	return s == n
}

力扣原题 · Doocs 题解来源

1154. 一年中的第几天

简单1 种解法

标签：数学、字符串

题目、示例与约束

给你一个字符串 date ，按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。

 

示例 1：

输入：date = "2019-01-09"
输出：9
解释：给定日期是2019年的第九天。

示例 2：

输入：date = "2019-02-10"
输出：41

 

提示：

• date.length == 10
• date[4] == date[7] == '-'，其他的 date[i] 都是数字
• date 表示的范围从 1900 年 1 月 1 日至 2019 年 12 月 31 日

方法一：直接计算 · Go 实现

思考

年内序号是此前各月天数之和再加日。拆出年、月、日后按闰年规则确定二月天数，累加 $days[0..m-2]$ 与 $d$ 即可，不必构造完整日期对象。

根据题意，给定的日期是公元纪年法的日期，因此可以直接计算出该日期是当年的第几天。

首先，根据给定的日期计算出年月日，分别为 $y$, $m$, $d$。

然后，根据公元纪年法的闰年规则，计算出当年二月份的天数，闰年的二月份有 $29$ 天，平年的二月份有 $28$ 天。

闰年的计算规则是：年份能被 $400$ 整除，或者年份能被 $4$ 整除且不能被 $100$ 整除。

最后，根据给定的日期计算出当年的第几天，即把前面每个月的天数累加起来，再加上当月的天数即可。

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

func dayOfYear(date string) (ans int) {
	var y, m, d int
	fmt.Sscanf(date, "%d-%d-%d", &y, &m, &d)
	days := []int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
	if y%400 == 0 || (y%4 == 0 && y%100 != 0) {
		days[1] = 29
	}
	ans += d
	for _, v := range days[:m-1] {
		ans += v
	}
	return
}

力扣原题 · Doocs 题解来源

1175. 质数排列

简单1 种解法

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

题目、示例与约束

请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。

让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。

由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。

 

示例 1：

输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。

示例 2：

输入：n = 100
输出：682289015

 

提示：

• 1 <= n <= 100

方法一：数学 · Go 实现

思考

质数只能放在质数下标，合数只能放在合数下标，方案数为 $cnt!\times (n-cnt)!$。 $n\le 100$，用埃氏筛一次得到 $[1,n]$ 内质数个数，再算两个阶乘并取模。

先统计 $[1,n]$ 范围内的质数个数，我们记为 $cnt$。然后求 $cnt$ 以及 $n-cnt$ 阶乘的乘积得到答案，注意取模操作。

这里我们用“埃氏筛”统计质数。

如果 $x$ 是质数，那么大于 $x$ 的 $x$ 的倍数 $2x$,$3x$,… 一定不是质数，因此我们可以从这里入手。

设 $primes[i]$ 表示数 $i$ 是不是质数，如果是质数则为 $true$，否则为 $false$。

我们在 $[2,n]$ 范围内顺序遍历每个数 $i$，如果这个数为质数，质数个数增 $1$，然后将其所有的倍数 $j$ 都标记为合数（除了该质数本身），即 $primes[j]=false$，这样在运行结束的时候我们即能知道质数的个数。

时间复杂度 $O(n\times \log \log n)$。

func numPrimeArrangements(n int) int {
	count := func(n int) int {
		cnt := 0
		primes := make([]bool, n+1)
		for i := range primes {
			primes[i] = true
		}
		for i := 2; i <= n; i++ {
			if primes[i] {
				cnt++
				for j := i + i; j <= n; j += i {
					primes[j] = false
				}
			}
		}
		return cnt
	}

	mod := int(1e9) + 7
	f := func(n int) int {
		ans := 1
		for i := 2; i <= n; i++ {
			ans = (ans * i) % mod
		}
		return ans
	}

	cnt := count(n)
	ans := f(cnt) * f(n-cnt)
	return ans % mod
}

力扣原题 · Doocs 题解来源

1180. 统计只含单一字母的子串 🔒

简单2 种解法

标签：数学、字符串

题目、示例与约束

给你一个字符串 s，返回 只含 单一字母 的子串个数 。

示例 1：

输入： s = "aaaba"
输出： 8
解释： 只含单一字母的子串分别是 "aaa"， "aa"， "a"， "b"。
"aaa" 出现 1 次。
"aa" 出现 2 次。
"a" 出现 4 次。
"b" 出现 1 次。
所以答案是 1 + 2 + 4 + 1 = 8。

示例 2:

输入： s = "aaaaaaaaaa"
输出： 55

 

提示：

• 1 <= s.length <= 1000
• s[i] 仅由小写英文字母组成

方法一：双指针 · Go 实现

思考

仅含一种字母的子串必落在一段连续相同字符内。长为 $L$ 的段贡献 $L(L+1)/2$ 个子串。双指针切出每段长度，按三角数累加，不必枚举全部 $O(n^2)$ 子串。

我们可以使用双指针，用指针 $i$ 指向当前子串的起始位置，指针 $j$ 向右移动到第一个与 $s[i]$ 不同的位置，那么 $[i,..j-1]$ 就是以 $s[i]$ 为唯一字母的子串，长度为 $j-i$，那么以 $s[i]$ 为唯一字母的子串的个数就是 $\frac{(j-i+1)(j-i)}{2}$，累加到答案中。然后令 $i=j$，继续遍历，直到 $i$ 超出字符串 $s$ 的范围。

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

func countLetters(s string) int {
	ans := 0
	for i, n := 0, len(s); i < n; {
		j := i
		for j < n && s[j] == s[i] {
			j++
		}
		ans += (1 + j - i) * (j - i) / 2
		i = j
	}
	return ans
}

方法二 · Go 实现

思考

方法一用闭式一次加上整段贡献。方法二在扩展段时用计数器 $1,2,\dots ,L$ 逐个累加，和仍为三角数，便于理解「以当前字符结尾的单字母子串」个数。

func countLetters(s string) (ans int) {
	i, n := 0, len(s)
	for i < n {
		j := i
		cnt := 0
		for j < n && s[j] == s[i] {
			j++
			cnt++
			ans += cnt
		}
		i = j
	}
	return
}

力扣原题 · Doocs 题解来源

1185. 一周中的第几天

简单1 种解法

标签：数学

题目、示例与约束

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。

注意：1971 年 1 月 1 日是星期五。

 

示例 1：

输入：day = 31, month = 8, year = 2019
输出："Saturday"

示例 2：

输入：day = 18, month = 7, year = 1999
输出："Sunday"

示例 3：

输入：day = 15, month = 8, year = 1993
输出："Sunday"

 

提示：

• 给出的日期一定是在 1971 到 2100 年之间的有效日期。

方法二：蔡勒公式 · Go 实现

思考

方法一依赖日期库。蔡勒公式用世纪、年后两位、月、日的整数运算直接得到星期，一月二月须当作上一年的十三、十四月。不引入外部日期类型。

我们可以使用蔡勒公式来计算星期几，蔡勒公式如下：

$$w=(\lfloor \frac{c}{4}\rfloor -2c+y+\lfloor \frac{y}{4}\rfloor +\lfloor \frac{13(m+1)}{5}\rfloor +d-1)mod7$$

其中：

• w: 星期（从 Sunday 开始）
• c: 年份前两位
• y: 年份后两位
• m: 月（m 的取值范围是 3 至 14，即在蔡勒公式中，某年的 1、2 月要看作上一年的 13、14 月来计算，比如 2003 年 1 月 1 日要看作 2002 年的 13 月 1 日来计算）
• d: 日
• ⌊⌋: 向下取整
• mod: 取余

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

func dayOfTheWeek(d int, m int, y int) string {
	if m < 3 {
		m += 12
		y -= 1
	}
	c := y / 100
	y %= 100
	w := (c/4 - 2*c + y + y/4 + 13*(m+1)/5 + d - 1) % 7
	weeks := []string{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}
	return weeks[(w+7)%7]
}

力扣原题 · Doocs 题解来源

1228. 等差数列中缺失的数字 🔒

简单2 种解法

标签：数组、数学

题目、示例与约束

在某个数组 arr 中，值符合等差数列的数值规律：在 0 <= i < arr.length - 1 的前提下，arr[i+1] - arr[i] 的值都相等。

我们会从该数组中删除一个 既不是第一个 也 不是最后一个的值，得到一个新的数组  arr。

给你这个缺值的数组 arr，返回 被删除的那个数 。

 

示例 1：

输入：arr = [5,7,11,13]
输出：9
解释：原来的数组是 [5,7,9,11,13]。

示例 2：

输入：arr = [15,13,12]
输出：14
解释：原来的数组是 [15,14,13,12]。

 

提示：

• 3 <= arr.length <= 1000
• 0 <= arr[i] <= 105
• 给定的数组 保证 是一个有效的数组。

方法一：等差数列求和公式 · Go 实现

思考

数组由等差数列删去一项得到， $n\le 1000$。完整数列有 $n+1$ 项，首末项已知，其和可由求和公式写出；与当前数组元素和之差即缺失项。一次求和即可，不必先求公差。

等差数列求和公式为 $\frac{(a_1+a_n)n}{2}$，其中 $n$ 为等差数列的项数，等差数列的首项为 $a_1$，末项为 $a_n$。

因为题目中给出的数组是一个等差数列，且缺失了一个数，所以数组的项数为 $n+1$，首项为 $a_1$，末项为 $a_n$，则数组的和为 $\frac{(a_1+a_n)(n+1)}{2}$。

因此，缺失的数为 $\frac{(a_1+a_n)(n+1)}{2}-\sum _{i=0}^n{a}_i$。

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

func missingNumber(arr []int) int {
	n := len(arr)
	x := (arr[0] + arr[n-1]) * (n + 1) / 2
	y := 0
	for _, v := range arr {
		y += v
	}
	return x - y
}

方法二：求公差 + 遍历 · Go 实现

思考

求和公式给出缺失值，但不经过公差。若先用首末项与长度求出 $d$，再扫描相邻差不等于 $d$ 的位置，即可在断点处还原缺失项；若全程相等则缺的是与各项相同的数。时间同为线性，过程更贴近数列定义。

因为题目中给出的数组是一个等差数列，且缺失了一个数，首项为 $a_1$，末项为 $a_n$，那么公差 $d=\frac{a_n-a_1}{n}$。

遍历数组，如果 $a_i\ne a_{i-1}+d$，则返回 $a_{i-1}+d$。

如果遍历完数组都没有找到缺失的数，说明数组的所有数都相等，直接返回数组的第一个数即可。

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

func missingNumber(arr []int) int {
	n := len(arr)
	d := (arr[n-1] - arr[0]) / n
	for i := 1; i < n; i++ {
		if arr[i] != arr[i-1]+d {
			return arr[i-1] + d
		}
	}
	return arr[0]
}

力扣原题 · Doocs 题解来源

1232. 缀点成线

简单1 种解法

标签：几何、数组、数学

题目、示例与约束

给定一个整数数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。

 

示例 1：

输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

示例 2：

输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

 

提示：

• 2 <= coordinates.length <= 1000
• coordinates[i].length == 2
• -104 <= coordinates[i][0], coordinates[i][1] <= 104
• coordinates 中不含重复的点

方法一：数学 · Go 实现

思考

共线当且仅当任意两点与第一点构成的向量平行。斜率比较会遇到竖直边与浮点误差。叉积 $(x-x_1)(y_2-y_1)=(y-y_1)(x_2-x_1)$ 避免除法。

取前两点为基准，对其余点检验该等式。 $n\le 1000$，一遍线性即可。点不重复，无需处理零向量。

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

func checkStraightLine(coordinates [][]int) bool {
	x1, y1 := coordinates[0][0], coordinates[0][1]
	x2, y2 := coordinates[1][0], coordinates[1][1]
	for i := 2; i < len(coordinates); i++ {
		x, y := coordinates[i][0], coordinates[i][1]
		if (x-x1)*(y2-y1) != (y-y1)*(x2-x1) {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

1250. 检查「好数组」

困难1 种解法

标签：数组、数学、最大公约数、数论、欧几里得算法、扩展欧几里得算法、裴蜀定理

题目、示例与约束

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

 

示例 1：

输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

输入：nums = [3,6]
输出：false

 

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

方法一：数学（裴蜀定理） · Go 实现

思考

裴蜀定理： $a_1{x}_1+\cdots +a_n{x}_n=1$ 有整数解当且仅当 $gcd(a_1,\dots ,a_n)=1$。 $n\le {10}^5$，不能枚举子集。

对全数组求一次最大公约数即可。任一互质子族存在时，全体的公约数也必为 $1$，故无需单独寻找那一组数。

我们先可以考虑选取两个数的情况，若选取的数是 $a$ 和 $b$，那么根据题目的要求，我们需要满足 $a\times x+b\times y=1$，其中 $x$ 和 $y$ 是任意整数。

根据裴蜀定理，可以得知，如果 $a$ 和 $b$ 互质，那么上述等式一定有解。实际上，裴蜀定理也可以推广到多个数的情况，即如果 $a_1,a_2,\cdots ,a_i$ 互质，那么 $a_1\times x_1+a_2\times x_2+\cdots +a_i\times x_i=1$ 一定有解，其中 $x_1,x_2,\cdots ,x_i$ 是任意整数。

因此，我们只需要判断在数组 nums 中是否存在 $i$ 个互质的数即可。两个数互质的充要条件是它们的最大公约数为 $1$。如果数组 nums 存在 $i$ 个互质的数，那么数组 nums 中的所有数的最大公约数也为 $1$。

所以我们将题目转化为：判断数组 nums 中的所有数的最大公约数是否为 $1$。遍历数组 nums，求出数组 nums 中的所有数的最大公约数即可。

时间复杂度 $O(n+logm)$，空间复杂度 $O(1)$，其中 $n$ 是数组 nums 的长度，而 $m$ 是数组 nums 中的最大值。

func isGoodArray(nums []int) bool {
	g := 0
	for _, x := range nums {
		g = gcd(x, g)
	}
	return g == 1
}

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

力扣原题 · Doocs 题解来源

1252. 奇数值单元格的数目

简单3 种解法

标签：数组、数学、模拟

题目、示例与约束

给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。

另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

对 indices[i] 所指向的每个位置，应同时执行下述增量操作：

1. ri 行上的所有单元格，加 1 。
2. ci 列上的所有单元格，加 1 。

给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。

 

示例 1：

输入：m = 2, n = 3, indices = [[0,1],[1,1]]
输出：6
解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。
第一次增量操作后得到 [[1,2,1],[0,1,0]]。
最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。

示例 2：

输入：m = 2, n = 2, indices = [[1,1],[0,0]]
输出：0
解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。

 

提示：

• 1 <= m, n <= 50
• 1 <= indices.length <= 100
• 0 <= ri < m
• 0 <= ci < n

 

进阶：你可以设计一个时间复杂度为 O(n + m + indices.length) 且仅用 O(n + m) 额外空间的算法来解决此问题吗？

方法一：模拟 · Go 实现

思考

$m,n\le 50$，可直接建矩阵并对每次操作把整行整列加一，最后数奇数。模拟忠实于题意，作为后续优化的参照。

我们创建一个矩阵 $g$ 来存放操作的结果。对于 $\mathit{\text{indices}}$ 中的每一对 $(r_i,c_i)$，我们将矩阵第 $r_i$ 行的所有数加 $1$，第 $c_i$ 列的所有元素加 $1$。

模拟结束后，遍历矩阵，统计奇数的个数。

时间复杂度 $O(k\times (m+n)+m\times n)$，空间复杂度 $O(m\times n)$。其中 $k$ 为 $\mathit{\text{indices}}$ 的长度。

func oddCells(m int, n int, indices [][]int) int {
	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
	}
	for _, e := range indices {
		r, c := e[0], e[1]
		for i := 0; i < m; i++ {
			g[i][c]++
		}
		for j := 0; j < n; j++ {
			g[r][j]++
		}
	}
	ans := 0
	for _, row := range g {
		for _, v := range row {
			ans += v % 2
		}
	}
	return ans
}

方法二：空间优化 · Go 实现

思考

方法一每次改 $O(m+n)$ 个格子，并占用整张表。格子 $(i,j)$ 的终值只是第 $i$ 行被点次数加第 $j$ 列被点次数。用两个一维数组记录行、列增量，最后枚举格子看奇偶，空间降为 $O(m+n)$。

我们可以使用行数组 $\mathit{\text{row}}$ 和列数组 $\mathit{\text{col}}$ 来记录每一行、每一列被增加的次数。对于 $\mathit{\text{indices}}$ 中的每一对 $(r_i,c_i)$，我们将 $\mathit{\text{row}}[r_i]$ 和 $\mathit{\text{col}}[c_i]$ 分别加 $1$。

操作结束后，可以算出 $(i,j)$ 位置的计数为 $\mathit{\text{row}}[i]+\mathit{\text{col}}[j]$。遍历矩阵，统计奇数的个数。

时间复杂度 $O(k+m\times n)$，空间复杂度 $O(m+n)$。其中 $k$ 为 $\mathit{\text{indices}}$ 的长度。

func oddCells(m int, n int, indices [][]int) int {
	row := make([]int, m)
	col := make([]int, n)
	for _, e := range indices {
		r, c := e[0], e[1]
		row[r]++
		col[c]++
	}
	ans := 0
	for _, i := range row {
		for _, j := range col {
			ans += (i + j) % 2
		}
	}
	return ans
}

方法三：数学优化 · Go 实现

思考

方法二仍枚举全部格子。 $(i,j)$ 为奇数当且仅当行增量与列增量一奇一偶。统计奇行数 $cnt1$、奇列数 $cnt2$，奇数个数为 $cnt1(n-cnt2)+cnt2(m-cnt1)$，时间降到 $O(k+m+n)$。

我们注意到，只有当 $\mathit{\text{row}}[i]$ 和 $\mathit{\text{col}}[j]$ 中恰好为“一奇一偶”时，矩阵 $(i,j)$ 位置的数才会是奇数。

我们统计 $\mathit{\text{row}}$ 中的奇数个数，记为 $\mathit{\text{cnt1}}$；而 $\mathit{\text{col}}$ 中的奇数个数，记为 $\mathit{\text{cnt2}}$。那么最终得到的奇数个数为 $\mathit{\text{cnt1}}\times (n-\mathit{\text{cnt2}})+\mathit{\text{cnt2}}\times (m-\mathit{\text{cnt1}})$。

时间复杂度 $O(k+m+n)$，空间复杂度 $O(m+n)$。其中 $k$ 为 $\mathit{\text{indices}}$ 的长度。

func oddCells(m int, n int, indices [][]int) int {
	row := make([]int, m)
	col := make([]int, n)
	for _, e := range indices {
		r, c := e[0], e[1]
		row[r]++
		col[c]++
	}
	cnt1, cnt2 := 0, 0
	for _, v := range row {
		cnt1 += v % 2
	}
	for _, v := range col {
		cnt2 += v % 2
	}
	return cnt1*(n-cnt2) + cnt2*(m-cnt1)
}

力扣原题 · Doocs 题解来源

1266. 访问所有点的最小时间

简单1 种解法

标签：几何、数组、数学

题目、示例与约束

平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi] 。请你计算访问所有这些点需要的 最小时间（以秒为单位）。

你需要按照下面的规则在平面上移动：

• 每一秒内，你可以：
  • 沿水平方向移动一个单位长度，或者
  • 沿竖直方向移动一个单位长度，或者
  • 跨过对角线移动 sqrt(2) 个单位长度（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
• 必须按照数组中出现的顺序来访问这些点。
• 在访问某个点时，可以经过该点后面出现的点，但经过的那些点不算作有效访问。

 

示例 1：

输入：points = [[1,1],[3,4],[-1,0]]
输出：7
解释：一条最佳的访问路径是： [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
从 [1,1] 到 [3,4] 需要 3 秒 
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒

示例 2：

输入：points = [[3,2],[-2,2]]
输出：5

 

提示：

• points.length == n
• 1 <= n <= 100
• points[i].length == 2
• -1000 <= points[i][0], points[i][1] <= 1000

方法一：模拟 · Go 实现

思考

平面上每秒可走八个方向，相邻点之间最短时间是切比雪夫距离 $max(|\mathrm{\Delta }x|,|\mathrm{\Delta }y|)$：对角一步同时消耗两个方向的差距。点按给定顺序访问，总时间即相邻切比雪夫距离之和。 $n\le 100$，线性累加即可。

对于两个点 $p_1=(x_1,y_1)$ 和 $p_2=(x_2,y_2)$，横坐标和纵坐标分别移动的距离分别为 $d_x=|x_1-x_2|$ 和 $d_y=|y_1-y_2|$。

如果 $d_x\ge d_y$，则沿对角线移动 $d_y$，再沿水平方向移动 $d_x-d_y$；如果 $d_x<d_y$，则沿对角线移动 $d_x$，再沿竖直方向移动 $d_y-d_x$。因此，两个点之间的最短距离为 $max(d_x,d_y)$。

我们可以遍历所有的点对，计算出每个点对之间的最短距离，然后求和即可。

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

func minTimeToVisitAllPoints(points [][]int) (ans int) {
	for i, p := range points[1:] {
		dx := abs(p[0] - points[i][0])
		dy := abs(p[1] - points[i][1])
		ans += max(dx, dy)
	}
	return
}

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

力扣原题 · Doocs 题解来源

1271. 十六进制魔术数字 🔒

简单1 种解法

标签：数学、字符串

题目、示例与约束

你有一个十进制数字，请按照此规则将它变成「十六进制魔术数字」：首先将它变成字母大写的十六进制字符串，然后将所有的数字 0 变成字母 O ，将数字 1  变成字母 I 。

如果一个数字在转换后只包含 {"A", "B", "C", "D", "E", "F", "I", "O"} ，那么我们就认为这个转换是有效的。

给你一个字符串 num ，它表示一个十进制数 N，如果它的十六进制魔术数字转换是有效的，请返回转换后的结果，否则返回 "ERROR" 。

 

示例 1：

输入：num = "257"
输出："IOI"
解释：257 的十六进制表示是 101 。

示例 2：

输入：num = "3"
输出："ERROR"

 

提示：

• 1 <= N <= 10^12
• 给定字符串不会有前导 0 。
• 结果中的所有字母都应该是大写字母。

方法一：模拟 · Go 实现

思考

把十进制数写成十六进制，再把 $0,1$ 换成 $O,I$，其余数字则非法。 $N$ 达 ${10}^{12}$，先 $hex$ 再替换并检查字符是否都在 $ABCDEFIO$。模拟即题意。

将数字转换为十六进制字符串，然后遍历字符串，将数字 $0$ 转换为字母 $O$，将数字 $1$ 转换为字母 $I$，最后判断转换后的字符串是否合法。

时间复杂度 $O(\log n)$，其中 $n$ 为 $num$ 所表示的十进制数字的大小。

func toHexspeak(num string) string {
	x, _ := strconv.Atoi(num)
	t := strings.ToUpper(fmt.Sprintf("%x", x))
	t = strings.ReplaceAll(t, "0", "O")
	t = strings.ReplaceAll(t, "1", "I")
	for _, c := range t {
		if c >= '2' && c <= '9' {
			return "ERROR"
		}
	}
	return t
}

力扣原题 · Doocs 题解来源

1276. 不浪费原料的汉堡制作方案

中等1 种解法

标签：数学

题目、示例与约束

圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。

给你两个整数 tomatoSlices 和 cheeseSlices，分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下：

• 巨无霸汉堡：4 片番茄和 1 片奶酪
• 小皇堡：2 片番茄和 1 片奶酪

请你以 [total_jumbo, total_small]（[巨无霸汉堡总数，小皇堡总数]）的格式返回恰当的制作方案，使得剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量都是 0。

如果无法使剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量为 0，就请返回 []。

 

示例 1：

输入：tomatoSlices = 16, cheeseSlices = 7
输出：[1,6]
解释：制作 1 个巨无霸汉堡和 6 个小皇堡需要 4*1 + 2*6 = 16 片番茄和 1 + 6 = 7 片奶酪。不会剩下原料。

示例 2：

输入：tomatoSlices = 17, cheeseSlices = 4
输出：[]
解释：只制作小皇堡和巨无霸汉堡无法用光全部原料。

示例 3：

输入：tomatoSlices = 4, cheeseSlices = 17
输出：[]
解释：制作 1 个巨无霸汉堡会剩下 16 片奶酪，制作 2 个小皇堡会剩下 15 片奶酪。

示例 4：

输入：tomatoSlices = 0, cheeseSlices = 0
输出：[0,0]

示例 5：

输入：tomatoSlices = 2, cheeseSlices = 1
输出：[0,1]

 

提示：

• 0 <= tomatoSlices <= 10^7
• 0 <= cheeseSlices <= 10^7

方法一：数学 · Go 实现

思考

巨无霸用 $4$ 番茄 $1$ 奶酪，小皇堡用 $2$ 番茄 $1$ 奶酪，且须用尽。两个方程两个未知数，解出非负整数解即可。番茄数为 ${10}^7$，枚举一种汉堡不可行，闭式解 $O(1)$。

我们设巨无霸汉堡数量为 $x$，小皇堡数量为 $y$，则有：

$$\begin{array}{rl}4x+2y& =tomatoSlices\\ x+y& =cheeseSlices\end{array}$$

将上述两式转换，可以得到：

$$\begin{array}{r}y=(4\times cheeseSlices-tomatoSlices)/2\\ x=cheeseSlices-y\end{array}$$

其中 $x$ 和 $y$ 必须为非负整数。

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

func numOfBurgers(tomatoSlices int, cheeseSlices int) []int {
	k := 4*cheeseSlices - tomatoSlices
	y := k / 2
	x := cheeseSlices - y
	if k%2 != 0 || x < 0 || y < 0 {
		return []int{}
	}
	return []int{x, y}
}

力扣原题 · Doocs 题解来源

1281. 整数的各位积和之差

简单1 种解法

标签：数学

题目、示例与约束

给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。

 

示例 1：

输入：n = 234
输出：15 
解释：
各位数之积 = 2 * 3 * 4 = 24 
各位数之和 = 2 + 3 + 4 = 9 
结果 = 24 - 9 = 15

示例 2：

输入：n = 4421
输出：21
解释： 
各位数之积 = 4 * 4 * 2 * 1 = 32 
各位数之和 = 4 + 4 + 2 + 1 = 11 
结果 = 32 - 11 = 21

 

提示：

• 1 <= n <= 10^5

方法一：模拟 · Go 实现

思考

$n\le {10}^5$，逐位取模即可同时累乘与累加，最后相减。不必转成字符串。循环次数为位数。

我们用两个变量 $x$ 和 $y$ 分别记录各位数之积、各位数之和，初始时 $x=1,y=0$。

当 $n>0$ 时，每次将 $n$ 对 $10$ 取模得到当前位的数字 $v$，并将 $n$ 除以 $10$ 后继续进行下一次循环。在每次循环中，我们更新 $x=x\times v$, $y=y+v$。

最终，我们返回 $x-y$ 即可。

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

func subtractProductAndSum(n int) int {
	x, y := 1, 0
	for ; n > 0; n /= 10 {
		v := n % 10
		x *= v
		y += v
	}
	return x - y
}

力扣原题 · Doocs 题解来源

1295. 统计位数为偶数的数字

简单1 种解法

标签：数组、数学

题目、示例与约束

给你一个整数数组 nums，请你返回其中包含 偶数 个数位的数字的个数。

 

示例 1：

输入：nums = [12,345,2,6,7896]
输出：2
解释：
12 是 2 位数字（位数为偶数） 
345 是 3 位数字（位数为奇数）  
2 是 1 位数字（位数为奇数） 
6 是 1 位数字 位数为奇数） 
7896 是 4 位数字（位数为偶数）  
因此只有 12 和 7896 是位数为偶数的数字

示例 2：

输入：nums = [555,901,482,1771]
输出：1 
解释： 
只有 1771 是位数为偶数的数字。

 

提示：

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 105

方法一：模拟 · Go 实现

思考

$n\le 500$，把每个数转成十进制字符串看长度奇偶即可。位数也可反复除 $10$ 得到，字符串写法更短。

我们遍历数组 $\mathit{\text{nums}}$ 中的每个元素，对于当前遍历到的元素 $x$，我们直接将其转换为字符串，然后判断其长度是否为偶数即可。若是则将答案加一。

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

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

func findNumbers(nums []int) (ans int) {
	for _, x := range nums {
		if len(strconv.Itoa(x))%2 == 0 {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1304. 和为零的 N 个不同整数

简单2 种解法

标签：数组、数学

题目、示例与约束

给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。

 

示例 1：

输入：n = 5
输出：[-7,-1,1,3,4]
解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。

示例 2：

输入：n = 3
输出：[-1,0,1]

示例 3：

输入：n = 1
输出：[0]

 

提示：

• 1 <= n <= 1000

方法一：构造 · Go 实现

思考

需要 $n$ 个互不相同且和为 $0$ 的整数。随机选取后再调整容易破坏互异性。互为相反数的一对已经和为 $0$，因此放入 $1,-1,\dots ,k,-k$。若 $n$ 为奇数，再补一个 $0$，和与互异性同时成立。

我们可以从 $1$ 开始，依次将正数和负数交替放入结果数组中，一共循环 $\frac{n}{2}$ 次，如果 $n$ 为奇数，则最后再将 $0$ 放入结果数组中。

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

func sumZero(n int) []int {
	ans := make([]int, n)
	for i, j := 1, 0; i <= n/2; i, j = i+1, j+1 {
		ans[j] = i
		j++
		ans[j] = -i
	}
	return ans
}

方法二：构造 + 数学 · Go 实现

思考

成对构造需要处理奇偶。将 $1$ 到 $n-1$ 直接放入，最后一项取前 $n-1$ 项之和的相反数，和必为 $0$，且该项不等于已有任一正整数。写法更短，仍保证互异。

我们也可以将 $1$ 到 $n-1$ 的所有整数放入结果数组中，最后再把前 $n-1$ 个整数的和 $\frac{n(n-1)}{2}$ 的相反数放入结果数组中。

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

func sumZero(n int) []int {
	ans := make([]int, n)
	for i := 1; i < n; i++ {
		ans[i] = i
	}
	ans[0] = -n * (n - 1) / 2
	return ans
}

力扣原题 · Doocs 题解来源

1317. 将整数转换为两个无零整数的和

简单2 种解法

标签：数学

题目、示例与约束

「无零整数」是十进制表示中 不含任何 0 的正整数。

给你一个整数 n，请你返回一个 由两个整数组成的列表 [a, b]，满足：

• a 和 b 都是无零整数
• a + b = n

题目数据保证至少有一个有效的解决方案。

如果存在多个有效解决方案，你可以返回其中任意一个。

 

示例 1：

输入：n = 2
输出：[1,1]
解释：a = 1, b = 1。a + b = n 并且 a 和 b 的十进制表示形式都不包含任何 0。

示例 2：

输入：n = 11
输出：[2,9]

示例 3：

输入：n = 10000
输出：[1,9999]

示例 4：

输入：n = 69
输出：[1,68]

示例 5：

输入：n = 1010
输出：[11,999]

 

提示：

• 2 <= n <= 104

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

思考

$n\le {10}^4$，满足 $a+b=n$ 且十进制均不含 $0$ 的拆分一定存在。从 $a=1$ 递增，令 $b=n-a$，把两数拼成字符串检查是否出现 '0'，第一次命中即可返回。

从 $1$ 开始枚举 $a$，那么 $b=n-a$。对于每个 $a$ 和 $b$，我们将它们转换为字符串并且连接起来，然后判断是否包含字符 '0'，如果不包含，那么就找到了答案，返回 $[a,b]$。

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

func getNoZeroIntegers(n int) []int {
	for a := 1; ; a++ {
		b := n - a
		if !strings.Contains(strconv.Itoa(a)+strconv.Itoa(b), "0") {
			return []int{a, b}
		}
	}
}

方法二：直接枚举（另一种写法） · Go 实现

思考

方法一借助字符串拼接判断零。改为对 $a$、 $b$ 分别除十检查余数，避免构造字符串，额外空间降为常数，枚举顺序不变。

在方法一中，我们将 $a$ 和 $b$ 转换为字符串并且连接起来，然后判断是否包含字符 '0'。这里我们可以通过一个函数 $f(x)$ 来判断 $x$ 是否包含字符 '0'，然后直接枚举 $a$，判断 $a$ 和 $b=n-a$ 是否都不包含字符 '0'，如果是，则找到了答案，返回 $[a,b]$。

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

func getNoZeroIntegers(n int) []int {
	f := func(x int) bool {
		for ; x > 0; x /= 10 {
			if x%10 == 0 {
				return false
			}
		}
		return true
	}
	for a := 1; ; a++ {
		b := n - a
		if f(a) && f(b) {
			return []int{a, b}
		}
	}
}

力扣原题 · Doocs 题解来源

1344. 时钟指针的夹角

中等1 种解法

标签：数学

题目、示例与约束

给你两个数 hour 和 minutes 。请你返回在时钟上，由给定时间的时针和分针组成的较小角的角度（60 单位制）。

 

示例 1：

输入：hour = 12, minutes = 30
输出：165

示例 2：

输入：hour = 3, minutes = 30
输出；75

示例 3：

输入：hour = 3, minutes = 15
输出：7.5

示例 4：

输入：hour = 4, minutes = 50
输出：155

示例 5：

输入：hour = 12, minutes = 0
输出：0

 

提示：

• 1 <= hour <= 12
• 0 <= minutes <= 59
• 与标准答案误差在 10^-5 以内的结果都被视为正确结果。

方法一：数学 · Go 实现

思考

时钟上时针、分针的较小夹角。时针同时受小时与分钟影响：每小时 ${30}^{\circ }$，每分钟再偏 ${0.5}^{\circ }$；分针每分钟 $6^{\circ }$。两者差的绝对值与 ${360}^{\circ }$ 减去该差取较小者，即为劣角。

时针每小时移动 30 度，每分钟移动 0.5 度。分针每分钟移动 6 度。如果指针之间的夹角大于 180 度，则取其与 360 度的差值，以确保获得最小的夹角。

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

func angleClock(hour int, minutes int) float64 {
	h := 30*float64(hour) + 0.5*float64(minutes)
	m := 6 * float64(minutes)
	diff := math.Abs(h - m)
	return math.Min(diff, 360-diff)
}

力扣原题 · Doocs 题解来源

1360. 日期之间隔几天

简单1 种解法

标签：数学、字符串

题目、示例与约束

请你编写一个程序来计算两个日期之间隔了多少天。

日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。

 

示例 1：

输入：date1 = "2019-06-29", date2 = "2019-06-30"
输出：1

示例 2：

输入：date1 = "2020-01-15", date2 = "2019-12-31"
输出：15

 

提示：

• 给定的日期是 1971 年到 2100 年之间的有效日期。

方法一：数学 · Go 实现

思考

两个合法日期相差的天数。直接按月累加容易漏闰年。把两天都换成距 $1971$-$01$-$01$ 的天数：先按年累加 $365$ 或 $366$，再按月查表（二月视闰年），最后加日，两者相减取绝对。

我们先定义一个函数 isLeapYear(year) 来判断给定的年份 year 是否是闰年，如果是闰年则返回 true，否则返回 false。

接下来，我们再定义一个函数 daysInMonth(year, month) 来计算给定的年份 year 和月份 month 一共有多少天，我们可以使用一个数组 days 来存储每个月份的天数，其中 days[1] 表示二月份的天数，如果是闰年则为 $29$ 天，否则为 $28$ 天。

然后，我们再定义一个函数 calcDays(date) 来计算给定的日期 date 距离 1971-01-01 有多少天，我们可以使用 date.split("-") 来将日期 date 按照 - 分割成年份 year、月份 month 和日期 day，然后我们可以使用一个循环来计算从 1971 年到 year 年一共有多少天，然后再计算从 1 月到 month 月一共有多少天，最后再加上 day 天即可。

最后，我们只需要返回 calcDays(date1) - calcDays(date2) 的绝对值即可。

时间复杂度 $O(y+m)$，其中 $y$ 表示给定的日期距离 1971-01-01 的年数，而 $m$ 表示给定的日期的月数。空间复杂度 $O(1)$。

func daysBetweenDates(date1 string, date2 string) int {
	return abs(calcDays(date1) - calcDays(date2))
}

func isLeapYear(year int) bool {
	return year%4 == 0 && (year%100 != 0 || year%400 == 0)
}

func daysInMonth(year, month int) int {
	days := [12]int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
	if isLeapYear(year) {
		days[1] = 29
	}
	return days[month-1]
}

func calcDays(date string) int {
	year, _ := strconv.Atoi(date[:4])
	month, _ := strconv.Atoi(date[5:7])
	day, _ := strconv.Atoi(date[8:])
	days := 0
	for y := 1971; y < year; y++ {
		days += 365
		if isLeapYear(y) {
			days++
		}
	}
	for m := 1; m < month; m++ {
		days += daysInMonth(year, m)
	}
	days += day
	return days
}

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

力扣原题 · Doocs 题解来源

1362. 最接近的因数

中等1 种解法

标签：数学、质因数分解

题目、示例与约束

给你一个整数 num，请你找出同时满足下面全部要求的两个整数：

• 两数乘积等于  num + 1 或 num + 2
• 以绝对差进行度量，两数大小最接近

你可以按任意顺序返回这两个整数。

 

示例 1：

输入：num = 8
输出：[3,3]
解释：对于 num + 1 = 9，最接近的两个因数是 3 & 3；对于 num + 2 = 10, 最接近的两个因数是 2 & 5，因此返回 3 & 3 。

示例 2：

输入：num = 123
输出：[5,25]

示例 3：

输入：num = 999
输出：[40,25]

 

提示：

• 1 <= num <= 10^9

方法一：枚举 · Go 实现

思考

找乘积为 $num+1$ 或 $num+2$ 的一对因数，使二者差最小。 $num\le {10}^9$，不能从 $1$ 扫到 $x$。差最小的一对必在 $\sqrt{x}$ 附近，故从 $\lfloor \sqrt{x}\rfloor$ 向下找第一个整除者。对 $num+1$ 与 $num+2$ 各求一对，取差更小者。

我们设计一个函数 $f(x)$，该函数返回乘积等于 $x$ 的两个数，且这两个数的差的绝对值最小。我们可以从 $\sqrt{x}$ 开始枚举 $i$，如果 $x$ 能被 $i$ 整除，那么 $\frac{x}{i}$ 就是另一个因数，此时我们就找到了一个乘积等于 $x$ 的两个因数，我们将其返回即可。否则我们减小 $i$ 的值，继续枚举。

接下来，我们只需要分别计算 $f(num+1)$ 和 $f(num+2)$，然后比较两个函数的返回值，返回差的绝对值更小的那个即可。

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

func closestDivisors(num int) []int {
	f := func(x int) []int {
		for i := int(math.Sqrt(float64(x))); ; i-- {
			if x%i == 0 {
				return []int{i, x / i}
			}
		}
	}
	a, b := f(num+1), f(num+2)
	if abs(a[0]-a[1]) < abs(b[0]-b[1]) {
		return a
	}
	return b
}

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

力扣原题 · Doocs 题解来源

1390. 四因数

中等1 种解法

标签：数组、数学、筛法、质因数分解

题目、示例与约束

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。

 

示例 1：

输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。

示例 2:

输入: nums = [21,21]
输出: 64

示例 3:

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

 

提示：

• 1 <= nums.length <= 104
• 1 <= nums[i] <= 105

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

思考

因数恰好四个的数，把其因数和加入答案。 $nums[i]\le {10}^5$，对每个数试到 $\sqrt{x}$ 即可枚尽因数。计数与求和同步进行，个数恰为 $4$ 时返回该和，否则贡献 $0$。

我们可以对每个数进行因数分解，如果因数的个数为 $4$ 个，那么这个数就是符合题意的数，我们将其因数累加到答案中即可。

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

func sumFourDivisors(nums []int) (ans int) {
	f := func(x int) int {
		cnt, s := 2, x+1
		for i := 2; i <= x/i; i++ {
			if x%i == 0 {
				cnt++
				s += i
				if i*i != x {
					cnt++
					s += x / i
				}
			}
		}
		if cnt == 4 {
			return s
		}
		return 0
	}
	for _, x := range nums {
		ans += f(x)
	}
	return
}

力扣原题 · Doocs 题解来源

1399. 统计最大组的数目

简单1 种解法

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

题目、示例与约束

给定一个整数 n 。

我们需要根据数字的数位和将 1 到 n 的数字分组。例如，数字 14 和 5 属于 同一 组，而数字 13 和 3 属于 不同 组。

返回最大组的数字数量，即元素数量 最多 的组。

 

示例 1：

输入：n = 13
输出：4
解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
[1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。

示例 2：

输入：n = 2
输出：2
解释：总共有 2 个大小为 1 的组 [1]，[2]。

 

提示：

• 1 <= n <= 104

方法一：哈希表或数组 · Go 实现

思考

$1$ 到 $n$ 按数位和分组，问最大组的组数。 $n\le {10}^4$，数位和不超过 $36$。枚举每个数累加数位和，用计数表维护各组大小，同步更新当前最大组大小及其出现次数。

我们注意到数字范围不超过 ${10}^4$，因此数位和的范围也不超过 $9\times 4=36$，因此我们可以用哈希表或者一个长度为 $40$ 的数组 $cnt$ 来统计每个数位和的个数，用一个变量 $mx$ 表示最大的数位和个数。

我们在 $[1,..n]$ 中枚举每个数，计算其数位和 $s$，然后将 $cnt[s]$ 加 $1$，如果 $mx<cnt[s]$，则更新 $mx=cnt[s]$，并将 $ans$ 置为 $1$，如果 $mx=cnt[s]$，则将 $ans$ 加 $1$。

最后返回 $ans$ 即可。

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

func countLargestGroup(n int) (ans int) {
	cnt := [40]int{}
	mx := 0
	for i := 1; i <= n; i++ {
		s := 0
		for x := i; x > 0; x /= 10 {
			s += x % 10
		}
		cnt[s]++
		if mx < cnt[s] {
			mx = cnt[s]
			ans = 1
		} else if mx == cnt[s] {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1401. 圆和矩形是否有重叠

中等1 种解法

标签：几何、数学

题目、示例与约束

给你一个以 (radius, xCenter, yCenter) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2) ，其中 (x1, y1) 是矩形左下角的坐标，而 (x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分，请你返回 true ，否则返回 false 。

换句话说，请你检测是否 存在 点 (xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。

 

示例 1 ：

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形存在公共点 (1,0) 。

示例 2 ：

输入：radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false

示例 3 ：

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true

 

提示：

• 1 <= radius <= 2000
• -104 <= xCenter, yCenter <= 104
• -104 <= x1 < x2 <= 104
• -104 <= y1 < y2 <= 104

方法一：数学 · Go 实现

思考

枚举矩形内的格点或仅检查四个顶点，既可能漏掉边、内部与圆相交的情形，也与连续几何判定无关。坐标范围达 ${10}^4$，需要一次精确的几何判断。

圆与矩形相交，当且仅当矩形上距圆心最近的点落入圆内（含边界）。该最近点的横、纵坐标可分别在区间 $[x_1,x_2]$、 $[y_1,y_2]$ 上独立夹取。

若圆心投影落在对应区间内，则该维距离为 $0$；否则取到较近端点的距离。两维平方和与 $radiu{s}^2$ 比较即可，避免开方。

对于一个点 $(x,y)$，它到圆心 $(xCenter,yCenter)$ 的最短距离为 $\sqrt{(x-xCenter{)}^2+(y-yCenter{)}^2}$，如果这个距离小于等于半径 $radius$，那么这个点就在圆内（包括边界）。

而对于矩形内（包括边界）的点，它们的横坐标 $x$ 满足 $x_1\le x\le x_2$，纵坐标 $y$ 满足 $y_1\le y\le y_2$。要判断圆和矩形是否有重叠的部分，相当于在矩形内找到一个点 $(x,y)$，使得 $a=|x-xCenter|$ 和 $b=|y-yCenter|$ 都取到最小值，此时若 $a^2+b^2\le radiu{s}^2$，则说明圆和矩形有重叠的部分。

因此，问题转化为求 $x\in [x_1,x_2]$ 时 $a=|x-xCenter|$ 的最小值，以及 $y\in [y_1,y_2]$ 时 $b=|y-yCenter|$ 的最小值。

对于 $x\in [x_1,x_2]$：

• 如果 $x_1\le xCenter\le x_2$，那么 $|x-xCenter|$ 的最小值为 $0$；
• 如果 $xCenter<x_1$，那么 $|x-xCenter|$ 的最小值为 $x_1-xCenter$；
• 如果 $xCenter>x_2$，那么 $|x-xCenter|$ 的最小值为 $xCenter-x_2$。

同理，我们可以求出 $y\in [y_1,y_2]$ 时 $|y-yCenter|$ 的最小值。以上我们可以统一用函数 $f(i,j,k)$ 来处理。

即 $a=f(x_1,x_2,xCenter)$, $b=f(y_1,y_2,yCenter)$，如果 $a^2+b^2\le radiu{s}^2$，则说明圆和矩形有重叠的部分。

func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
	f := func(i, j, k int) int {
		if i <= k && k <= j {
			return 0
		}
		if k < i {
			return i - k
		}
		return k - j
	}
	a := f(x1, x2, xCenter)
	b := f(y1, y2, yCenter)
	return a*a+b*b <= radius*radius
}

力扣原题 · Doocs 题解来源

1427. 字符串的左右移 🔒

简单1 种解法

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

题目、示例与约束

给定一个包含小写英文字母的字符串 s 以及一个矩阵 shift，其中 shift[i] = [direction, amount]：

• direction 可以为 0 （表示左移）或 1 （表示右移）。
• amount 表示 s 左右移的位数。
• 左移 1 位表示移除 s 的第一个字符，并将该字符插入到 s 的结尾。
• 类似地，右移 1 位表示移除 s 的最后一个字符，并将该字符插入到 s 的开头。

对这个字符串进行所有操作后，返回最终结果。

 

示例 1：

输入：s = "abc", shift = [[0,1],[1,2]]
输出："cab"
解释：
[0,1] 表示左移 1 位。 "abc" -> "bca"
[1,2] 表示右移 2 位。 "bca" -> "cab"

示例 2：

输入：s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
输出："efgabcd"
解释： 
[1,1] 表示右移 1 位。 "abcdefg" -> "gabcdef"
[1,1] 表示右移 1 位。 "gabcdef" -> "fgabcde"
[0,2] 表示左移 2 位。 "fgabcde" -> "abcdefg"
[1,3] 表示右移 3 位。 "abcdefg" -> "efgabcd"

 

提示：

• 1 <= s.length <= 100
• s 只包含小写英文字母
• 1 <= shift.length <= 100
• shift[i].length == 2
• 0 <= shift[i][0] <= 1
• 0 <= shift[i][1] <= 100

方法一：模拟 · Go 实现

思考

多次左右移可以互相抵消。把左移记为负、右移记为正，累加偏移再对 $n$ 取模，一次切片完成全部移位。 $n,m\le 100$，即使逐步模拟也够用，合并后只需 $O(n+m)$。

我们不妨记字符串 $s$ 的长度为 $n$。接下来遍历数组 $shift$，累加得到最终的偏移量 $x$，然后将 $x$ 对 $n$ 取模，最终结果就是将 $s$ 的前 $n-x$ 个字符移动到末尾。

时间复杂度 $O(n+m)$，其中 $n$ 和 $m$ 分别是字符串 $s$ 的长度和数组 $shift$ 的长度。空间复杂度 $O(1)$。

func stringShift(s string, shift [][]int) string {
	x := 0
	for _, e := range shift {
		if e[0] == 0 {
			e[1] = -e[1]
		}
		x += e[1]
	}
	n := len(s)
	x = (x%n + n) % n
	return s[n-x:] + s[:n-x]
}

力扣原题 · Doocs 题解来源

1447. 最简分数

中等1 种解法

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

题目、示例与约束

给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于  n 的 最简 分数 。分数可以以 任意 顺序返回。

 

示例 1：

输入：n = 2
输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。

示例 2：

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

示例 3：

输入：n = 4
输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。

示例 4：

输入：n = 1
输出：[]

 

提示：

• 1 <= n <= 100

方法一：枚举分子分母 · Go 实现

思考

$n\le 100$，枚举 $1\le i<j\le n$，用 $gcd(i,j)=1$ 筛出最简真分数即可。

我们可以枚举分子 $i$ 和分母 $j$，其中 $1\le i<j\le n$，并判断 $i$ 和 $j$ 的最大公约数是否为 $1$，如果是则 $i/j$ 是一个最简分数。

时间复杂度 $O(n^2\times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是给定的参数。

func simplifiedFractions(n int) (ans []string) {
	for i := 1; i < n; i++ {
		for j := i + 1; j < n+1; j++ {
			if gcd(i, j) == 1 {
				ans = append(ans, strconv.Itoa(i)+"/"+strconv.Itoa(j))
			}
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源