LeetCode Go · 数学与几何（1）

来源与许可

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

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

7. 整数反转

中等1 种解法

标签：数学

题目、示例与约束

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2³¹, 2³¹− 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

提示：

-2³¹ <= x <= 2³¹ - 1

方法一：数学 · Go 实现

思考

若将整数转为字符串再反转，不必处理算术溢出。题目假定环境无法存储 $64$ 位整数，因此需要在 $32$ 位范围内逐位还原，并在运算过程中判断是否越界。

我们可以不断取出 $x$ 的个位 $y$ ，再累加到答案末尾，等价于 $ans \leftarrow 10 \cdot ans + y$ 。在乘 $10$ 之前就必须判断结果是否仍落在 $[- 2^{31}, 2^{31} - 1]$ 内，一旦越界则返回 $0$ 。

该判断可以化简为：当前 $ans$ 是否仍位于 $[⌊ m i / 10 ⌋, ⌊ m x / 10 ⌋]$ 。若在此范围内，再接入一位数字一定合法；若已经越出，则必然溢出。

我们不妨记 $m i$ 和 $m x$ 分别为 $- 2^{31}$ 和 $2^{31} - 1$ ，则 $x$ 的反转结果 $a n s$ 需要满足 $m i \leq a n s \leq m x$ 。

我们可以通过不断地对 $x$ 取余来获取 $x$ 的最后一位数字 $y$ ，并将 $y$ 添加到 $a n s$ 的末尾。在添加 $y$ 之前，我们需要判断 $a n s$ 是否溢出。即判断 $a n s \times 10 + y$ 是否在 $[m i, m x]$ 的范围内。

若 $x > 0$ ，那么需要满足 $a n s \times 10 + y \leq m x$ ，即 $a n s \times 10 + y \leq ⌊ \frac{m x}{10} ⌋ \times 10 + 7$ 。整理得 $(a n s - ⌊ \frac{m x}{10} ⌋) \times 10 \leq 7 - y$ 。

下面我们讨论上述不等式成立的条件：

当 $a n s < ⌊ \frac{m x}{10} ⌋$ 时，不等式显然成立；
当 $a n s = ⌊ \frac{m x}{10} ⌋$ 时，不等式成立的充要条件是 $y \leq 7$ 。如果 $a n s = ⌊ \frac{m x}{10} ⌋$ 并且还能继续添加数字，说明此时数字是最高位，即此时 $y$ 一定不超过 $2$ ，因此，不等式一定成立；
当 $a n s > ⌊ \frac{m x}{10} ⌋$ 时，不等式显然不成立。

综上，当 $x > 0$ 时，不等式成立的充要条件是 $a n s \leq ⌊ \frac{m x}{10} ⌋$ 。

同理，当 $x < 0$ 时，不等式成立的充要条件是 $a n s \geq ⌊ \frac{m i}{10} ⌋$ 。

因此，我们可以通过判断 $a n s$ 是否在 $[⌊ \frac{m i}{10} ⌋, ⌊ \frac{m x}{10} ⌋]$ 的范围内来判断 $a n s$ 是否溢出。若溢出，则返回 $0$ 。否则，将 $y$ 添加到 $a n s$ 的末尾，然后将 $x$ 的最后一位数字去除，即 $x \leftarrow ⌊ \frac{x}{10} ⌋$ 。

时间复杂度 $O (\log | x |)$ ，其中 $| x |$ 为 $x$ 的绝对值。空间复杂度 $O (1)$ 。

func reverse(x int) (ans int) {
	for ; x != 0; x /= 10 {
		if ans < math.MinInt32/10 || ans > math.MaxInt32/10 {
			return 0
		}
		ans = ans*10 + x%10
	}
	return
}

力扣原题 · Doocs 题解来源

9. 回文数

简单1 种解法

标签：数学

题目、示例与约束

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

-2³¹ <= x <= 2³¹ - 1

进阶：你能不将整数转为字符串来解决这个问题吗？

方法一：反转一半数字 · Go 实现

思考

判断 $x$ 是否回文，一种做法是转为字符串再比较。题目进阶要求不使用字符串；若将整个 $x$ 反转后再比较，则可能超出 $32$ 位整数范围。

我们只需反转后半部分：不断将 $x$ 的个位接到 $y$ 上，直到 $y$ 不再小于剩余的前半部分。负数带有负号，不可能是回文数；非零却以 $0$ 结尾的数，反转后会丢失末尾的 $0$ ，也可以直接返回 false。

循环在两半长度对齐时停止。位数为偶数时比较 $x$ 与 $y$ ；位数为奇数时，中间一位落在 $y$ 上，比较 $x$ 与 $⌊ y / 10 ⌋$ 。

我们先判断特殊情况：

如果 $x < 0$ ，那么 $x$ 不是回文数，直接返回 false；
如果 $x > 0$ 且 $x$ 的个位数是 $0$ ，那么 $x$ 不是回文数，直接返回 false；
如果 $x$ 的个位数不是 $0$ ，那么 $x$ 可能是回文数，继续执行下面的步骤。

我们将 $x$ 的后半部分反转，与前半部分进行比较，如果相等，那么 $x$ 是回文数，否则 $x$ 不是回文数。

举个例子，例如 $x = 1221$ ，我们可以将数字后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相等，我们得知数字 $x$ 是回文。

让我们看看如何将后半部分反转。

对于数字 $1221$ ，如果执行 $1221 mod 10$ ，我们将得到最后一位数字 $1$ ，要得到倒数第二位数字，我们可以先通过除以 $10$ 将最后一位数字从 $1221$ 中移除， $1221 / 10 = 122$ ，再求出上一步结果除以 $10$ 的余数， $122 mod 10 = 2$ ，就可以得到倒数第二位数字。

如果继续这个过程，我们将得到更多位数的反转数字。

通过将最后一位数字不断地累乘到取出数字的变量 $y$ 上，我们可以得到以相反顺序的数字。

在代码实现上，我们可以反复“取出” $x$ 的最后一位数字，并将其“添加”到 $y$ 的后面，循环直到 $y \geq x$ ，如果此时 $x = y$ ，或者 $x = y / 10$ ，那么 $x$ 就是回文数。

时间复杂度 $O (\log_{10} (n))$ ，其中 $n$ 是 $x$ 。对于每次迭代，我们会将输入除以 $10$ ，因此时间复杂度为 $O (\log_{10} (n))$ 。空间复杂度 $O (1)$ 。

func isPalindrome(x int) bool {
	if x < 0 || (x > 0 && x%10 == 0) {
		return false
	}
	y := 0
	for ; y < x; x /= 10 {
		y = y*10 + x%10
	}
	return x == y || x == y/10
}

力扣原题 · Doocs 题解来源

12. 整数转罗马数字

中等1 种解法

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

题目、示例与约束

七个不同的符号代表罗马数字，其值如下：

符号	值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

示例 1：

输入：num = 3749

输出： "MMMDCCXLIX"

解释：

3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
  40 = XL 由于 50 (L) 减 10 (X)
   9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

示例 2：

输入：num = 58

输出："LVIII"

解释：

50 = L
 8 = VIII

示例 3：

输入：num = 1994

输出："MCMXCIV"

解释：

1000 = M
 900 = CM
  90 = XC
   4 = IV

提示：

1 <= num <= 3999

方法一：贪心 · Go 实现

思考

按千、百、十、个分别查表，再单独处理 $4$ 、 $9$ 的减法写法，在 $1 \leq n u m \leq 3999$ 的范围内可以接受，但普通累加与减法形式要分成两套规则，分支多、容易遗漏。

注意到，若把 $CM = 900$ 、 $CD = 400$ 、 $XC = 90$ 等也视为独立面额，罗马数字就变成一组从大到小的固定面值。题目保证表示唯一，因此每次选取还能放下的最大面额一定合法。我们按面额从大到小扫描，当前剩余值不小于该面额时便减去并拼接对应符号。

我们可以先将所有可能的符号 $c s$ 和对应的数值 $v s$ 列出来，然后从大到小枚举每个数值 $v s [i]$ ，每次尽可能多地使用该数值对应的符号 $c s [i]$ ，直到数字 $n u m$ 变为 $0$ 。

时间复杂度为 $O (m)$ ，空间复杂度为 $O (m)$ 。其中 $m$ 为符号的个数。

func intToRoman(num int) string {
	cs := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
	vs := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	ans := &strings.Builder{}
	for i, v := range vs {
		for num >= v {
			num -= v
			ans.WriteString(cs[i])
		}
	}
	return ans.String()
}

力扣原题 · Doocs 题解来源

13. 罗马数字转整数

简单1 种解法

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

题目、示例与约束

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - 百度百科。

方法一：哈希表 + 模拟 · Go 实现

思考

从左到右扫描，遇到 $IV$ 、 $IX$ 等六种减法组合再特殊处理，其余字符直接累加，在 $| s | \leq 15$ 的范围内可以接受，但特例容易遗漏。

一个字符应当减去，当且仅当它比右侧相邻字符小；末位永远是加。因此不必枚举那六种组合。我们可以用哈希表记录每个字符的数值，从左到右比较相邻两位以决定正负，最后补上末位即可。

我们先用哈希表 $d$ 记录每个字符对应的数值，然后从左到右遍历字符串 $s$ ，如果当前字符对应的数值小于右边字符对应的数值，则减去当前字符对应的数值，否则加上当前字符对应的数值。

时间复杂度 $O (n)$ ，空间复杂度 $O (m)$ 。其中 $n$ 和 $m$ 分别为字符串 $s$ 的长度和字符集的大小。

func romanToInt(s string) (ans int) {
	d := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	for i := 0; i < len(s)-1; i++ {
		if d[s[i]] < d[s[i+1]] {
			ans -= d[s[i]]
		} else {
			ans += d[s[i]]
		}
	}
	ans += d[s[len(s)-1]]
	return
}

力扣原题 · Doocs 题解来源

43. 字符串相乘

中等1 种解法

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

题目、示例与约束

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

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

思考

题目不允许将输入直接转为整数，也不允许使用内置大整数库。两串长度可达 $200$ ，普通整型无法容纳乘积。

竖式乘法给出位置关系： $num1$ 的第 $i$ 位与 $num2$ 的第 $j$ 位之积只贡献到固定的数位，各位的进位可以在全部累加之后再统一处理。

乘积长度至多为 $m + n$ 。我们可以申请长度为 $m + n$ 的数组作为草稿纸，按位累加后再从低位向高位进位，最后去掉可能的前导零。

假设 $n u m 1$ 和 $n u m 2$ 的长度分别为 $m$ 和 $n$ ，则它们的乘积的长度最多为 $m + n$ 。

证明如下：

如果 $n u m 1$ 和 $n u m 2$ 都取最小值，那么它们的乘积为 $10^{m - 1} \times 10^{n - 1} = 10^{m + n - 2}$ ，长度为 $m + n - 1$ 。
如果 $n u m 1$ 和 $n u m 2$ 都取最大值，那么它们的乘积为 $(10^{m} - 1) \times (10^{n} - 1) = 10^{m + n} - 10^{m} - 10^{n} + 1$ ，长度为 $m + n$ 。

因此，我们可以申请一个长度为 $m + n$ 的数组，用于存储乘积的每一位。

从低位到高位，依次计算乘积的每一位，最后将数组转换为字符串即可。

注意判断最高位是否为 $0$ ，如果是，则去掉。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m + n)$ 。其中 $m$ 和 $n$ 分别为 $n u m 1$ 和 $n u m 2$ 的长度。

func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	m, n := len(num1), len(num2)
	arr := make([]int, m+n)
	for i := m - 1; i >= 0; i-- {
		a := int(num1[i] - '0')
		for j := n - 1; j >= 0; j-- {
			b := int(num2[j] - '0')
			arr[i+j+1] += a * b
		}
	}
	for i := len(arr) - 1; i > 0; i-- {
		arr[i-1] += arr[i] / 10
		arr[i] %= 10
	}
	i := 0
	if arr[0] == 0 {
		i = 1
	}
	ans := []byte{}
	for ; i < len(arr); i++ {
		ans = append(ans, byte('0'+arr[i]))
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

48. 旋转图像

中等1 种解法

标签：数组、数学、矩阵

题目、示例与约束

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

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

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

方法一：原地翻转 · Go 实现

思考

顺时针旋转 $90^{\circ}$ 的映射是 $matrix [i] [j] \to matrix [j] [n - 1 - i]$ 。若新开矩阵按此赋值，时间和空间都是 $O (n^{2})$ 。 $n \leq 20$ 时额外空间足够，但题目要求原地修改。

该映射可拆成两个可原地完成的操作：先上下翻转，再沿主对角线翻转（转置）。

$(i, j)$ 先到 $(n - 1 - i, j)$ ，再转到 $(j, n - 1 - i)$ ，恰好是目标位置。两次交换即可，额外空间 $O (1)$ 。

根据题目要求，我们实际上需要将 $matrix [i] [j]$ 旋转至 $matrix [j] [n - i - 1]$ 。

我们可以先对矩阵进行上下翻转，即 $matrix [i] [j]$ 和 $matrix [n - i - 1] [j]$ 进行交换，然后再对矩阵进行主对角线翻转，即 $matrix [i] [j]$ 和 $matrix [j] [i]$ 进行交换。这样就能将 $matrix [i] [j]$ 旋转至 $matrix [j] [n - i - 1]$ 了。

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

func rotate(matrix [][]int) {
	n := len(matrix)
	for i := 0; i < n>>1; i++ {
		for j := 0; j < n; j++ {
			matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
}

力扣原题 · Doocs 题解来源

50. Pow(x, n)

中等1 种解法

标签：递归、数学

题目、示例与约束

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xⁿ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2^-2 = 1/2² = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
n 是一个整数
要么 x 不为零，要么 n > 0 。
-10⁴ <= xⁿ <= 10⁴

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

思考

若把 $x$ 连乘 $| n |$ 次， $| n |$ 最大约 $2^{31}$ ，线性乘法容易超时；还要单独处理 $n < 0$ 时取倒数。

一次只乘一个 $x$ 没有利用幂的倍增结构。注意到 $x^{2 k} = (x^{k})^{2}$ ， $x^{2 k + 1} = x \cdot (x^{k})^{2}$ ，指数每次可以折半。

因此按 $n$ 的二进制位累乘：当前底不断平方，遇到 $1$ 位就乘进答案。负数指数先算正幂再取倒数。快速幂把 $O (| n |)$ 压成 $O (\log | n |)$ 。

快速幂算法的核心思想是将幂指数 $n$ 拆分为若干个二进制位上的 $1$ 的和，然后将 $x$ 的 $n$ 次幂转化为 $x$ 的若干个幂的乘积。

时间复杂度 $O (\log n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为幂指数。

func myPow(x float64, n int) float64 {
	qpow := func(a float64, n int) float64 {
		ans := 1.0
		for ; n > 0; n >>= 1 {
			if n&1 == 1 {
				ans *= a
			}
			a *= a
		}
		return ans
	}
	if n >= 0 {
		return qpow(x, n)
	}
	return 1 / qpow(x, -n)
}

力扣原题 · Doocs 题解来源

60. 排列序列

困难1 种解法

标签：递归、数学

题目、示例与约束

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出："213"

示例 2：

输入：n = 4, k = 9
输出："2314"

示例 3：

输入：n = 3, k = 1
输出："123"

提示：

1 <= n <= 9
1 <= k <= n!

方法一：枚举 · Go 实现

思考

第 $k$ 个排列不必先列出前面的 $k - 1$ 个。若生成全部 $n!$ 种排列再按下标取值， $n \leq 9$ 时可以枚举完，但其余排列都用不上。

确定某一位后，剩余数字的排列恰好占 $(n - i - 1)!$ 种。用 $k$ 与这个块大小比较，即可知道当前位应取第几个尚未使用的数字，并一次性跳过整块。

为此从左到右填每一位，用阶乘定位、用 $vis$ 记录已用数字，时间 $O (n^{2})$ 。

我们知道，集合 $[1, 2, . . n]$ 一共有 $n!$ 种排列，如果我们确定首位，那剩余位能组成的排列数量为 $(n - 1)!$ 。

因此，我们枚举每一位 $i$ ，如果此时 $k$ 大于当前位置确定后的排列数量，那么我们可以直接减去这个数量；否则，说明我们找到了当前位置的数。

对于每一位 $i$ ，其中 $0 \leq i < n$ ，剩余位能组成的排列数量为 $(n - i - 1)!$ ，我们记为 $f a c t$ 。过程中已使用的数记录在 vis 中。

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

func getPermutation(n int, k int) string {
	ans := make([]byte, n)
	vis := make([]bool, n+1)
	for i := 0; i < n; i++ {
		fact := 1
		for j := 1; j < n-i; j++ {
			fact *= j
		}
		for j := 1; j <= n; j++ {
			if !vis[j] {
				if k > fact {
					k -= fact
				} else {
					ans[i] = byte('0' + j)
					vis[j] = true
					break
				}
			}
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

66. 加一

简单1 种解法

标签：数组、数学

题目、示例与约束

给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。

将大整数加 1，并返回结果的数字数组。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
加 1 后得到 123 + 1 = 124。
因此，结果应该是 [1,2,4]。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
加 1 后得到 4321 + 1 = 4322。
因此，结果应该是 [4,3,2,2]。

示例 3：

输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

提示：

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits 不包含任何前导 0。

方法一：模拟 · Go 实现

思考

数组表示的整数最长可达 $100$ 位，远超普通整型范围，不能拼成整数再加一。

加一产生的进位至多为 $1$ ，且只会从最低位向高位传播。因此从右向左模拟即可：若某位加一后不再进位，则后续高位不变，可以直接返回；若每一位都变为 $0$ ，再在开头补上 $1$ 。不必将整个大数转换成其他表示。

我们从数组的最后一个元素开始遍历，将当前元素加一，然后对 $10$ 取模，如果取模后的结果不为 $0$ ，说明当前元素没有进位，直接返回数组即可。否则，当前元素为 $0$ ，需要进位，继续遍历前一个元素，重复上述操作。如果遍历完数组后，仍然没有返回，说明数组中所有元素都为 $0$ ，需要在数组的头部插入一个 $1$ 。

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

func plusOne(digits []int) []int {
	n := len(digits)
	for i := n - 1; i >= 0; i-- {
		digits[i]++
		digits[i] %= 10
		if digits[i] != 0 {
			return digits
		}
	}
	return append([]int{1}, digits...)
}

力扣原题 · Doocs 题解来源

149. 直线上最多的点数

困难2 种解法

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

题目、示例与约束

给你一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

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

示例 2：

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

提示：

1 <= points.length <= 300
points[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
points 中的所有点 互不相同

方法一：暴力枚举 · Go 实现

思考

求共线点的最大个数。点互不相同， $n$ 较小，枚举两点确定直线再扫其余点是否共线，用叉积避免除法，时间 $O (n^{3})$ 可以过。

我们可以枚举任意两个点 $(x_{1}, y_{1}), (x_{2}, y_{2})$ ，把这两个点连成一条直线，那么此时这条直线上的点的个数就是 2，接下来我们再枚举其他点 $(x_{3}, y_{3})$ ，判断它们是否在同一条直线上，如果在，那么直线上的点的个数就加 1，如果不在，那么直线上的点的个数不变。找出所有直线上的点的个数的最大值，即为答案。

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

func maxPoints(points [][]int) int {
	n := len(points)
	ans := 1
	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]
		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]
			cnt := 2
			for k := j + 1; k < n; k++ {
				x3, y3 := points[k][0], points[k][1]
				a := (y2 - y1) * (x3 - x1)
				b := (y3 - y1) * (x2 - x1)
				if a == b {
					cnt++
				}
			}
			if ans < cnt {
				ans = cnt
			}
		}
	}
	return ans
}

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

思考

方法一是 $O (n^{3})$ 。固定一点后，其余点按与它的斜率分组，同一斜率即共线。斜率用约分后的 $(Δ y, Δ x)$ 作键，避免浮点误差。对每个点 $O (n)$ 统计，总时间 $O (n^{2})$ 。

我们可以枚举一个点 $(x_{1}, y_{1})$ ，把其他所有点 $(x_{2}, y_{2})$ 与 $(x_{1}, y_{1})$ 连成的直线的斜率存入哈希表中，斜率相同的点在同一条直线上，哈希表的键为斜率，值为直线上的点的个数。找出哈希表中的最大值，即为答案。为了避免精度问题，我们可以将斜率 $\frac{y_{2} - y_{1}}{x_{2} - x_{1}}$ 进行约分，约分的方法是求最大公约数，然后分子分母同时除以最大公约数，将求得的分子分母作为哈希表的键。

时间复杂度 $O (n^{2} \times \log m)$ ，空间复杂度 $O (n)$ 。其中 $n$ 和 $m$ 分别是数组 points 的长度和数组 points 所有横纵坐标差的最大值。

相似题目：

面试题 16.14. 最佳直线

func maxPoints(points [][]int) int {
	n := len(points)
	ans := 1
	type pair struct{ x, y int }
	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]
		cnt := map[pair]int{}
		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]
			dx, dy := x2-x1, y2-y1
			g := gcd(dx, dy)
			k := pair{dx / g, dy / g}
			cnt[k]++
			if ans < cnt[k]+1 {
				ans = cnt[k] + 1
			}
		}
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

166. 分数到小数

中等1 种解法

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

题目、示例与约束

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证答案字符串的长度小于 10⁴ 。

注意，如果分数可以表示为有限长度的字符串，则必须返回它。

示例 1：

输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1
输出："2"

示例 3：

输入：numerator = 4, denominator = 333
输出："0.(012)"

提示：

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

方法一：数学 + 哈希表 · Go 实现

思考

把分数转成小数，循环节要加括号。长除法产生循环，当且仅当余数重复。先处理符号与整数部分；小数阶段用哈希表记下每个余数第一次出现的位置，余数再现则在该位置插入括号。余数为 $0$ 则是有限小数。

我们首先判断 $n u m e r a t o r$ 是否为 $0$ ，如果是，则直接返回 "0"。

接着我们判断 $n u m e r a t o r$ 和 $d e n o m i n a t o r$ 是否异号，如果是，则结果为负数，我们将结果的第一个字符设为 "-"。

然后我们将 $n u m e r a t o r$ 和 $d e n o m i n a t o r$ 取绝对值，分别记为 $a$ 和 $b$ 。由于分子和分母的范围为 $[- 2^{31}, 2^{31} - 1]$ ，直接取绝对值可能会溢出，因此我们将 $a$ 和 $b$ 都转换为长整型。

接着我们计算整数部分，即 $a$ 除以 $b$ 的整数部分，将其转换为字符串并添加到结果中。然后我们将 $a$ 取余 $b$ ，记为 $a$ 。

如果 $a$ 为 $0$ ，说明结果为整数，直接返回结果。

接着我们计算小数部分，我们使用哈希表 $d$ 记录每个余数对应的结果的长度。我们不断将 $a$ 乘以 $10$ ，然后将 $a$ 除以 $b$ 的整数部分添加到结果中，然后将 $a$ 取余 $b$ ，记为 $a$ 。如果 $a$ 为 $0$ ，说明结果为有限小数，直接返回结果。如果 $a$ 在哈希表中出现过，说明结果为循环小数，我们找到循环的起始位置，将结果插入括号中，然后返回结果。

时间复杂度 $O (l)$ ，空间复杂度 $O (l)$ ，其中 $l$ 为结果的长度，本题中 $l < 10^{4}$ 。

func fractionToDecimal(numerator int, denominator int) string {
	if numerator == 0 {
		return "0"
	}
	ans := ""
	if (numerator > 0) != (denominator > 0) {
		ans += "-"
	}
	a := int64(numerator)
	b := int64(denominator)
	a = abs(a)
	b = abs(b)
	ans += strconv.FormatInt(a/b, 10)
	a %= b
	if a == 0 {
		return ans
	}
	ans += "."
	d := make(map[int64]int)
	for a != 0 {
		if pos, ok := d[a]; ok {
			ans = ans[:pos] + "(" + ans[pos:] + ")"
			break
		}
		d[a] = len(ans)
		a *= 10
		ans += strconv.FormatInt(a/b, 10)
		a %= b
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

168. Excel 表列名称

简单1 种解法

标签：数学、字符串

题目、示例与约束

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

示例 1：

输入：columnNumber = 1
输出："A"

示例 2：

输入：columnNumber = 28
输出："AB"

示例 3：

输入：columnNumber = 701
输出："ZY"

示例 4：

输入：columnNumber = 2147483647
输出："FXSHRXW"

提示：

1 <= columnNumber <= 2³¹ - 1

方法一 · Go 实现

思考

把正整数转成 Excel 列名，本质是 $1 \dots 26$ 对应 $A \dots Z$ 的进制，没有 $0$ 。普通 $26$ 进制会把余 $0$ 写成 $0$ 而不是 $Z$ 。每次先减 $1$ 再模 $26$ ，余数对上 $A$ 到 $Z$ ，商继续，最后反转字符。

func convertToTitle(columnNumber int) string {
	res := []rune{}
	for columnNumber != 0 {
		columnNumber -= 1
		res = append([]rune{rune(columnNumber%26 + int('A'))}, res...)
		columnNumber /= 26
	}
	return string(res)
}

力扣原题 · Doocs 题解来源

171. Excel 表列序号

简单1 种解法

标签：数学、字符串

题目、示例与约束

给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。

例如：

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

示例 1:

输入: columnTitle = "A"
输出: 1

示例 2:

输入: columnTitle = "AB"
输出: 28

示例 3:

输入: columnTitle = "ZY"
输出: 701

提示：

1 <= columnTitle.length <= 7
columnTitle 仅由大写英文组成
columnTitle 在范围 ["A", "FXSHRXW"] 内

方法一：进制转换 · Go 实现

思考

列名转序号，是 $168$ 的逆过程：每位是 $1 \dots 26$ 的 $26$ 进制。从左到右累加 $ans = ans \times 26 + (c -^{'} A^{'} + 1)$ ，与把十进制字符串转整数同一套路。

Excel 表格中的列名称是一种 26 进制的表示方法。例如，"AB" 表示的列序号是 $1 \times 26 + 2 = 28$ 。

因此，我们可以遍历字符串 columnTitle，将每个字符转换为对应的数值，然后计算结果即可。

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

func titleToNumber(columnTitle string) (ans int) {
	for _, c := range columnTitle {
		ans = ans*26 + int(c-'A'+1)
	}
	return
}

力扣原题 · Doocs 题解来源

172. 阶乘后的零

中等1 种解法

标签：数学

题目、示例与约束

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0

提示：

0 <= n <= 10⁴

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

方法一：数学 · Go 实现

思考

阶乘末尾零来自因子 $10 = 2 \times 5$ ，而 $2$ 的个数远多于 $5$ ，因此零的个数等于 $[1, n]$ 中 $5$ 的因子个数。直接算 $n!$ 在 $n \leq 10^{4}$ 都会溢出。进阶要对数时间：反复 $n \leftarrow ⌊ n / 5 ⌋$ 累加，分别计入 $5, 5^{2}, 5^{3}, \dots$ 的贡献。

题目实际上是求 $[1, n]$ 中有多少个 $5$ 的因数。

我们以 $130$ 为例来分析：

第 $1$ 次除以 $5$ ，得到 $26$ ，表示存在 $26$ 个包含因数 $5$ 的数；
第 $2$ 次除以 $5$ ，得到 $5$ ，表示存在 $5$ 个包含因数 $5^{2}$ 的数；
第 $3$ 次除以 $5$ ，得到 $1$ ，表示存在 $1$ 个包含因数 $5^{3}$ 的数；
累加得到从 $[1, n]$ 中所有 $5$ 的因数的个数。

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

func trailingZeroes(n int) int {
	ans := 0
	for n > 0 {
		n /= 5
		ans += n
	}
	return ans
}

力扣原题 · Doocs 题解来源

204. 计数质数

中等1 种解法

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

题目、示例与约束

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

0 <= n <= 5 * 10⁶

方法一：埃氏筛 · Go 实现

思考

对每个 $x$ 试除到 $\sqrt{x}$ 可统计素数，但 $n$ 可达 $5 \times 10^{6}$ ，重复试除偏慢。若 $x$ 为素数，则 $2 x, 3 x, \dots$ 必为合数。

为此用埃氏筛：从小到大扫描，遇到素数便将其倍数标记为合数，最后统计仍为素数的个数。每个合数只被其因子划去，时间约为 $O (n \log \log n)$ 。

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

设 $p r i m e s [i]$ 表示数 $i$ 是不是质数，如果是质数则为 $t r u e$ ，否则为 $f a l s e$ 。

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

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

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

力扣原题 · Doocs 题解来源

223. 矩形面积

中等1 种解法

标签：几何、数学

题目、示例与约束

给你二维平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其左下顶点和右上顶点坐标表示：

第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

示例 1：

输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45

示例 2：

输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16

提示：

-10⁴ <= ax1 <= ax2 <= 10⁴
-10⁴ <= ay1 <= ay2 <= 10⁴
-10⁴ <= bx1 <= bx2 <= 10⁴
-10⁴ <= by1 <= by2 <= 10⁴

方法一：计算重叠面积 · Go 实现

思考

两矩形并面积等于各自面积之和减去重叠。重叠宽度为右边界较小者减去左边界较大者，高度同理；若为负则不相交。

为此先算两面积，再用 $max (width, 0) \times max (height, 0)$ 扣掉重叠。

我们先计算出两个矩形各自的面积，记为 $a$ 和 $b$ ，然后计算重叠的宽度 $w i d t h$ 和高度 $h e i g h t$ ，那么重叠的面积为 $m a x (w i d t h, 0) \times m a x (h e i g h t, 0)$ ，最后将 $a$ , $b$ 和重叠面积相减即可。

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

func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
	a := (ax2 - ax1) * (ay2 - ay1)
	b := (bx2 - bx1) * (by2 - by1)
	width := min(ax2, bx2) - max(ax1, bx1)
	height := min(ay2, by2) - max(ay1, by1)
	return a + b - max(height, 0)*max(width, 0)
}

力扣原题 · Doocs 题解来源

258. 各位相加

简单1 种解法

标签：数学、数论、模拟

题目、示例与约束

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

示例 1:

输入: num = 38
输出: 2 
解释: 各位相加的过程为：
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于 2 是一位数，所以返回 2。

示例 2:

输入: num = 0
输出: 0

提示：

0 <= num <= 2³¹ - 1

进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

方法一 · Go 实现

思考

反复求各位和最终得到一位数，即数根。对非负整数有闭式： $num = 0$ 时为 $0$ ，否则为 $(num - 1) mod 9 + 1$ 。

func addDigits(num int) int {
	if num == 0 {
		return 0
	}
	return (num-1)%9 + 1
}

力扣原题 · Doocs 题解来源

263. 丑数

简单1 种解法

标签：数学

题目、示例与约束

丑数就是只包含质因数 2、3 和 5 的正整数。

给你一个整数 n ，请你判断 n 是否为丑数。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

示例 2：

输入：n = 1
输出：true
解释：1 没有质因数。

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。

提示：

-2³¹ <= n <= 2³¹ - 1

方法一 · Go 实现

思考

丑数的质因子只能是 $2, 3, 5$ 。非正数直接否决；否则不断除掉这三个因子，最后剩 $1$ 则为丑数。

func isUgly(n int) bool {
	if n < 1 {
		return false
	}
	for _, x := range []int{2, 3, 5} {
		for n%x == 0 {
			n /= x
		}
	}
	return n == 1
}

力扣原题 · Doocs 题解来源

273. 整数转换英文表示

困难1 种解法

标签：递归、数学、字符串

题目、示例与约束

将非负整数 num 转换为其对应的英文表示。

示例 1：

输入：num = 123
输出："One Hundred Twenty Three"

示例 2：

输入：num = 12345
输出："Twelve Thousand Three Hundred Forty Five"

示例 3：

输入：num = 1234567
输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

提示：

0 <= num <= 2³¹ - 1

方法一 · Go 实现

思考

英文读法按千分位分组：Billion、Million、Thousand。每组至多三位数，可用二十以内、整十与 Hundred 拼出。

$0$ 单独返回 Zero；从高到低取每组非零块，调用 $t r a n s f e r$ 后再接单位。

func numberToWords(num int) string {
	if num == 0 {
		return "Zero"
	}

	lt20 := []string{
		"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight",
		"Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen",
		"Sixteen", "Seventeen", "Eighteen", "Nineteen",
	}
	tens := []string{
		"", "Ten", "Twenty", "Thirty", "Forty", "Fifty",
		"Sixty", "Seventy", "Eighty", "Ninety",
	}
	thousands := []string{"Billion", "Million", "Thousand", ""}

	var transfer func(int) string
	transfer = func(num int) string {
		if num == 0 {
			return ""
		}
		if num < 20 {
			return lt20[num]
		}
		if num < 100 {
			if num%10 == 0 {
				return tens[num/10]
			}
			return tens[num/10] + " " + transfer(num%10)
		}
		if num%100 == 0 {
			return lt20[num/100] + " Hundred"
		}
		return lt20[num/100] + " Hundred " + transfer(num%100)
	}

	res := ""
	for i, j := 1000000000, 0; i > 0; i, j = i/1000, j+1 {
		cur := num / i
		if cur == 0 {
			continue
		}
		if res != "" {
			res += " "
		}
		res += transfer(cur)
		if thousands[j] != "" {
			res += " " + thousands[j]
		}
		num %= i
	}
	return res
}

力扣原题 · Doocs 题解来源

292. Nim 游戏

简单1 种解法

标签：脑筋急转弯、极小化极大、数学、博弈、Nim 游戏、无偏博弈

题目、示例与约束

你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合， 你作为先手 。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入：n = 4
输出：false 
解释：以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

提示：

1 <= n <= 2³¹ - 1

方法一：找规律 · Go 实现

思考

每次可取 $1$ 到 $3$ 块，谁面对 $4$ 的倍数都无法一次取完，对手总能补到 $4$ 。因此先手获胜当且仅当 $n$ 不能被 $4$ 整除。

第一个得到 $4$ 的倍数（即 $n$ 能被 $4$ 整除）的将会输掉比赛。

证明：

当 $n < 4$ 时，第一个玩家可以直接拿走所有的石头，所以第一个玩家将会赢得比赛。
当 $n = 4$ ，无论第一个玩家选择 $1, 2, 3$ 哪个数字，第二个玩家总能选择剩下的数字，所以第一个玩家将会输掉比赛。
当 $4 < n < 8$ 时，即 $n = 5, 6, 7$ ，第一个玩家可以相应地将数字减少为 $4$ ，那么 $4$ 这个死亡数字给到了第二个玩家，第二个玩家将会输掉比赛。
当 $n = 8$ ，无论第一个玩家选择 $1, 2, 3$ 哪个数字，都会把 $4 < n < 8$ 的数字留给第二个，所以第一个玩家将会输掉比赛。
...
依次类推，当玩家拿到 $n$ 这个数字，且 $n$ 能被 $4$ 整除，他将会输掉比赛，否则他将赢得比赛。

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

func canWinNim(n int) bool {
	return n%4 != 0
}

力扣原题 · Doocs 题解来源

296. 最佳的碰头地点 🔒

困难1 种解法

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

题目、示例与约束

给你一个 m x n 的二进制网格 grid ，其中 1 表示某个朋友的家所处的位置。返回最小的 总行走距离 。

总行走距离 是朋友们家到碰头地点的距离之和。

我们将使用曼哈顿距离来计算，其中 distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y| 。

示例 1：

输入: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
输出: 6 
解释: 给定的三个人分别住在(0,0)，(0,4) 和 (2,2):
     (0,2) 是一个最佳的碰面点，其总行走距离为 2 + 2 + 2 = 6，最小，因此返回 6。

示例 2:

输入: grid = [[1,1]]
输出: 1

提示:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] == 0 or 1.
grid 中至少有两个朋友

方法一：排序 + 中位数 · Go 实现

思考

曼哈顿距离可拆成横坐标差之和与纵坐标差之和。一维上到各点距离之和在中位数处最小。

收集所有 $1$ 的行号（已有序）与列号（再排序），取中位数为碰头点，再累加绝对差。

对于每一行，我们可以将所有的 $1$ 的下标排序，然后取中位数 $i$ 作为碰头地点的横坐标。

对于每一列，我们可以将所有的 $1$ 的下标排序，然后取中位数 $i$ 作为碰头地点的纵坐标。

最后，我们计算所有 $1$ 到碰头地点 $(i, j)$ 的曼哈顿距离之和即可。

时间复杂度 $O (m \times n \times \log (m \times n))$ 。最多有 $m \times n$ 个 $1$ ，排序的时间复杂度为 $\log (m \times n)$ 。

相似题目：

func minTotalDistance(grid [][]int) int {
	rows, cols := []int{}, []int{}
	for i, row := range grid {
		for j, v := range row {
			if v == 1 {
				rows = append(rows, i)
				cols = append(cols, j)
			}
		}
	}
	sort.Ints(cols)
	i := rows[len(rows)>>1]
	j := cols[len(cols)>>1]
	f := func(arr []int, x int) int {
		s := 0
		for _, v := range arr {
			s += abs(v - x)
		}
		return s
	}
	return f(rows, i) + f(cols, j)
}

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

力扣原题 · Doocs 题解来源

319. 灯泡开关

中等1 种解法

标签：脑筋急转弯、数学

题目、示例与约束

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

示例 1：

输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

0 <= n <= 10⁹

方法一：数学 · Go 实现

思考

第 $i$ 盏灯被操作的次数等于 $i$ 的因子个数；奇数次则最终亮着。模拟 $n$ 轮开关为 $O (n \log n)$ ，而 $n$ 可达 $10^{9}$ 。

因子成对出现，仅完全平方数有奇数个因子。 $1 \dots n$ 中平方数的个数为 $⌊ \sqrt{n} ⌋$ ，直接返回该值。

我们不妨将 $n$ 个灯泡编号为 $1, 2, 3, \dots, n$ ，那么对于第 $i$ 个灯泡，它会在第 $d$ 轮被操作，当且仅当 $d$ 是 $i$ 的因子。

对于一个数 $i$ ，它的因子个数是有限的，且因子个数为奇数时，最后的状态是开启的，否则是关闭的。

因此，我们只需要找到 $1$ 到 $n$ 中因子个数为奇数的数的个数即可。

对于一个数 $i$ ，如果它有因子 $d$ ，那么它一定有因子 $i / d$ ，因此因子个数为奇数的数一定是平方数。

举个例子，数字 $12$ 的因子有 $1, 2, 3, 4, 6, 12$ ，因子个数为 $6$ ，是偶数；而对于数字 $16$ 这个平方数，因子有 $1, 2, 4, 8, 16$ ，因子个数为 $5$ ，是奇数。

因此，我们只需要找到 $1$ 到 $n$ 中有多少个平方数即可，即 $⌊ \sqrt{n} ⌋$ 。

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

func bulbSwitch(n int) int {
	return int(math.Sqrt(float64(n)))
}

力扣原题 · Doocs 题解来源

326. 3 的幂

简单2 种解法

标签：递归、数学

题目、示例与约束

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

-2³¹ <= n <= 2³¹ - 1

进阶：你能不使用循环或者递归来完成本题吗？

方法一：试除法 · Go 实现

思考

判断 $n$ 是否为 $3$ 的幂。连乘直到溢出再比较亦可，但试除更直接：在 $n > 2$ 时若不能被 $3$ 整除则否，否则除以 $3$ 。最终只剩 $1$ 则为是。 $n \leq 1$ 的情况自然落到最后的相等判断。

如果 $n > 2$ ，我们可以不断地将 $n$ 除以 $3$ ，如果不能整除，说明 $n$ 不是 $3$ 的幂，否则继续除以 $3$ ，直到 $n$ 小于等于 $2$ 。如果 $n$ 等于 $1$ ，说明 $n$ 是 $3$ 的幂，否则不是 $3$ 的幂。

时间复杂度 $O (\log_{3} n)$ ，空间复杂度 $O (1)$ 。

func isPowerOfThree(n int) bool {
	for n > 2 {
		if n%3 != 0 {
			return false
		}
		n /= 3
	}
	return n == 1
}

方法二：数学 · Go 实现

思考

试除需 $O (\log n)$ 次除法。 $32$ 位内最大 $3$ 的幂为 $3^{19} = 1162261467$ ，正整数 $n$ 为 $3$ 的幂当且仅当它整除该值。一次取模即可。

如果 $n$ 是 $3$ 的幂，那么 $n$ 最大是 $3^{19} = 1162261467$ ，因此我们只需要判断 $n$ 是否是 $3^{19}$ 的约数即可。

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

func isPowerOfThree(n int) bool {
	return n > 0 && 1162261467%n == 0
}

力扣原题 · Doocs 题解来源

335. 路径交叉

困难1 种解法

标签：几何、数组、数学

题目、示例与约束

给你一个整数数组 distance 。

从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。

示例 1：

输入：distance = [2,1,1,2]
输出：true

示例 2：

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

示例 3：

输入：distance = [1,1,1,1]
输出：true

提示：

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

方法一 · Go 实现

思考

从原点交替向上、左、下、右走给定距离，判断折线是否自交。模拟坐标再判交为 $O (n^{2})$ ，且 $n$ 可达 $5 \times 10^{4}$ 。

自交只可能发生在最近的三四段：第四段够到第一段、第五段补到第二段、第六段同时够到第三与第一段。对 $i \geq 3$ 检查这三种局部几何关系即可，无需存整条路径。

func isSelfCrossing(distance []int) bool {
	d := distance
	for i := 3; i < len(d); i++ {
		if d[i] >= d[i-2] && d[i-1] <= d[i-3] {
			return true
		}
		if i >= 4 && d[i-1] == d[i-3] && d[i]+d[i-4] >= d[i-2] {
			return true
		}
		if i >= 5 && d[i-2] >= d[i-4] && d[i-1] <= d[i-3] && d[i] >= d[i-2]-d[i-4] && d[i-1]+d[i-5] >= d[i-3] {
			return true
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

356. 直线镜像 🔒

中等1 种解法

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

题目、示例与约束

在一个二维平面空间中，给你 n 个点的坐标。问，是否能找出一条平行于 y 轴的直线，让这些点关于这条直线成镜像排布？

注意：题目数据中可能有重复的点。

示例 1：

输入：points = [[1,1],[-1,1]]
输出：true
解释：可以找出 x = 0 这条线。

示例 2：

输入：points = [[1,1],[-1,-1]]
输出：false
解释：无法找出这样一条线。

提示：

n == points.length
1 <= n <= 10^4
-10^8 <= points[i][j] <= 10^8

进阶：你能找到比 O(n²) 更优的解法吗?

方法一：哈希表 · Go 实现

思考

判断点集是否关于某条竖直线对称。枚举所有可能中线过多。若对称，中线必过最左与最右 $x$ 的中点。

令 $s = min x + max x$ ，每个 $(x, y)$ 的对称点 $(s - x, y)$ 须在集合中。先把点放入哈希集合再一次检查。

我们先找出所有点中的最小、最大的 $x$ 坐标 $m i n X$ 和 $m a x X$ 。若存在满足条件的直线，则直线 $x = (m i n X + m a x X) / 2$ ，或者说 $s = m i n X + m a x X$ 。

接下来，我们遍历每个点 $(x, y)，若 $(s - x, y)$ 不在点集里，说明不满足条件，直接返回 false。遍历结束返回 true。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $p o i n t s$ 的长度。

func isReflected(points [][]int) bool {
	const inf = 1 << 30
	minX, maxX := inf, -inf
	pointSet := map[[2]int]bool{}
	for _, p := range points {
		minX = min(minX, p[0])
		maxX = max(maxX, p[0])
		pointSet[[2]int{p[0], p[1]}] = true
	}
	s := minX + maxX
	for _, p := range points {
		if !pointSet[[2]int{s - p[0], p[1]}] {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

372. 超级次方

中等1 种解法

标签：数学、分治、欧拉函数、欧拉定理

题目、示例与约束

你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1：

输入： a = 2, b = [3]

输出： 8

解释：

数组 b = [3] 表示指数 3。因此，a³ = 2³ = 8，所以结果为 8。

示例 2：

输入： a = 2, b = [1,0]

输出： 1024

解释：

数组 b = [1, 0] 表示指数 10。因此，a¹⁰ = 2¹⁰ = 1024，所以结果为 1024。

示例 3：

输入： a = 1, b = [4,3,3,8,5,2]

输出： 1

解释：

数组 b = [4, 3, 3, 8, 5, 2] 表示一个正整数指数。由于 a = 1，1 的任意正整数次幂都等于 1。因此，结果为 1。

提示：

1 <= a <= 2³¹ - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

方法一：快速幂 · Go 实现

思考

$a$ 的指数是大整数 $b$ 的十进制数组，求 $a^{b} mod 1337$ 。直接把 $b$ 拼成整数再幂在语言限制下不便。按位展开 $b = \dots + e_{i} \cdot 10^{i}$ 。

自低位向高位：答案乘 $a^{e}$ ，再把底数换成 $a^{10}$ 。快速幂取模保证每步 $O (\log e)$ 。

我们初始化答案变量 $a n s = 1$ 。

接下来，倒序遍历数组 $b$ ，每次遍历到一个元素 $e$ ，我们将答案变量 $a n s$ 自乘 $a^{e}$ 并对 $1337$ 取模，然后将 $a$ 自乘 $10$ 次并对 $1337$ 取模。这里需要用到快速幂。

遍历完数组后，返回答案即可。

时间复杂度 $O (\sum_{i = 0}^{n - 1} \log b_{i})$ ，空间复杂度 $O (1)$ 。

func superPow(a int, b []int) int {
	const mod int = 1337
	ans := 1
	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
	}
	for i := len(b) - 1; i >= 0; i-- {
		ans = ans * qpow(a, b[i]) % mod
		a = qpow(a, 10)
	}
	return ans
}

力扣原题 · Doocs 题解来源

390. 消除游戏

中等1 种解法

标签：递归、数学

题目、示例与约束

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回 arr 最后剩下的数字。

示例 1：

输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 10⁹

方法一 · Go 实现

思考

从 $1 \dots n$ 交替从左、从右每隔一个删除，求最后剩下的数。模拟链表为 $O (n)$ ，而 $n$ 达 $10^{9}$ 。每轮长度减半，首尾与步长有闭式。

维护当前区间首 $a 1$ 、尾 $a n$ 、步长与剩余个数。从左删则首一定右移；从右删且长度为奇时首也右移。尾对称更新。剩一个时返回 $a 1$ 。

func lastRemaining(n int) int {
	a1, an, step := 1, n, 1
	for i, cnt := 0, n; cnt > 1; cnt, step, i = cnt>>1, step<<1, i+1 {
		if i%2 == 1 {
			an -= step
			if cnt%2 == 1 {
				a1 += step
			}
		} else {
			a1 += step
			if cnt%2 == 1 {
				an -= step
			}
		}
	}
	return a1
}

力扣原题 · Doocs 题解来源

391. 完美矩形

困难1 种解法

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

题目、示例与约束

给你一个数组 rectangles ，其中 rectangles[i] = [x_i, y_i, a_i, b_i] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (x_i, y_i) ，右上顶点是 (a_i, b_i) 。

如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

示例 1：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。

示例 2：

输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

提示：

1 <= rectangles.length <= 2 * 10⁴
rectangles[i].length == 4
-10⁵ <= x_i < a_i <= 10⁵
-10⁵ <= y_i < b_i <= 10⁵

方法一 · Go 实现

思考

小矩形能否无重叠、无缝铺成一个大矩形。扫描线或暴力对齐复杂。完美覆盖当且仅当面积相等，且除大矩形四角外每个顶点出现偶数次（ $2$ 或 $4$ ）。

累加面积并统计顶点出现次数。大矩形四角须恰出现一次，其余顶点次数为 $2$ 或 $4$ ，面积等于包围盒。

type pair struct {
	first  int
	second int
}

func isRectangleCover(rectangles [][]int) bool {
	area := 0
	minX, minY := rectangles[0][0], rectangles[0][1]
	maxX, maxY := rectangles[0][2], rectangles[0][3]

	cnt := make(map[pair]int)
	for _, r := range rectangles {
		area += (r[2] - r[0]) * (r[3] - r[1])

		minX = min(minX, r[0])
		minY = min(minY, r[1])
		maxX = max(maxX, r[2])
		maxY = max(maxY, r[3])

		cnt[pair{r[0], r[1]}]++
		cnt[pair{r[0], r[3]}]++
		cnt[pair{r[2], r[3]}]++
		cnt[pair{r[2], r[1]}]++
	}

	if area != (maxX-minX)*(maxY-minY) ||
		cnt[pair{minX, minY}] != 1 ||
		cnt[pair{minX, maxY}] != 1 ||
		cnt[pair{maxX, maxY}] != 1 ||
		cnt[pair{maxX, minY}] != 1 {
		return false
	}

	delete(cnt, pair{minX, minY})
	delete(cnt, pair{minX, maxY})
	delete(cnt, pair{maxX, maxY})
	delete(cnt, pair{maxX, minY})

	for _, c := range cnt {
		if c != 2 && c != 4 {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

398. 随机数索引

中等1 种解法

标签：水塘抽样、哈希表、数学、随机化

题目、示例与约束

给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。

实现 Solution 类：

Solution(int[] nums) 用数组 nums 初始化对象。
int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引，则每个索引的返回概率应当相等。

示例：

输入
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
输出
[null, 4, 0, 2]

解释
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
solution.pick(1); // 返回 0 。因为只有 nums[0] 等于 1 。
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。

提示：

1 <= nums.length <= 2 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
target 是 nums 中的一个整数
最多调用 pick 函数 10⁴ 次

方法一 · Go 实现

思考

在数组中等概率返回 $t a r g e t$ 的一个下标。预处理下标列表需 $O (n)$ 空间。水塘抽样按流式处理。

扫到第 $n$ 个匹配时以 $1 / n$ 替换答案下标。不存全部位置。

type Solution struct {
	nums []int
}

func Constructor(nums []int) Solution {
	return Solution{nums}
}

func (this *Solution) Pick(target int) int {
	n, ans := 0, 0
	for i, v := range this.nums {
		if v == target {
			n++
			x := 1 + rand.Intn(n)
			if n == x {
				ans = i
			}
		}
	}
	return ans
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.Pick(target);
 */

力扣原题 · Doocs 题解来源

412. Fizz Buzz

简单1 种解法

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

题目、示例与约束

给你一个整数 n ，返回一个字符串数组 answer（下标从 1 开始），其中：

answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
answer[i] == "Fizz" 如果 i 是 3 的倍数。
answer[i] == "Buzz" 如果 i 是 5 的倍数。
answer[i] == i （以字符串形式）如果上述条件全不满足。

示例 1：

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

示例 2：

输入：n = 5
输出：["1","2","Fizz","4","Buzz"]

示例 3：

输入：n = 15
输出：["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

提示：

1 <= n <= 10⁴

方法一：模拟 · Go 实现

思考

按规则输出 $1$ 到 $n$ 的读法，约束下线性扫描即可。

对每个 $i$ 先判断能否被 $15$ 整除，再判断 $3$ 与 $5$ ，最后才写入数字本身。先判 $15$ ，避免同时满足两个条件时漏写 $FizzBuzz$ 。

我们遍历从 1 到 n 的每个整数，对于每个整数，我们检查它是否是 3 和 5 的倍数，或者只是 3 的倍数，或者只是 5 的倍数。根据检查的结果，我们将相应的字符串添加到答案数组中。

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

func fizzBuzz(n int) []string {
	ans := make([]string, 0, n)
	for i := 1; i < n+1; i++ {
		switch {
		case i%15 == 0:
			ans = append(ans, "FizzBuzz")
		case i%3 == 0:
			ans = append(ans, "Fizz")
		case i%5 == 0:
			ans = append(ans, "Buzz")
		default:
			ans = append(ans, strconv.Itoa(i))
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

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

7. 整数反转 ​

9. 回文数 ​

12. 整数转罗马数字 ​

13. 罗马数字转整数 ​

43. 字符串相乘 ​

48. 旋转图像 ​

50. Pow(x, n) ​

60. 排列序列 ​

66. 加一 ​

149. 直线上最多的点数 ​

166. 分数到小数 ​

168. Excel 表列名称 ​

171. Excel 表列序号 ​

172. 阶乘后的零 ​

204. 计数质数 ​

223. 矩形面积 ​

258. 各位相加 ​

263. 丑数 ​

273. 整数转换英文表示 ​

292. Nim 游戏 ​

296. 最佳的碰头地点 🔒 ​

319. 灯泡开关 ​

326. 3 的幂 ​

335. 路径交叉 ​

356. 直线镜像 🔒 ​

372. 超级次方 ​

390. 消除游戏 ​

391. 完美矩形 ​

398. 随机数索引 ​

412. Fizz Buzz ​

继续阅读

LeetCode Go · 数学与几何（1）

7. 整数反转

9. 回文数

12. 整数转罗马数字

13. 罗马数字转整数

43. 字符串相乘

48. 旋转图像

50. Pow(x, n)

60. 排列序列

66. 加一

149. 直线上最多的点数

166. 分数到小数

168. Excel 表列名称

171. Excel 表列序号

172. 阶乘后的零

204. 计数质数

223. 矩形面积

258. 各位相加

263. 丑数

273. 整数转换英文表示

292. Nim 游戏

296. 最佳的碰头地点 🔒

319. 灯泡开关

326. 3 的幂

335. 路径交叉

356. 直线镜像 🔒

372. 超级次方

390. 消除游戏

391. 完美矩形

398. 随机数索引

412. Fizz Buzz