LeetCode Go · 数学与几何（6）

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

来源与许可

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

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

1952. 三除数

简单2 种解法

标签：数学、枚举、数论、筛法、质因数分解

题目、示例与约束

给你一个整数 n 。如果 n 恰好有三个正除数 ，返回 true ；否则，返回 false 。

如果存在整数 k ，满足 n = k * m ，那么整数 m 就是 n 的一个 除数 。

 

示例 1：

输入：n = 2
输出：false
解释：2 只有两个除数：1 和 2 。

示例 2：

输入：n = 4
输出：true
解释：4 有三个除数：1、2 和 4 。

 

提示：

• 1 <= n <= 104

方法一：枚举 · Go 实现

思考

恰有三个正因数的数必为某个素数的平方。 $n$ 不大，枚举 $2$ 到 $n-1$ 统计中间因数个数是否为 $1$ 即可判定。

一个数 $n$ 一定有 $1$ 和 $n$ 两个正除数，因此只需要枚举 $2$ 到 $n-1$ 之间的数，看它们是否是 $n$ 的正除数即可，是则累加计数器，最后判断计数器是否为 $1$ 即可。

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

func isThree(n int) bool {
	cnt := 0
	for i := 2; i < n; i++ {
		if n%i == 0 {
			cnt++
		}
	}
	return cnt == 1
}

方法二：枚举优化 · Go 实现

思考

线性枚举在 $n$ 接近上限时偏慢。改为枚举到 $\sqrt{n}$，每找到因数对计数加二（平方时加一），判断总数是否为 $3$。

我们可以枚举 $1$ 到 $\sqrt{n}$ 之间的数 $i$，如果 $n$ 能被 $i$ 整除，并且 $\frac{n}{i}$ 不等于 $i$，那么计数器累加 $2$，否则计数器累加 $1$。最后判断计数器是否为 $3$ 即可。

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

func isThree(n int) bool {
	cnt := 0
	for i := 1; i <= n/i; i++ {
		if n%i == 0 {
			if n/i == i {
				cnt++
			} else {
				cnt += 2
			}
		}
	}
	return cnt == 3
}

力扣原题 · Doocs 题解来源

1979. 找出数组的最大公约数

简单1 种解法

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

题目、示例与约束

给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。

两个数的 最大公约数 是能够被两个数整除的最大正整数。

 

示例 1：

输入：nums = [2,5,6,9,10]
输出：2
解释：
nums 中最小的数是 2
nums 中最大的数是 10
2 和 10 的最大公约数是 2

示例 2：

输入：nums = [7,5,6,8,3]
输出：1
解释：
nums 中最小的数是 3
nums 中最大的数是 8
3 和 8 的最大公约数是 1

示例 3：

输入：nums = [3,3]
输出：3
解释：
nums 中最小的数是 3
nums 中最大的数是 3
3 和 3 的最大公约数是 3

 

提示：

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

方法一：模拟 · Go 实现

思考

数组的最大公约数等于最大元与最小元的公约数，其余元素不必参与。一遍求两端再调用 $gcd$。

我们根据题意模拟即可，即先找出数组 $\mathit{\text{nums}}$ 中的最大值和最小值，然后求最大值和最小值的最大公约数。

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

func findGCD(nums []int) int {
	a, b := slices.Max(nums), slices.Min(nums)
	return gcd(a, b)
}

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

力扣原题 · Doocs 题解来源

1999. 最小的仅由两个数组成的倍数 🔒

中等1 种解法

标签：数学、枚举

题目、示例与约束

给你三个整数, k, digit1和 digit2, 你想要找到满足以下条件的 最小 整数：

• 大于k 且是 k 的倍数
• 仅由digit1 和 digit2 组成，即 每一位数 均是 digit1 或 digit2

请你返回 最小的满足这两个条件的整数，如果不存在这样的整数，或者最小的满足这两个条件的整数不在32位整数范围（0~231-1），就返回 -1 。

 

示例 1：

输入：k = 2, digit1 = 0, digit2 = 2
输出：20
解释：
20 是第一个仅有数字0和2组成的，比2大且是2的倍数的整数。

示例 2：

输入：k = 3, digit1 = 4, digit2 = 2
输出：24
解释：
24 是第一个仅有数字 2 和 4 组成的，比 3 大且是 3 的倍数的整数。

示例 3：

输入：k = 2, digit1 = 0, digit2 = 0
输出：-1
解释：
不存在仅由 0 组成的比 2 大且是 2 的倍数的整数，因此返回 -1 。

 

提示：

• 1 <= k <= 1000
• 0 <= digit1 <= 9
• 0 <= digit2 <= 9

方法一：BFS · Go 实现

思考

在仅含两个给定数字的整数中找大于 $k$ 的最小倍数。按数值枚举倍数可能很长；按数位 BFS 可按从小到大生成全体合法整数。

两数字先排序，从 $0$ 出发每次在末尾接上其中一个数字。队列保证先短后长、同长则字典序，因而第一个大于 $k$ 且能整除 $k$ 者即最小。超过 $2^{31}-1$ 则无解。

我们观察 $k$ 的范围，发现 $1\le k\le 1000$，因此，如果 $digit1$ 和 $digit2$ 都为 $0$，那么一定不存在满足条件的整数，直接返回 $-1$ 即可。

否则，我们不妨设 $digit1\le digit2$，接下来我们可以使用 BFS 的方法，初始时将整数 $0$ 入队，然后不断地从队首取出一个整数 $x$，如果 $x>2^{31}-1$，那么说明不存在满足条件的整数，直接返回 $-1$ 即可。如果 $x>k$ 且 $xmodk=0$，那么说明找到了满足条件的整数，直接返回 $x$ 即可。否则，我们将其乘以 $10$ 后加上 $digit1$ 和 $digit2$，并将这两个整数入队，继续进行搜索。

时间复杂度 $O({\log }_{10}M)$，空间复杂度 $O({\log }_{10}M)$，其中 $M$ 为 $2^{31}-1$。

func findInteger(k int, digit1 int, digit2 int) int {
	if digit1 == 0 && digit2 == 0 {
		return -1
	}
	if digit1 > digit2 {
		digit1, digit2 = digit2, digit1
	}
	q := []int{0}
	for {
		x := q[0]
		q = q[1:]
		if x > math.MaxInt32 {
			return -1
		}
		if x > k && x%k == 0 {
			return x
		}
		q = append(q, x*10+digit1)
		if digit1 != digit2 {
			q = append(q, x*10+digit2)
		}
	}
}

力扣原题 · Doocs 题解来源

2001. 可互换矩形的组数

中等1 种解法

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

题目、示例与约束

用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形，其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。

如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换 。更规范的说法是，两个矩形满足 widthi/heighti == widthj/heightj（使用实数除法而非整数除法），则认为这两个矩形 可互换 。

计算并返回 rectangles 中有多少对 可互换 矩形。

 

示例 1：

输入：rectangles = [[4,8],[3,6],[10,20],[15,30]]
输出：6
解释：下面按下标（从 0 开始）列出可互换矩形的配对情况：
- 矩形 0 和矩形 1 ：4/8 == 3/6
- 矩形 0 和矩形 2 ：4/8 == 10/20
- 矩形 0 和矩形 3 ：4/8 == 15/30
- 矩形 1 和矩形 2 ：3/6 == 10/20
- 矩形 1 和矩形 3 ：3/6 == 15/30
- 矩形 2 和矩形 3 ：10/20 == 15/30

示例 2：

输入：rectangles = [[4,5],[7,8]]
输出：0
解释：不存在成对的可互换矩形。

 

提示：

• n == rectangles.length
• 1 <= n <= 105
• rectangles[i].length == 2
• 1 <= widthi, heighti <= 105

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

思考

可互换当且仅当宽高比相同。 $n\le {10}^5$，两两比较比值会达到平方级，难以接受。

浮点除法存在精度误差，不能直接用 $w/h$ 作为键。将 $(w,h)$ 除以 $gcd(w,h)$ 后，同一最简分数对应同一对整数。

为此用哈希表统计每个最简对出现次数；每读入一个矩形，先累加已有同比例个数，再写入计数，避免组合数的二次扫描。

为了能够唯一表示矩形，我们需要将矩形的宽高比化简为最简分数。因此，我们可以求出每个矩形的宽高比的最大公约数，然后将宽高比化简为最简分数。接下来，我们使用哈希表统计每个最简分数的矩形数量，然后计算每个最简分数的矩形数量的组合数，即可得到答案。

时间复杂度 $O(n\times \log M)$，空间复杂度 $O(n)$。其中 $n$ 和 $M$ 分别是矩形的数量和矩形的最大边长。

func interchangeableRectangles(rectangles [][]int) int64 {
	ans := 0
	cnt := map[int]int{}
	for _, e := range rectangles {
		w, h := e[0], e[1]
		g := gcd(w, h)
		w, h = w/g, h/g
		x := w*100001 + h
		ans += cnt[x]
		cnt[x]++
	}
	return int64(ans)
}

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

力扣原题 · Doocs 题解来源

2028. 找出缺失的观测数据

中等1 种解法

标签：数组、数学、模拟

题目、示例与约束

现有一份 n + m 次投掷单个 六面 骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。

给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。

返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。

k 个数字的 平均值 为这些数字求和后再除以 k 。

注意 mean 是一个整数，所以 n + m 次投掷的总和需要被 n + m 整除。

 

示例 1：

输入：rolls = [3,2,4,3], mean = 4, n = 2
输出：[6,6]
解释：所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。

示例 2：

输入：rolls = [1,5,6], mean = 3, n = 4
输出：[2,3,2,2]
解释：所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。

示例 3：

输入：rolls = [1,2,3,4], mean = 6, n = 4
输出：[]
解释：无论丢失的 4 次数据是什么，平均值都不可能是 6 。

示例 4：

输入：rolls = [1], mean = 3, n = 1
输出：[5]
解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。

 

提示：

• m == rolls.length
• 1 <= n, m <= 105
• 1 <= rolls[i], mean <= 6

方法一：构造 · Go 实现

思考

缺失 $n$ 个骰子，每个在 $[1,6]$，且全体平均为 $mean$。总和被唯一确定，故只需判断缺失和 $s$ 是否落在 $[n,6n]$。 $n,m\le {10}^5$，构造而非搜索。

可行时把 $s$ 尽量均分：先人人 $s//n$，再给前 $smodn$ 个各加一，均不超过 $6$。

根据题目描述，所有数字之和为 $(n+m)\times \mathit{\text{mean}}$，已知的数字之和为 $\sum _{i=0}^{m-1}\mathit{\text{rolls}}[i]$，那么缺失的数字之和为 $s=(n+m)\times \mathit{\text{mean}}-\sum _{i=0}^{m-1}\mathit{\text{rolls}}[i]$。

如果 $s>n\times 6$ 或者 $s<n$，说明不存在满足条件的答案，返回空数组。

否则，我们可以将 $s$ 平均分配到 $n$ 个数字上，即每个数字的值为 $s/n$，其中 $smodn$ 个数字的值再加上 $1$。

时间复杂度 $O(n+m)$，其中 $n$ 和 $m$ 分别为缺失的数字个数和已知的数字个数。忽略答案的空间消耗，空间复杂度 $O(1)$。

func missingRolls(rolls []int, mean int, n int) []int {
	m := len(rolls)
	s := (n + m) * mean
	for _, v := range rolls {
		s -= v
	}
	if s > n*6 || s < n {
		return []int{}
	}
	ans := make([]int, n)
	for i, j := 0, 0; i < n; i, j = i+1, j+1 {
		ans[i] = s / n
		if j < s%n {
			ans[i]++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2033. 获取单值网格的最小操作数

中等1 种解法

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

题目、示例与约束

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。

每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。

单值网格 是全部元素都相等的网格。

返回使网格化为 单值 网格所需的 最小 操作数。如果不能，返回 -1 。

 

示例 1：

输入：grid = [[2,4],[6,8]], x = 2
输出：4
解释：可以执行下述操作使所有元素都等于 4 ： 
- 2 加 x 一次。
- 6 减 x 一次。
- 8 减 x 两次。
共计 4 次操作。

示例 2：

输入：grid = [[1,5],[2,3]], x = 1
输出：5
解释：可以使所有元素都等于 3 。

示例 3：

输入：grid = [[1,2],[3,4]], x = 2
输出：-1
解释：无法使所有元素相等。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= x, grid[i][j] <= 104

方法一：贪心 · Go 实现

思考

每次只能加减 $x$，故所有格子模 $x$ 必须相同，否则无解。格子数 $\le {10}^5$，要把它们改成同一值 $t$，操作次数为 $\sum |a_i-t|/x$。

该和在中位数处最小。摊平后排序取中位，再累加绝对差除以 $x$。

首先，要使得网格化为单值网格，那么网格的所有元素与 $x$ 的余数必须相同。

因此，我们可以先遍历网格，判断所有元素与 $x$ 的余数是否相同，若不同则返回 $-1$。否则，我们将所有元素放入数组中，对数组进行排序，取中位数，然后遍历数组，计算每个元素与中位数的差值，再除以 $x$，将所有的差值相加，即为答案。

时间复杂度 $O((m\times n)\times \log (m\times n))$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为网格的行数和列数。

func minOperations(grid [][]int, x int) int {
	mod := grid[0][0] % x
	nums := []int{}
	for _, row := range grid {
		for _, v := range row {
			if v%x != mod {
				return -1
			}
			nums = append(nums, v)
		}
	}
	sort.Ints(nums)
	mid := nums[len(nums)>>1]
	ans := 0
	for _, v := range nums {
		ans += abs(v-mid) / x
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

2081. k 镜像数字的和

困难1 种解法

标签：数学、枚举

题目、示例与约束

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。

• 比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
• 相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。

给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。

 

示例 1：

输入：k = 2, n = 5
输出：25
解释：
最小的 5 个 2 镜像数字和它们的二进制表示如下：
  十进制       二进制
    1          1
    3          11
    5          101
    7          111
    9          1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。

示例 2：

输入：k = 3, n = 7
输出：499
解释：
7 个最小的 3 镜像数字和它们的三进制表示如下：
  十进制       三进制
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。

示例 3：

输入：k = 7, n = 17
输出：20379000
解释：17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

 

提示：

• 2 <= k <= 9
• 1 <= n <= 30

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

思考

$n\le 30$，但 $k$ 镜像数随长度稀疏，不能从 $1$ 扫到很大。十进制回文可由前半段唯一确定，枚举量小得多。

按长度折半枚举前半，镜像生成十进制回文，再检验 $k$ 进制是否回文。凑满 $n$ 个后求和。

对于一个 k 镜像数字，我们可以将其分为两部分：前半部分和后半部分。对于偶数长度的数字，前半部分和后半部分完全相同；对于奇数长度的数字，前半部分和后半部分相同，但中间的数字可以是任意数字。

我们可以通过枚举前半部分的数字，然后根据前半部分构造出完整的 k 镜像数字。具体步骤如下：

1. 枚举长度：从 1 开始枚举数字的长度，直到找到满足条件的 k 镜像数字。
2. 计算前半部分的范围：对于长度为 $l$ 的数字，前半部分的范围是 $[{10}^{(l-1)/2},{10}^{(l+1)/2})$。
3. 构造 k 镜像数字：对于每个前半部分的数字 $i$，如果长度为偶数，则直接将 $i$ 作为前半部分；如果长度为奇数，则将 $i$ 除以 10 得到前半部分。然后将前半部分的数字反转并添加到后半部分，构造出完整的 k 镜像数字。
4. 检查 k 镜像数字：将构造出的数字转换为 k 进制，检查其是否是回文数。
5. 累加结果：如果是 k 镜像数字，则将其累加到结果中，并减少计数器 $n$。当计数器 $n$ 减至 0 时，返回结果。

时间复杂度主要取决于枚举的长度和前半部分的范围。由于 $n$ 的最大值为 30，因此在实际操作中，枚举的次数是有限的。空间复杂度 $O(1)$，因为我们只使用了常数级别的额外空间。

func kMirror(k int, n int) int64 {
	check := func(x int64, k int) bool {
		s := []int{}
		for x > 0 {
			s = append(s, int(x%int64(k)))
			x /= int64(k)
		}
		for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
			if s[i] != s[j] {
				return false
			}
		}
		return true
	}

	var ans int64 = 0
	for l := 1; ; l++ {
		x := pow10((l - 1) / 2)
		y := pow10((l + 1) / 2)
		for i := x; i < y; i++ {
			v := int64(i)
			j := i
			if l%2 != 0 {
				j = i / 10
			}
			for j > 0 {
				v = v*10 + int64(j%10)
				j /= 10
			}
			if check(v, k) {
				ans += v
				n--
				if n == 0 {
					return ans
				}
			}
		}
	}
}

func pow10(exp int) int {
	res := 1
	for i := 0; i < exp; i++ {
		res *= 10
	}
	return res
}

力扣原题 · Doocs 题解来源

2117. 一个区间内所有数乘积的缩写

困难1 种解法

标签：数学、数论

题目、示例与约束

给你两个正整数 left 和 right ，满足 left <= right 。请你计算 闭区间 [left, right] 中所有整数的 乘积 。

由于乘积可能非常大，你需要将它按照以下步骤 缩写 ：

1. 统计乘积中 后缀 0 的数目，并 移除 这些 0 ，将这个数目记为 C 。
   • 比方说，1000 中有 3 个后缀 0 ，546 中没有后缀 0 。
2. 将乘积中剩余数字的位数记为 d 。如果 d > 10 ，那么将乘积表示为 <pre>...<suf> 的形式，其中 <pre> 表示乘积最 开始 的 5 个数位，<suf> 表示删除后缀 0 之后 结尾的 5 个数位。如果 d <= 10 ，我们不对它做修改。
   • 比方说，我们将 1234567654321 表示为 12345...54321 ，但是 1234567 仍然表示为 1234567 。
3. 最后，将乘积表示为 字符串 "<pre>...<suf>eC" 。
   • 比方说，12345678987600000 被表示为 "12345...89876e5" 。

请你返回一个字符串，表示 闭区间 [left, right] 中所有整数 乘积 的 缩写 。

 

示例 1：

输入：left = 1, right = 4
输出："24e0"
解释：
乘积为 1 × 2 × 3 × 4 = 24 。
由于没有后缀 0 ，所以 24 保持不变，缩写的结尾为 "e0" 。
因为乘积的结果是 2 位数，小于 10 ，所欲我们不进一步将它缩写。
所以，最终将乘积表示为 "24e0" 。

示例 2：

输入：left = 2, right = 11
输出："399168e2"
解释：乘积为 39916800 。
有 2 个后缀 0 ，删除后得到 399168 。缩写的结尾为 "e2" 。 
删除后缀 0 后是 6 位数，不需要进一步缩写。 
所以，最终将乘积表示为 "399168e2" 。

示例 3：

输入：left = 371, right = 375
输出："7219856259e3"
解释：乘积为 7219856259000 。

 

提示：

• 1 <= left <= right <= 104

方法一 · Go 实现

思考

区间乘积的位数可达数万，直接高精度乘法再截取前后五位代价过大。科学计数法要求去掉尾随零，并在位数超过十时输出前五位、后五位与指数。

尾随零的个数等于因子 $2$ 与 $5$ 的对数的较小值。去掉这些因子后，后缀可用对 ${10}^{10}$ 取模维护最后若干位；前缀则用浮点（或反复除以 $10$）把有效数字压回五位以上的窗口。

为此先统计并扣除 $min({\mathit{\text{cnt}}}_2,{\mathit{\text{cnt}}}_5)$ 个 $2$ 与 $5$，再扫一遍乘积维护 $\mathit{\text{pre}}$ 与 $\mathit{\text{suf}}$；若后缀曾超过 ${10}^{10}$ 则按缩写格式输出，否则输出完整去零结果。

func abbreviateProduct(left int, right int) string {
	cnt2, cnt5 := 0, 0
	for i := left; i <= right; i++ {
		x := i
		for x%2 == 0 {
			cnt2++
			x /= 2
		}
		for x%5 == 0 {
			cnt5++
			x /= 5
		}
	}
	c := int(math.Min(float64(cnt2), float64(cnt5)))
	cnt2 = c
	cnt5 = c
	suf := int64(1)
	pre := float64(1)
	gt := false
	for i := left; i <= right; i++ {
		for suf *= int64(i); cnt2 > 0 && suf%2 == 0; {
			cnt2--
			suf /= int64(2)
		}
		for cnt5 > 0 && suf%5 == 0 {
			cnt5--
			suf /= int64(5)
		}
		if float64(suf) >= 1e10 {
			gt = true
			suf %= int64(1e10)
		}
		for pre *= float64(i); pre > 1e5; {
			pre /= 10
		}
	}
	if gt {
		return fmt.Sprintf("%05d...%05de%d", int(pre), int(suf)%int(1e5), c)
	}
	return fmt.Sprintf("%de%d", suf, c)
}

力扣原题 · Doocs 题解来源

2119. 反转两次的数字

简单1 种解法

标签：数学

题目、示例与约束

反转 一个整数意味着倒置它的所有位。

• 例如，反转 2021 得到 1202 。反转 12300 得到 321 ，不保留前导零 。

给你一个整数 num ，反转 num 得到 reversed1 ，接着反转 reversed1 得到 reversed2 。如果 reversed2 等于 num ，返回 true ；否则，返回 false 。

 

示例 1：

输入：num = 526
输出：true
解释：反转 num 得到 625 ，接着反转 625 得到 526 ，等于 num 。

示例 2：

输入：num = 1800
输出：false
解释：反转 num 得到 81 ，接着反转 81 得到 18 ，不等于 num 。 

示例 3：

输入：num = 0
输出：true
解释：反转 num 得到 0 ，接着反转 0 得到 0 ，等于 num 。

 

提示：

• 0 <= num <= 106

方法一：数学 · Go 实现

思考

反转整数会丢掉前导零，因而第二次反转能否回到原数，取决于第一次是否丢掉了末尾零。对 $num$ 做两次真实反转即可验证，但数字范围虽不大，仍可直接看数位性质。

若 $num=0$，两次反转仍为 $0$。否则，第一次反转丢掉末尾零当且仅当 $num$ 含因子 $10$，即个位为 $0$。

因此当且仅当 $num=0$ 或 $nummod10\ne 0$ 时答案为真。

如果数字是 $0$，或者数字的个位不是 $0$，那么反转两次后的数字一定和原数字相等。

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

func isSameAfterReversals(num int) bool {
	return num == 0 || num%10 != 0
}

力扣原题 · Doocs 题解来源

2125. 银行中的激光束数量

中等1 种解法

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

题目、示例与约束

银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。

对任意两个安全设备而言，如果同时 满足下面两个条件，则二者之间存在 一个 激光束：

• 两个设备位于两个 不同行 ：r1 和 r2 ，其中 r1 < r2 。
• 满足 r1 < i < r2 的 所有 行 i ，都 没有安全设备 。

激光束是独立的，也就是说，一个激光束既不会干扰另一个激光束，也不会与另一个激光束合并成一束。

返回银行中激光束的总数量。

 

示例 1：

输入：bank = ["011001","000000","010100","001000"]
输出：8
解释：在下面每组设备对之间，存在一条激光束。总共是 8 条激光束：
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
注意，第 0 行和第 3 行上的设备之间不存在激光束。
这是因为第 2 行存在安全设备，这不满足第 2 个条件。

示例 2：

输入：bank = ["000","111","000"]
输出：0
解释：不存在两个位于不同行的设备

 

提示：

• m == bank.length
• n == bank[i].length
• 1 <= m, n <= 500
• bank[i][j] 为 '0' 或 '1'

方法一：逐行统计 · Go 实现

思考

激光只存在于两行安全设备之间，且中间行不能再有设备。若枚举行对再检查中间是否全空，行数为 $m$ 时可达 $O(m^2)$ 的行对，再乘上扫行的代价。

相邻两个「非空行」之间的光束数恰为两行设备数之积，中间的空行可以跳过。因此只需按行统计 1 的个数，记住上一非空行的计数。

扫过每一行，若当前计数 $\mathit{\text{cur}}>0$，则累加 $\mathit{\text{pre}}\times \mathit{\text{cur}}$ 并更新 $\mathit{\text{pre}}$。

我们可以逐行统计每行的安全设备数量，如果当前行没有安全设备，直接跳过，否则我们将当前行的安全设备数量乘以前一行的安全设备数量，累加到答案中。然后更新前一行的安全设备数量为当前行的安全设备数量。

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

func numberOfBeams(bank []string) (ans int) {
	pre := 0
	for _, row := range bank {
		if cur := strings.Count(row, "1"); cur > 0 {
			ans += pre * cur
			pre = cur
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2162. 设置时间的最少代价

中等1 种解法

标签：数学、枚举

题目、示例与约束

常见的微波炉可以设置加热时间，且加热时间满足以下条件：

• 至少为 1 秒钟。
• 至多为 99 分 99 秒。

你可以 最多 输入 4 个数字 来设置加热时间。如果你输入的位数不足 4 位，微波炉会自动加 前缀 0 来补足 4 位。微波炉会将设置好的四位数中，前 两位当作分钟数，后 两位当作秒数。它们所表示的总时间就是加热时间。比方说：

• 你输入 9 5 4 （三个数字），被自动补足为 0954 ，并表示 9 分 54 秒。
• 你输入 0 0 0 8 （四个数字），表示 0 分 8 秒。
• 你输入 8 0 9 0 ，表示 80 分 90 秒。
• 你输入 8 1 3 0 ，表示 81 分 30 秒。

给你整数 startAt ，moveCost ，pushCost 和 targetSeconds 。一开始，你的手指在数字 startAt 处。将手指移到 任何其他数字 ，需要花费 moveCost 的单位代价。每 输入你手指所在位置的数字一次，需要花费 pushCost 的单位代价。

要设置 targetSeconds 秒的加热时间，可能会有多种设置方法。你想要知道这些方法中，总代价最小为多少。

请你能返回设置 targetSeconds 秒钟加热时间需要花费的最少代价。

请记住，虽然微波炉的秒数最多可以设置到 99 秒，但一分钟等于 60 秒。

 

示例 1：

输入：startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600
输出：6
解释：以下为设置加热时间的所有方法。
- 1 0 0 0 ，表示 10 分 0 秒。
  手指一开始就在数字 1 处，输入 1 （代价为 1），移到 0 处（代价为 2），输入 0（代价为 1），输入 0（代价为 1），输入 0（代价为 1）。
  总代价为：1 + 2 + 1 + 1 + 1 = 6 。这是所有方案中的最小代价。
- 0 9 6 0，表示 9 分 60 秒。它也表示 600 秒。
  手指移到 0 处（代价为 2），输入 0 （代价为 1），移到 9 处（代价为 2），输入 9（代价为 1），移到 6 处（代价为 2），输入 6（代价为 1），移到 0 处（代价为 2），输入 0（代价为 1）。
  总代价为：2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12 。
- 9 6 0，微波炉自动补全为 0960 ，表示 9 分 60 秒。
  手指移到 9 处（代价为 2），输入 9 （代价为 1），移到 6 处（代价为 2），输入 6（代价为 1），移到 0 处（代价为 2），输入 0（代价为 1）。
  总代价为：2 + 1 + 2 + 1 + 2 + 1 = 9 。

示例 2：

输入：startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76
输出：6
解释：最优方案为输入两个数字 7 6，表示 76 秒。
手指移到 7 处（代价为 1），输入 7 （代价为 2），移到 6 处（代价为 1），输入 6（代价为 2）。总代价为：1 + 2 + 1 + 2 = 6
其他可行方案为 0076 ，076 ，0116 和 116 ，但是它们的代价都比 6 大。

 

提示：

• 0 <= startAt <= 9
• 1 <= moveCost, pushCost <= 105
• 1 <= targetSeconds <= 6039

方法一 · Go 实现

思考

微波炉用四位分钟与秒显示，同一秒数可写成 $m$ 分 $s$ 秒或 $m-1$ 分 $s+60$ 秒（需仍在两位范围内）。代价由指针移动与按键组成，枚举合法四位序列即可。

对一种 $(\mathit{\text{m}},\mathit{\text{s}})$ 去掉前导零后，从 $\mathit{\text{startAt}}$ 起模拟每位是否换指并累加 $\mathit{\text{moveCost}}$、 $\mathit{\text{pushCost}}$。

取 $\mathtt{\text{f}}(m,s)$ 与 $\mathtt{\text{f}}(m-1,s+60)$ 的较小值。

func minCostSetTime(startAt int, moveCost int, pushCost int, targetSeconds int) int {
	m, s := targetSeconds/60, targetSeconds%60
	f := func(m, s int) int {
		if m < 0 || m > 99 || s < 0 || s > 99 {
			return 0x3f3f3f3f
		}
		arr := []int{m / 10, m % 10, s / 10, s % 10}
		i := 0
		for ; i < 4 && arr[i] == 0; i++ {
		}
		t := 0
		prev := startAt
		for ; i < 4; i++ {
			if arr[i] != prev {
				t += moveCost
			}
			t += pushCost
			prev = arr[i]
		}
		return t
	}
	return min(f(m, s), f(m-1, s+60))
}

力扣原题 · Doocs 题解来源

2165. 重排数字的最小值

中等1 种解法

标签：数学、排序

题目、示例与约束

给你一个整数 num 。重排 num 中的各位数字，使其值 最小化 且不含 任何 前导零。

返回不含前导零且值最小的重排数字。

注意，重排各位数字后，num 的符号不会改变。

 

示例 1：

输入：num = 310
输出：103
解释：310 中各位数字的可行排列有：013、031、103、130、301、310 。
不含任何前导零且值最小的重排数字是 103 。

示例 2：

输入：num = -7605
输出：-7650
解释：-7605 中各位数字的部分可行排列为：-7650、-6705、-5076、-0567。
不含任何前导零且值最小的重排数字是 -7650 。

 

提示：

• -1015 <= num <= 1015

方法一：计数 · Go 实现

思考

重排数位：负数十位应尽量大，正数应尽量小且不能有前导零。对数位全排列在位数较多时不必要。

计数 $0$– $9$ 的出现次数。负数从 $9$ 到 $0$ 拼接；正数先拿出一个最小非零数字当首位，再从小到大接上剩余（含零）。

从绝对值统计，最后按符号输出。

我们首先用一个数组 $\mathit{\text{cnt}}$ 记录 $\mathit{\text{num}}$ 中每个数字的出现次数。

如果 $\mathit{\text{num}}$ 是负数，那么数字应该按照从大到小的顺序排列，因此我们从 $9$ 到 $0$ 遍历 $\mathit{\text{cnt}}$，将数字按照出现次数从大到小的顺序排列。

如果是正数，我们首先找到第一个非 $0$ 的数字，将其放在第一位，然后按照从小到大的顺序排列剩余的数字。

时间复杂度 $O(\log n)$，其中 $n$ 为数字 $\mathit{\text{num}}$ 的大小。空间复杂度 $O(1)$。

func smallestNumber(num int64) (ans int64) {
	neg := num < 0
	num = max(num, -num)
	cnt := make([]int, 10)

	for num > 0 {
		cnt[num%10]++
		num /= 10
	}

	if neg {
		for i := 9; i >= 0; i-- {
			for cnt[i] > 0 {
				ans = ans*10 + int64(i)
				cnt[i]--
			}
		}
		return -ans
	}

	if cnt[0] > 0 {
		for i := 1; i < 10; i++ {
			if cnt[i] > 0 {
				cnt[i]--
				ans = int64(i)
				break
			}
		}
	}

	for i := 0; i < 10; i++ {
		for cnt[i] > 0 {
			ans = ans*10 + int64(i)
			cnt[i]--
		}
	}

	return ans
}

力扣原题 · Doocs 题解来源

2169. 得到 0 的操作数

简单2 种解法

标签：数学、模拟

题目、示例与约束

给你两个 非负 整数 num1 和 num2 。

每一步 操作 中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。

• 例如，num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。

返回使 num1 = 0 或 num2 = 0 的 操作数 。

 

示例 1：

输入：num1 = 2, num2 = 3
输出：3
解释：
- 操作 1 ：num1 = 2 ，num2 = 3 。由于 num1 < num2 ，num2 减 num1 得到 num1 = 2 ，num2 = 3 - 2 = 1 。
- 操作 2 ：num1 = 2 ，num2 = 1 。由于 num1 > num2 ，num1 减 num2 。
- 操作 3 ：num1 = 1 ，num2 = 1 。由于 num1 == num2 ，num1 减 num2 。
此时 num1 = 0 ，num2 = 1 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 3 。

示例 2：

输入：num1 = 10, num2 = 10
输出：1
解释：
- 操作 1 ：num1 = 10 ，num2 = 10 。由于 num1 == num2 ，num1 减 num2 得到 num1 = 10 - 10 = 0 。
此时 num1 = 0 ，num2 = 10 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 1 。

 

提示：

• 0 <= num1, num2 <= 105

方法一：模拟 · Go 实现

思考

每次从较大数中减去较小数，直到一方为 $0$，这与辗转相减相同。数值不超过 ${10}^4$，直接模拟步数可接受。

循环中比较 $\mathit{\text{num1}}$ 与 $\mathit{\text{num2}}$，减去较小者并计数。

任一方为 $0$ 时返回计数。

我们可以直接模拟这个过程，循环执行以下操作：

• 如果 $\mathit{\text{num1}}\ge \mathit{\text{num2}}$，则 $\mathit{\text{num1}}=\mathit{\text{num1}}-\mathit{\text{num2}}$；
• 否则， $\mathit{\text{num2}}=\mathit{\text{num2}}-\mathit{\text{num1}}$。
• 每执行一次操作，操作数加一。

当 $\mathit{\text{num1}}$ 或 $\mathit{\text{num2}}$ 有一个为 $0$ 时，停止循环，返回操作数。

时间复杂度 $O(m)$，其中 $m$ 为 $\mathit{\text{num1}}$ 和 $\mathit{\text{num2}}$ 的最大值。空间复杂度 $O(1)$。

func countOperations(num1 int, num2 int) (ans int) {
	for ; num1 != 0 && num2 != 0; ans++ {
		if num1 >= num2 {
			num1 -= num2
		} else {
			num2 -= num1
		}
	}
	return
}

方法二：数学 · Go 实现

思考

方法一在两数相差很大时会减许多次。辗转相减可改成辗转相除：一次加上商、把被减数换成余数。

步数降到 $O(\log m)$，与欧几里得算法同阶。

如果按照方法一的模拟过程，我们会发现，如果 $\mathit{\text{num1}}$ 远大于 $\mathit{\text{num2}}$，那么每次操作我们都会减少 $\mathit{\text{num1}}$ 的值，这样会导致操作数过多。我们可以优化这个过程，每次操作时，我们可以直接将 $\mathit{\text{num1}}$ 除以 $\mathit{\text{num2}}$ 的商加到答案中，然后将 $\mathit{\text{num1}}$ 对 $\mathit{\text{num2}}$ 取余，这样可以减少操作数。

时间复杂度 $O(\log m)$，其中 $m$ 为 $\mathit{\text{num1}}$ 和 $\mathit{\text{num2}}$ 的最大值。空间复杂度 $O(1)$。

func countOperations(num1 int, num2 int) (ans int) {
	for num1 != 0 && num2 != 0 {
		if num1 >= num2 {
			ans += num1 / num2
			num1 %= num2
		} else {
			ans += num2 / num1
			num2 %= num1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2177. 找到和为给定整数的三个连续整数

中等1 种解法

标签：数学、模拟

题目、示例与约束

给你一个整数 num ，请你返回三个连续的整数，它们的 和 为 num 。如果 num 无法被表示成三个连续整数的和，请你返回一个 空 数组。

 

示例 1：

输入：num = 33
输出：[10,11,12]
解释：33 可以表示为 10 + 11 + 12 = 33 。
10, 11, 12 是 3 个连续整数，所以返回 [10, 11, 12] 。

示例 2：

输入：num = 4
输出：[]
解释：没有办法将 4 表示成 3 个连续整数的和。

 

提示：

• 0 <= num <= 1015

方法一：数学 · Go 实现

思考

三个连续整数之和为 $3x$，故 $\mathit{\text{num}}$ 必须是 $3$ 的倍数，此时中间数为 $\mathit{\text{num}}/3$。

整除则返回 $[x-1,x,x+1]$，否则空数组。

判断与构造均为常数时间。

我们假设三个连续的整数分别为 $x-1$, $x$, $x+1$，则它们的和为 $3x$，因此 $\mathit{\text{num}}$ 必须是 $3$ 的倍数。如果 $\mathit{\text{num}}$ 不是 $3$ 的倍数，则无法表示成三个连续整数的和，返回空数组。否则，令 $x=\frac{\mathit{\text{num}}}{3}$，则 $x-1$, $x$, $x+1$ 就是三个连续整数，它们的和为 $\mathit{\text{num}}$。

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

func sumOfThree(num int64) []int64 {
	if num%3 != 0 {
		return []int64{}
	}
	x := num / 3
	return []int64{x - 1, x, x + 1}
}

力扣原题 · Doocs 题解来源

2180. 统计各位数字之和为偶数的整数个数

简单2 种解法

标签：数学、模拟

题目、示例与约束

给你一个正整数 num ，请你统计并返回 小于或等于 num 且各位数字之和为 偶数 的正整数的数目。

正整数的 各位数字之和 是其所有位上的对应数字相加的结果。

 

示例 1：

输入：num = 4
输出：2
解释：
只有 2 和 4 满足小于等于 4 且各位数字之和为偶数。    

示例 2：

输入：num = 30
输出：14
解释：
只有 14 个整数满足小于等于 30 且各位数字之和为偶数，分别是： 
2、4、6、8、11、13、15、17、19、20、22、24、26 和 28 。

 

提示：

• 1 <= num <= 1000

方法一：枚举 · Go 实现

思考

统计 $[1,\mathit{\text{num}}]$ 中数位和为偶数的个数。 $\mathit{\text{num}}\le 1000$，枚举每个数并求数位和即可。

对 $x$ 反复取模累加，偶则计数加一。

实现简单，复杂度带一个 $\log n$ 因子。

一种最简单直接的方法是枚举 $[1,..num]$ 的所有整数 $x$，判断 $x$ 各位数字之和是否为偶数，是则答案加一。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(1)$。其中 $n$ 为 $num$ 的值。

func countEven(num int) (ans int) {
	for i := 1; i <= num; i++ {
		s := 0
		for x := i; x > 0; x /= 10 {
			s += x % 10
		}
		if s%2 == 0 {
			ans++
		}
	}
	return
}

方法二：数学 · Go 实现

思考

方法一随 $\mathit{\text{num}}$ 线性增长。注意到每 $10$ 个连续整数中恰有 $5$ 个数字和为偶数，可先按整十段计算，再处理余数。

整十段贡献 $\lfloor \mathit{\text{num}}/10\rfloor \times 5$，去掉 $0$ 后为减一。余下的个位个数还取决于高位数字和的奇偶，用 $s$ 的最低位调整公式中的偏移。

位数循环只需 $O(\log n)$。

我们观察发现，在 $[0,..x]$ 的所有数中，每 $10$ 个数中，就有 $5$ 个数的各位数字之和为偶数。例如，在 $[0,..9]$ 中，每 $10$ 个数中，就有 $5$ 个数的各位数字之和为偶数，分别是 $0,2,4,6,8$。

因此，我们可以先算出 $num$ 中有多少个 $10$ 的倍数，然后乘以 $5$ 再减去 $1$（排除 $0$ 这个偶数），可以得到初始答案 $ans=\lfloor \frac{num}{10}\rfloor \times 5-1$。

接下来，我们还需要考虑剩下的 $num\mathrm{\%}10+1$ 个数字中，有多少个数的各位数字之和为偶数。这些数字是否是偶数，跟数字的前面数字之和有关，因此，我们可以算出 $num$ 的前面数字之和 $s$，那么剩余的数字中，还有 $\lfloor \frac{num\mathrm{\%}10+2-(s\mathrm{\&}1)}{2}\rfloor$ 个数的各位数字之和为偶数。累加到答案 $ans$ 中即可。

我们不妨举个例子，假设 $num$ 为 $123$，那么前面 $[0,..119]$ 中一共有 $12$ 个 $10$ 的倍数，每个 $10$ 的倍数中有 $5$ 个数的各位数字之和为偶数，因此，初始答案为 $ans=12\times 5-1=59$。

剩下的数字分别是 $120,121,122,123$，每个数字的前两位数字之和为 $s=1+2=3$，是奇数，因此，剩下的数字中，只有 $2$ 个数的各位数字之和为偶数，累加到答案 $ans$ 中，最终答案为 $ans+2=61$。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为 $num$ 的值。

func countEven(num int) (ans int) {
	ans = num/10*5 - 1
	s := 0
	for x := num / 10; x > 0; x /= 10 {
		s += x % 10
	}
	ans += (num%10 + 2 - (s & 1)) >> 1
	return
}

力扣原题 · Doocs 题解来源

2183. 统计可以被 K 整除的下标对数目

困难1 种解法

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

题目、示例与约束

给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：

• 0 <= i < j <= n - 1 且
• nums[i] * nums[j] 能被 k 整除。

 

示例 1：

输入：nums = [1,2,3,4,5], k = 2
输出：7
解释：
共有 7 对下标的对应积可以被 2 整除：
(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)
它们的积分别是 2、4、6、8、10、12 和 20 。
其他下标对，例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ，都无法被 2 整除。    

示例 2：

输入：nums = [1,2,3,4], k = 5
输出：0
解释：不存在对应积可以被 5 整除的下标对。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 105

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可

本站根据 Go 源码整理，非作者原文。

思路：先枚举 k 的全部约数，令 cnt[d] 表示此前元素中能被约数 d 整除的数量。当前值为 v 时，v 与先前值的乘积能被 k 整除，等价于先前值能被 k/gcd(v,k) 整除，因此直接累加对应计数。然后遍历所有约数，把能整除 v 的约数计数加一。先查询、后更新可避免把当前元素与自己配对。

复杂度：设数组长度为 n，k 的约数个数为 D。枚举约数需 O(√k)，每个元素求 gcd 并扫描全部约数；按哈希映射平均常数时间计算，总时间为 O(√k+n(D+log(k+1)))，辅助空间为 O(D)。

// github.com/EndlessCheng/codeforces-go
func coutPairs(nums []int, k int) (ans int64) {
	divisors := []int{}
	for d := 1; d*d <= k; d++ {
		if k%d == 0 {
			divisors = append(divisors, d)
			if d*d < k {
				divisors = append(divisors, k/d)
			}
		}
	}
	cnt := map[int]int{}
	for _, v := range nums {
		ans += int64(cnt[k/gcd(v, k)])
		for _, d := range divisors {
			if v%d == 0 {
				cnt[d]++
			}
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

2217. 找到指定长度的回文数

中等1 种解法

标签：数组、数学

题目、示例与约束

给你一个整数数组 queries 和一个 正 整数 intLength ，请你返回一个数组 answer ，其中 answer[i] 是长度为 intLength 的 正回文数 中第 queries[i] 小的数字，如果不存在这样的回文数，则为 -1 。

回文数 指的是从前往后和从后往前读一模一样的数字。回文数不能有前导 0 。

 

示例 1：

输入：queries = [1,2,3,4,5,90], intLength = 3
输出：[101,111,121,131,141,999]
解释：
长度为 3 的最小回文数依次是：
101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...
第 90 个长度为 3 的回文数是 999 。

示例 2：

输入：queries = [2,4,6], intLength = 4
输出：[1111,1331,1551]
解释：
长度为 4 的前 6 个回文数是：
1001, 1111, 1221, 1331, 1441 和 1551 。

 

提示：

• 1 <= queries.length <= 5 * 104
• 1 <= queries[i] <= 109
• 1 <= intLength <= 15

方法一 · Go 实现

思考

要输出长度为 $\mathit{\text{intLength}}$ 的第 $q$ 个回文数， $q$ 可达 ${10}^9$，长度可达 $15$，既不能按顺序生成全部回文，也不能对每个询问暴力构造。回文由前半段唯一决定：后半段是前半段的镜像。

前半长度为 $\lceil \mathit{\text{intLength}}/2\rceil$，合法前半是从 ${10}^{l-1}$ 到 ${10}^l-1$ 的全体整数。第 $q$ 个对应 $v={10}^{l-1}+q-1$；若 $v$ 越界则答案为 $-1$，否则把 $v$ 的字符串镜像拼上（奇数长度时丢掉中间位的重复）。每个询问 $O(\mathit{\text{intLength}})$。

func kthPalindrome(queries []int, intLength int) []int64 {
	l := (intLength + 1) >> 1
	start, end := int(math.Pow10(l-1)), int(math.Pow10(l))-1
	var ans []int64
	for _, q := range queries {
		v := start + q - 1
		if v > end {
			ans = append(ans, -1)
			continue
		}
		t := v
		if intLength%2 == 1 {
			t /= 10
		}
		for t > 0 {
			v = v*10 + t%10
			t /= 10
		}
		ans = append(ans, int64(v))
	}
	return ans
}

力扣原题 · Doocs 题解来源

2221. 数组的三角和

中等1 种解法

标签：数组、数学、组合数学、数论、模拟

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。

nums 的 三角和 是执行以下操作以后最后剩下元素的值：

1. nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
2. 对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
3. 将 newNums 替换 数组 nums 。
4. 从步骤 1 开始 重复 整个过程。

请你返回 nums 的三角和。

 

示例 1：

输入：nums = [1,2,3,4,5]
输出：8
解释：
上图展示了得到数组三角和的过程。

示例 2：

输入：nums = [5]
输出：5
解释：
由于 nums 中只有一个元素，数组的三角和为这个元素自己。

 

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

方法一：模拟 · Go 实现

思考

每一轮把相邻两数之和模 $10$ 写成新数组，直到剩一个数。 $n\le {10}^3$，模拟 $n$ 轮、第 $k$ 轮做 $k$ 次加法，总时间 $O(n^2)$，可以通过。无需闭式或组合数，按题意原地更新即可。

从长为 $n-1$ 的一轮做到长为 $1$，内层把 $nums[i]$ 写成 $(nums[i]+nums[i+1])mod10$。最后留下的 $nums[0]$ 即三角和。

我们可以直接模拟题目描述的操作，对数组 $\mathit{\text{nums}}$ 进行 $n-1$ 轮操作，每轮操作都按照题目描述的规则更新数组 $\mathit{\text{nums}}$。最后返回数组 $\mathit{\text{nums}}$ 中剩下的唯一元素即可。

时间复杂度 $O(n^2)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func triangularSum(nums []int) int {
	for k := len(nums) - 1; k > 0; k-- {
		for i := 0; i < k; i++ {
			nums[i] = (nums[i] + nums[i+1]) % 10
		}
	}
	return nums[0]
}

力扣原题 · Doocs 题解来源

2235. 两整数相加

简单2 种解法

标签：数学

题目、示例与约束

给你两个整数 num1 和 num2，返回这两个整数的和。

 

示例 1：

输入：num1 = 12, num2 = 5
输出：17
解释：num1 是 12，num2 是 5 ，它们的和是 12 + 5 = 17 ，因此返回 17 。

示例 2：

输入：num1 = -10, num2 = 4
输出：-6
解释：num1 + num2 = -6 ，因此返回 -6 。

 

提示：

• -100 <= num1, num2 <= 100

方法一：使用加法运算符 · Go 实现

思考

求两整数之和，取值范围只有 $[-100,100]$。直接使用语言提供的加法即可在常数时间得到结果，无需额外处理进位。

我们可以直接使用加法运算符 + 来计算两个整数的和。

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

func sum(num1 int, num2 int) int {
	return num1 + num2
}

方法二：位运算（不使用加法运算符） · Go 实现

思考

方法一依赖加法运算符。若不允许使用它，就要在比特上模拟竖式加法：异或给出无进位的和，与运算左移一位给出进位，反复直到进位为 $0$。

Python 整数无限长，需先与 $0\mathtt{\text{xFFFFFFFF}}$ 截成 $32$ 位再循环；若最高位为 $1$，再按补码还原成负数。时间与位数成正比。

我们也可以在不使用加法运算符的前提下，使用位运算来计算两个整数的和。

假设 $num{1}_i$ 和 $num{2}_i$ 分别表示 $num1$ 和 $num2$ 的第 $i$ 个二进制位。一共有 $4$ 种情况：

$num{1}_i$	$num{2}_i$	不进位的和	进位
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

观察可以发现，“不进位的和”与“异或运算”有相同规律，而进位则与“与”运算规律相同，并且需要左移一位。

因此：

• 对两数进行按位 & 与运算，然后左移一位，得到进位，记为 $carry$；
• 对两数进行按位 ^ 异或运算，得到不进位的和；
• 问题转换为求：“不进位的数 + 进位” 之和；
• 循环，直至第二个数为 $0$，返回第一个数即可（也可以用递归实现）。

时间复杂度 $O(\log M)$，其中 $M$ 为题目中数字的最大值。空间复杂度 $O(1)$。

func sum(num1 int, num2 int) int {
	for num2 != 0 {
		carry := (num1 & num2) << 1
		num1 ^= num2
		num2 = carry
	}
	return num1
}

力扣原题 · Doocs 题解来源

2240. 买钢笔和铅笔的方案数

中等1 种解法

标签：数学、枚举

题目、示例与约束

给你一个整数 total ，表示你拥有的总钱数。同时给你两个整数 cost1 和 cost2 ，分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱，去买任意数目的两种笔。

请你返回购买钢笔和铅笔的 不同方案数目 。

 

示例 1：

输入：total = 20, cost1 = 10, cost2 = 5
输出：9
解释：一支钢笔的价格为 10 ，一支铅笔的价格为 5 。
- 如果你买 0 支钢笔，那么你可以买 0 ，1 ，2 ，3 或者 4 支铅笔。
- 如果你买 1 支钢笔，那么你可以买 0 ，1 或者 2 支铅笔。
- 如果你买 2 支钢笔，那么你没法买任何铅笔。
所以买钢笔和铅笔的总方案数为 5 + 3 + 1 = 9 种。

示例 2：

输入：total = 5, cost1 = 10, cost2 = 10
输出：1
解释：钢笔和铅笔的价格都为 10 ，都比拥有的钱数多，所以你没法购买任何文具。所以只有 1 种方案：买 0 支钢笔和 0 支铅笔。

 

提示：

• 1 <= total, cost1, cost2 <= 106

方法一：枚举 · Go 实现

思考

总金额为 $\mathit{\text{total}}$，两种商品单价固定，购买数量不限，求方案数。完全背包在 $\mathit{\text{total}}\le {10}^6$ 时空间偏大，且只需计数。固定钢笔数量后，铅笔的可行个数是一段前缀。

枚举钢笔支数 $x\in [0,\lfloor \mathit{\text{total}}/\mathit{\text{cost1}}\rfloor ]$，剩余金额能买 $0$ 到 $\lfloor (\mathit{\text{total}}-x\cdot \mathit{\text{cost1}})/\mathit{\text{cost2}}\rfloor$ 支铅笔，贡献该值加一。循环长度约为 $\mathit{\text{total}}/\mathit{\text{cost1}}$。

我们可以枚举购买钢笔的数量 $x$，对于每个 $x$，我们最多可以购买铅笔的数量为 $\frac{\mathit{\text{total}}-x\times \mathit{\text{cost1}}}{\mathit{\text{cost2}}}$，那么数量加 $1$ 即为 $x$ 的方案数。我们累加所有的 $x$ 的方案数，即为答案。

时间复杂度 $O(\frac{total}{cost1})$，空间复杂度 $O(1)$。

func waysToBuyPensPencils(total int, cost1 int, cost2 int) (ans int64) {
	for x := 0; x <= total/cost1; x++ {
		y := (total-x*cost1)/cost2 + 1
		ans += int64(y)
	}
	return
}

力扣原题 · Doocs 题解来源

2249. 统计圆内格点数目

中等1 种解法

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

题目、示例与约束

给你一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为 ri 的第 i 个圆，返回出现在 至少一个 圆内的 格点数目 。

注意：

• 格点 是指整数坐标对应的点。
• 圆周上的点 也被视为出现在圆内的点。

 

示例 1：

输入：circles = [[2,2,1]]
输出：5
解释：
给定的圆如上图所示。
出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2)，在图中用绿色标识。
像 (1, 1) 和 (1, 3) 这样用红色标识的点，并未出现在圆内。
因此，出现在至少一个圆内的格点数目是 5 。

示例 2：

输入：circles = [[2,2,2],[3,4,1]]
输出：16
解释：
给定的圆如上图所示。
共有 16 个格点出现在至少一个圆内。
其中部分点的坐标是 (0, 2)、(2, 0)、(2, 4)、(3, 2) 和 (4, 4) 。

 

提示：

• 1 <= circles.length <= 200
• circles[i].length == 3
• 1 <= xi, yi <= 100
• 1 <= ri <= min(xi, yi)

方法一：枚举 · Go 实现

思考

统计至少被一个圆覆盖的整点。圆至多 $200$ 个，坐标与半径不超过 $100$，整点范围很小。对每个圆枚举其外接正方形再判重，需要去重集合；对边界盒内每个整点测试是否落入任一圆，实现更直接。

取所有 $x+r$、 $y+r$ 的最大值作为枚举上界，对每个 $(i,j)$ 检查是否存在圆满足距离平方不超过 $r^2$，命中即计数并跳出。 $O(XYn)$ 在本题范围内可通过。

枚举所有的格点，判断其是否在圆内，如果在圆内，则答案加一。

枚举的时候，可以将所有圆的最大横纵坐标求出来，作为枚举的上界。

时间复杂度 $O(X\times Y\times n)$，空间复杂度 $O(1)$。其中 $X$ 和 $Y$ 分别为所有圆的最大横纵坐标，而 $n$ 为圆的个数。

func countLatticePoints(circles [][]int) (ans int) {
	mx, my := 0, 0
	for _, c := range circles {
		mx = max(mx, c[0]+c[2])
		my = max(my, c[1]+c[2])
	}
	for i := 0; i <= mx; i++ {
		for j := 0; j <= my; j++ {
			for _, c := range circles {
				dx, dy := i-c[0], j-c[1]
				if dx*dx+dy*dy <= c[2]*c[2] {
					ans++
					break
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2280. 表示一个折线图的最少线段数

中等1 种解法

标签：几何、数组、数学、数论、排序

题目、示例与约束

给你一个二维整数数组 stockPrices ，其中 stockPrices[i] = [dayi, pricei] 表示股票在 dayi 的价格为 pricei 。折线图 是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例子：

请你返回要表示一个折线图所需要的 最少线段数 。

 

示例 1：

输入：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
输出：3
解释：
上图为输入对应的图，横坐标表示日期，纵坐标表示价格。
以下 3 个线段可以表示折线图：
- 线段 1 （红色）从 (1,7) 到 (4,4) ，经过 (1,7) ，(2,6) ，(3,5) 和 (4,4) 。
- 线段 2 （蓝色）从 (4,4) 到 (5,4) 。
- 线段 3 （绿色）从 (5,4) 到 (8,1) ，经过 (5,4) ，(6,3) ，(7,2) 和 (8,1) 。
可以证明，无法用少于 3 条线段表示这个折线图。

示例 2：

输入：stockPrices = [[3,4],[1,2],[7,8],[2,3]]
输出：1
解释：
如上图所示，折线图可以用一条线段表示。

 

提示：

• 1 <= stockPrices.length <= 105
• stockPrices[i].length == 2
• 1 <= dayi, pricei <= 109
• 所有 dayi 互不相同 。

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

思考

按日期连折线，共线的连续段只需一条直线。点数 ${10}^5$，日期互异。先按日期排序，再判断相邻两段斜率是否相同。用除法比斜率会有浮点误差，应改成交叉相乘。

维护上一段 $(\mathrm{\Delta }x,\mathrm{\Delta }y)$，若 $\mathrm{\Delta }y\cdot \mathrm{\Delta }{x}_1\ne \mathrm{\Delta }x\cdot \mathrm{\Delta }{y}_1$ 则需要新的一条线。单个点贡献 $0$ 条。

需要注意：

1. 只有一个点时，需要的线段数为 0；
2. 利用除法计算斜率时，会有浮点误差，可以改成乘法比较。

func minimumLines(stockPrices [][]int) int {
	ans := 0
	sort.Slice(stockPrices, func(i, j int) bool { return stockPrices[i][0] < stockPrices[j][0] })
	for i, dx, dy := 1, 0, 1; i < len(stockPrices); i++ {
		x, y := stockPrices[i-1][0], stockPrices[i-1][1]
		x1, y1 := stockPrices[i][0], stockPrices[i][1]
		dx1, dy1 := x1-x, y1-y
		if dy*dx1 != dx*dy1 {
			ans++
		}
		dx, dy = dx1, dy1
	}
	return ans
}

力扣原题 · Doocs 题解来源

2348. 全 0 子数组的数目

中等1 种解法

标签：数组、数学

题目、示例与约束

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

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

 

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

 

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

方法一：遍历计数 · Go 实现

思考

全零子数组由连续零段决定。 $n\le {10}^5$，应按段统计而非枚举两端。

扫过时维护当前连续零个数 $cnt$：遇到 $0$ 则 $cnt$ 加一并把 $cnt$ 累入答案（以该位置结尾的全零段）；遇到非零则清零。

我们遍历数组 $\mathit{\text{nums}}$，用变量 $\mathit{\text{cnt}}$ 记录当前连续的 $0$ 的个数。那么对于当前遍历到的元素 $x$，如果 $x$ 为 $0$，则 $\mathit{\text{cnt}}$ 自增 $1$，以当前 $x$ 为结尾的全 $0$ 子数组的个数为 $\mathit{\text{cnt}}$，将其累加到答案中。否则，我们将 $\mathit{\text{cnt}}$ 置为 $0$。

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

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

相似题目：

• 413. 等差数列划分
• 1513. 仅含 1 的子串数

func zeroFilledSubarray(nums []int) (ans int64) {
	cnt := 0
	for _, x := range nums {
		if x == 0 {
			cnt++
			ans += int64(cnt)
		} else {
			cnt = 0
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2364. 统计坏数对的数目

中等1 种解法

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

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。

请你返回 nums 中 坏数对 的总数目。

 

示例 1：

输入：nums = [4,1,3,3]
输出：5
解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。
数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。
数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。
数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。
数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。
总共有 5 个坏数对，所以我们返回 5 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：没有坏数对。

 

提示：

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

方法一：式子转换 + 哈希表 · Go 实现

思考

坏数对满足 $j-i\ne nums[j]-nums[i]$，即 $i-nums[i]\ne j-nums[j]$。 $n\le {10}^5$，应统计互补的好对。

从左到右扫描，当前下标 $i$ 与此前同余 $i-nums[i]$ 的个数之差即新增坏对，再把该键加一。前缀计数避免双重循环。

根据题目描述，我们可以得知，对于任意的 $i<j$，如果 $j-i\ne \mathit{\text{nums}}[j]-\mathit{\text{nums}}[i]$，则 $(i,j)$ 是一个坏数对。

我们可以将式子转换为 $i-\mathit{\text{nums}}[i]\ne j-\mathit{\text{nums}}[j]$。这启发我们用哈希表 $cnt$ 来统计 $i-\mathit{\text{nums}}[i]$ 的出现次数。

遍历数组，对于当前元素 $\mathit{\text{nums}}[i]$，我们将 $i-cnt[i-\mathit{\text{nums}}[i]]$ 加到答案中，然后将 $i-\mathit{\text{nums}}[i]$ 的出现次数加 $1$。

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

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

func countBadPairs(nums []int) (ans int64) {
	cnt := map[int]int{}
	for i, x := range nums {
		x = i - x
		ans += int64(i - cnt[x])
		cnt[x]++
	}
	return
}

力扣原题 · Doocs 题解来源

2409. 统计共同度过的日子数

简单1 种解法

标签：数学、字符串

题目、示例与约束

Alice 和 Bob 计划分别去罗马开会。

给你四个字符串 arriveAlice ，leaveAlice ，arriveBob 和 leaveBob 。Alice 会在日期 arriveAlice 到 leaveAlice 之间在城市里（日期为闭区间），而 Bob 在日期 arriveBob 到 leaveBob 之间在城市里（日期为闭区间）。每个字符串都包含 5 个字符，格式为 "MM-DD" ，对应着一个日期的月和日。

请你返回 Alice和 Bob 同时在罗马的天数。

你可以假设所有日期都在 同一个 自然年，而且 不是 闰年。每个月份的天数分别为：[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 。

 

示例 1：

输入：arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
输出：3
解释：Alice 从 8 月 15 号到 8 月 18 号在罗马。Bob 从 8 月 16 号到 8 月 19 号在罗马，他们同时在罗马的日期为 8 月 16、17 和 18 号。所以答案为 3 。

示例 2：

输入：arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"
输出：0
解释：Alice 和 Bob 没有同时在罗马的日子，所以我们返回 0 。

 

提示：

• 所有日期的格式均为 "MM-DD" 。
• Alice 和 Bob 的到达日期都 早于或等于 他们的离开日期。
• 题目测试用例所给出的日期均为 非闰年 的有效日期。

方法一：前缀和 · Go 实现

思考

共同天数是两段闭区间的交集长度。逐日枚举全年可以做完，日期却是 $\mathtt{\text{MM-DD}}$，比较和计数都要先落到同一个序号上。

现场把前面各月天数加起来，每次转换都重复同一段常数工作。该格式的字典序与日历顺序一致，交集由较晚的到达日和较早的离开日决定；非闰年各月长度固定，预先求前缀和 $f$ 后，第 $m$ 月 $d$ 日直接对应年内第 $f_{m-1}+d$ 天。

两端日期经 $f$ 换成序号后相减加一，即得交集长度；左端晚于右端则为空。

我们将两个到达日与离开日分别取较晚者和较早者，再用月份天数的前缀和换成当年的第几天，最后计算闭区间长度。

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

var f = [12]int{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}

func countDaysTogether(arriveAlice string, leaveAlice string, arriveBob string, leaveBob string) int {
	start := arriveAlice
	if arriveBob > start {
		start = arriveBob
	}
	end := leaveAlice
	if leaveBob < end {
		end = leaveBob
	}
	d1 := f[int(start[0]-'0')*10+int(start[1]-'0')-1] + int(start[3]-'0')*10 + int(start[4]-'0')
	d2 := f[int(end[0]-'0')*10+int(end[1]-'0')-1] + int(end[3]-'0')*10 + int(end[4]-'0')
	return max(d2-d1+1, 0)
}

力扣原题 · Doocs 题解来源

2413. 最小偶倍数

简单1 种解法

标签：数学、数论

题目、示例与约束

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

 

示例 1：

输入：n = 5
输出：10
解释：5 和 2 的最小公倍数是 10 。

示例 2：

输入：n = 6
输出：6
解释：6 和 2 的最小公倍数是 6 。注意数字会是它自身的倍数。

 

提示：

• 1 <= n <= 150

方法一：数学 · Go 实现

思考

$n\le 150$，求 $2$ 与 $n$ 的最小公倍数。若 $n$ 为偶数，则自身已是 $2$ 的倍数；否则乘 $2$。常数时间即可。

如果 $n$ 为偶数，那么 $2$ 和 $n$ 的最小公倍数就是 $n$ 本身。否则， $2$ 和 $n$ 的最小公倍数就是 $n\times 2$。

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

func smallestEvenMultiple(n int) int {
	if n%2 == 0 {
		return n
	}
	return n * 2
}

力扣原题 · Doocs 题解来源

2417. 最近的公平整数 🔒

中等1 种解法

标签：数学、枚举

题目、示例与约束

给定一个 正整数 n。

如果一个整数 k 中的 偶数 位数与 奇数 位数相等，那么我们称 k 为公平整数。

返回 大于或等于 n 的 最小 的公平整数。

 

示例 1:

输入: n = 2
输出: 10
解释: 大于等于 2 的最小的公平整数是 10。
10是公平整数，因为它的偶数和奇数个数相等 (一个奇数和一个偶数)。

示例 2:

输入: n = 403
输出: 1001
解释: 大于或等于 403 的最小的公平整数是 1001。
1001 是公平整数，因为它有相等数量的偶数和奇数 (两个奇数和两个偶数)。

 

提示:

• 1 <= n <= 109

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

思考

公平整数要求偶数位与奇数位个数相等，故位数必须为偶数。 $n$ 本身可能已公平；否则要找不小于 $n$ 的最近者。

若当前位数 $k$ 为奇数，任何 $k$ 位数都不可能公平，直接构造 $k+1$ 位的最小公平数：最高位为 $1$，低一半为 $1$。若 $k$ 为偶数且 $n$ 尚未公平，则对 $n+1$ 递归，直到落入上述两类之一。

我们记 $n$ 的位数为 $k$，奇数位数、偶数位数分别为 $a$ 和 $b$。

• 若 $a=b$，则 $n$ 本身就是 fair 的，直接返回 $n$ 即可；
• 否则，若 $k$ 为奇数，那么我们找到 $k+1$ 位的最小 fair 数即可，形如 10000111；若 $k$ 为偶数，我们直接暴力递归 closestFair(n+1) 即可。

时间复杂度 $O(\sqrt{n}\times {\log }_{10}n)$。

func closestFair(n int) int {
	a, b := 0, 0
	t, k := n, 0
	for t > 0 {
		if (t%10)%2 == 1 {
			a++
		} else {
			b++
		}
		k++
		t /= 10
	}
	if a == b {
		return n
	}
	if k%2 == 1 {
		x := int(math.Pow(10, float64(k)))
		y := 0
		for i := 0; i < k>>1; i++ {
			y = y*10 + 1
		}
		return x + y
	}
	return closestFair(n + 1)
}

力扣原题 · Doocs 题解来源

2427. 公因子的数目

简单2 种解法

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

题目、示例与约束

给你两个正整数 a 和 b ，返回 a 和 b 的 公 因子的数目。

如果 x 可以同时整除 a 和 b ，则认为 x 是 a 和 b 的一个 公因子 。

 

示例 1：

输入：a = 12, b = 6
输出：4
解释：12 和 6 的公因子是 1、2、3、6 。

示例 2：

输入：a = 25, b = 30
输出：2
解释：25 和 30 的公因子是 1、5 。

 

提示：

• 1 <= a, b <= 1000

方法一：枚举 · Go 实现

思考

公因子必整除 $gcd(a,b)$。 $a,b\le 1000$，枚举 $[1,g]$ 判断是否整除 $g$ 即可，不必分别检查 $a$ 与 $b$。

我们可以先算出 $a$ 和 $b$ 的最大公约数 $g$，然后枚举 $[1,..g]$ 中的每个数，判断其是否是 $g$ 的因子，如果是，则答案加一。

时间复杂度 $O(min(a,b))$，空间复杂度 $O(1)$。

func commonFactors(a int, b int) (ans int) {
	g := gcd(a, b)
	for x := 1; x <= g; x++ {
		if g%x == 0 {
			ans++
		}
	}
	return
}

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

方法二：枚举优化 · Go 实现

思考

方法一已线性扫到 $g$。因子成对出现，枚举到 $\sqrt{g}$ 即可同时计入 $x$ 与 $g/x$（平方时只计一次），时间降为 $O(\sqrt{g})$。

与方法一类似，我们可以先算出 $a$ 和 $b$ 的最大公约数 $g$，然后枚举最大公约数 $g$ 的所有因子，累加答案。

时间复杂度 $O(\sqrt{min(a,b)})$，空间复杂度 $O(1)$。

func commonFactors(a int, b int) (ans int) {
	g := gcd(a, b)
	for x := 1; x*x <= g; x++ {
		if g%x == 0 {
			ans++
			if x*x < g {
				ans++
			}
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

2442. 反转之后不同整数的数目

中等1 种解法

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

题目、示例与约束

给你一个由 正 整数组成的数组 nums 。

你必须取出数组中的每个整数，反转其中每个数位，并将反转后得到的数字添加到数组的末尾。这一操作只针对 nums 中原有的整数执行。

返回结果数组中 不同 整数的数目。

 

示例 1：

输入：nums = [1,13,10,12,31]
输出：6
解释：反转每个数字后，结果数组是 [1,13,10,12,31,1,31,1,21,13] 。
反转后得到的数字添加到数组的末尾并按斜体加粗表示。注意对于整数 10 ，反转之后会变成 01 ，即 1 。
数组中不同整数的数目为 6（数字 1、10、12、13、21 和 31）。

示例 2：

输入：nums = [2,2,2]
输出：1
解释：反转每个数字后，结果数组是 [2,2,2,2,2,2] 。
数组中不同整数的数目为 1（数字 2）。

 

提示：

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

方法一：哈希表 · Go 实现

思考

每个原数及其数位反转都要计入集合。 $n\le {10}^5$、数值 $\le {10}^6$，反转可按字符串倒置。先把原数组放入集合，再逐个插入反转结果，大小即为答案。

我们先用哈希表记录数组中的所有整数，然后遍历数组中的每个整数，对其进行反转，将反转后的整数添加到哈希表中，最后返回哈希表的大小即可。

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

func countDistinctIntegers(nums []int) int {
	s := map[int]struct{}{}
	for _, x := range nums {
		s[x] = struct{}{}
	}
	for _, x := range nums {
		y := 0
		for x > 0 {
			y = y*10 + x%10
			x /= 10
		}
		s[y] = struct{}{}
	}
	return len(s)
}

力扣原题 · Doocs 题解来源

2443. 反转之后的数字和

中等1 种解法

标签：数学、枚举

题目、示例与约束

给你一个 非负 整数 num 。如果存在某个 非负 整数 k 满足 k + reverse(k) = num  ，则返回 true ；否则，返回 false 。

reverse(k) 表示 k 反转每个数位后得到的数字。

 

示例 1：

输入：num = 443
输出：true
解释：172 + 271 = 443 ，所以返回 true 。

示例 2：

输入：num = 63
输出：false
解释：63 不能表示为非负整数及其反转后数字之和，返回 false 。

示例 3：

输入：num = 181
输出：true
解释：140 + 041 = 181 ，所以返回 true 。注意，反转后的数字可能包含前导零。

 

提示：

• 0 <= num <= 105

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

思考

$num\le {10}^5$，在 $[0,num]$ 上枚举 $k$ 并检查 $k+reverse(k)$ 是否等于 $num$。枚举量可接受，按字符串反转即可。

在 $[0,..,num]$ 范围内枚举 $k$，判断 $k+reverse(k)$ 是否等于 $num$ 即可。

时间复杂度 $O(n \times \log n)。其中 $n$ 为 $num$ 的大小。

func sumOfNumberAndReverse(num int) bool {
	for x := 0; x <= num; x++ {
		k, y := x, 0
		for k > 0 {
			y = y*10 + k%10
			k /= 10
		}
		if x+y == num {
			return true
		}
	}
	return false
}

力扣原题 · Doocs 题解来源