LeetCode Go · 数学与几何（5）

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

来源与许可

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

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

1453. 圆形靶内的最大飞镖数量

困难1 种解法

标签：几何、数组、数学

题目、示例与约束

Alice 向一面非常大的墙上掷出 n 支飞镖。给你一个数组 darts ，其中 darts[i] = [xi, yi] 表示 Alice 掷出的第 i 支飞镖落在墙上的位置。

Bob 知道墙上所有 n 支飞镖的位置。他想要往墙上放置一个半径为 r 的圆形靶。使 Alice 掷出的飞镖尽可能多地落在靶上。

给你整数 r ，请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。

 

示例 1 ：

输入：darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
输出：4
解释：如果圆形靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。

示例 2 ：

输入：darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出：5
解释：如果圆形靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。

 

提示：

• 1 <= darts.length <= 100
• darts[i].length == 2
• -104 <= xi, yi <= 104
• darts 中的元素互不相同
• 1 <= r <= 5000

方法一 · Go 实现

思考

$n\le 100$，覆盖最多点的半径为 $r$ 的圆，其最优位置往往使至少两点落在圆周上。枚举点对，若距离不超过 $2r$，可求出两个候选圆心，再数有多少点落入圆内。

单点答案至少为 $1$。浮点比较时对半径加微小误差以免边界漏计。

func numPoints(darts [][]int, r int) int {
	n := len(darts)
	maxDarts := 1
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			for _, c := range possibleCenters(darts[i][0], darts[i][1], darts[j][0], darts[j][1], r) {
				maxDarts = max(maxDarts, countDarts(c[0], c[1], darts, r))
			}
		}
	}
	return maxDarts
}

func possibleCenters(x1, y1, x2, y2, r int) [][2]float64 {
	dx := float64(x2 - x1)
	dy := float64(y2 - y1)
	d := math.Sqrt(dx*dx + dy*dy)
	if d > 2*float64(r) {
		return nil
	}
	midX := float64(x1+x2) / 2
	midY := float64(y1+y2) / 2
	distToCenter := math.Sqrt(float64(r*r) - (d/2)*(d/2))
	offsetX := distToCenter * dy / d
	offsetY := distToCenter * -dx / d
	return [][2]float64{{midX + offsetX, midY + offsetY}, {midX - offsetX, midY - offsetY}}
}

func countDarts(x, y float64, darts [][]int, r int) (count int) {
	for _, dart := range darts {
		if math.Hypot(float64(dart[0])-x, float64(dart[1])-y) <= float64(r)+1e-7 {
			count++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1492. n 的第 k 个因子

中等2 种解法

标签：数学、数论、质因数分解

题目、示例与约束

给你两个正整数 n 和 k 。

如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。

考虑整数 n 的所有因子，将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。

 

示例 1：

输入：n = 12, k = 3
输出：3
解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。

示例 2：

输入：n = 7, k = 2
输出：7
解释：因子列表包括 [1, 7] ，第 2 个因子是 7 。

示例 3：

输入：n = 4, k = 4
输出：-1
解释：因子列表包括 [1, 2, 4] ，只有 3 个因子，所以我们应该返回 -1 。

 

提示：

• 1 <= k <= n <= 1000

 

进阶：

你可以设计时间复杂度小于 O(n) 的算法来解决此问题吗？

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

思考

$n\le 1000$，从 $1$ 扫到 $n$，每遇到因子把 $k$ 减一，减到 $0$ 即第 $k$ 小因子；扫完则不存在。

“因子”是指能整除某个数的数。因此，我们只需要从小到大枚举 $[1,2,..n]$，找到所有能整除 $n$ 的数，然后返回第 $k$ 个即可。

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

func kthFactor(n int, k int) int {
	for i := 1; i <= n; i++ {
		if n%i == 0 {
			k--
			if k == 0 {
				return i
			}
		}
	}
	return -1
}

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

思考

方法一是 $O(n)$。因子成对出现，先枚举到 $\lfloor \sqrt{n}\rfloor$ 收集较小因子；若还不够，再倒序用 $n/i$ 取较大因子，降为 $O(\sqrt{n})$。

我们可以发现，如果 $n$ 有一个因子 $x$，那么 $n$ 一定也有一个因子 $n/x$。

因此，我们先需要枚举 $[1,2,...\lfloor \sqrt{n}\rfloor ]$，找到所有能整除 $n$ 的数，如果找到第 $k$ 个因子，那么直接返回即可。如果没有找到第 $k$ 个因子，那么我们再倒序枚举 $[\lfloor \sqrt{n}\rfloor ,..1]$，找到第 $k$ 个因子即可。

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

func kthFactor(n int, k int) int {
	i := 1
	for ; i < n/i; i++ {
		if n%i == 0 {
			k--
			if k == 0 {
				return i
			}
		}
	}
	if i*i != n {
		i--
	}
	for ; i > 0; i-- {
		if n%(n/i) == 0 {
			k--
			if k == 0 {
				return n / i
			}
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1512. 好数对的数目

简单1 种解法

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

题目、示例与约束

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

 

示例 1：

输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始

示例 2：

输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对

示例 3：

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

 

提示：

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

方法一：计数 · Go 实现

思考

统计满足 $i<j$ 且 $nums[i]=nums[j]$ 的下标对。双重循环在 $n\le 100$ 时可通过，但每次都回头扫描相同值。

对当前 $x$ 而言，它能与此前出现的每一个 $x$ 各组成一对。用计数器记录已扫过的频次，遇到 $x$ 时先把已有次数加入答案再自增，一次遍历即可。

遍历数组，对于每个元素 $x$，计算 $x$ 之前有多少个元素与其相等，即为 $x$ 与之前元素组成的好数对的数目。遍历完数组后，即可得到答案。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为数组长度，而 $C$ 为数组中元素的取值范围。本题中 $C=101$。

func numIdenticalPairs(nums []int) (ans int) {
	cnt := [101]int{}
	for _, x := range nums {
		ans += cnt[x]
		cnt[x]++
	}
	return
}

力扣原题 · Doocs 题解来源

1513. 仅含 1 的子串数

中等1 种解法

标签：数学、字符串

题目、示例与约束

给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

 

示例 1：

输入：s = "0110111"
输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次

示例 2：

输入：s = "101"
输出：2
解释：子字符串 "1" 在 s 中共出现 2 次

示例 3：

输入：s = "111111"
输出：21
解释：每个子字符串都仅由 '1' 组成

示例 4：

输入：s = "000"
输出：0

 

提示：

• s[i] == '0' 或 s[i] == '1'
• 1 <= s.length <= 10^5

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

思考

统计全为 $1$ 的子串个数， $n\le {10}^5$，不能枚举全部 $O(n^2)$ 个子串。被 $0$ 隔开的连续 $1$ 段彼此独立，只需对每段计数。

长度为 $k$ 的全 $1$ 段贡献 $k(k+1)/2$ 个子串，也等价于扫描时维护当前连续 $1$ 长度 $cur$：每多一个 $1$， $cur$ 加一并把 $cur$ 累入答案；遇到 $0$ 则清零。这样不必预先切段。

我们遍历字符串 $s$，用一个变量 $\mathit{\text{cur}}$ 记录当前连续的 1 的个数，用变量 $\mathit{\text{ans}}$ 记录答案。当遍历到字符 $s[i]$ 时，如果 $s[i]=0$，则 $\mathit{\text{cur}}$ 置 0，否则 $\mathit{\text{cur}}$ 自增 1，然后 $\mathit{\text{ans}}$ 自增 $\mathit{\text{cur}}$，并对 ${10}^9+7$ 取模。

遍历结束，返回 $\mathit{\text{ans}}$ 即可。

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

相似题目：

• 413. 等差数列划分
• 2348. 全 0 子数组的数目

func numSub(s string) (ans int) {
	const mod int = 1e9 + 7
	cur := 0
	for _, c := range s {
		if c == '0' {
			cur = 0
		} else {
			cur++
			ans = (ans + cur) % mod
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1515. 服务中心的最佳位置

困难1 种解法

标签：几何、数组、数学、随机化

题目、示例与约束

一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。

给你一个数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个客户在二维地图上的位置，返回到所有客户的 欧几里得距离的最小总和 。

换句话说，请你为服务中心选址，该位置的坐标 [xcentre, ycentre] 需要使下面的公式取到最小值：

与真实值误差在 10-5之内的答案将被视作正确答案。

 

示例 1：

输入：positions = [[0,1],[1,0],[1,2],[2,1]]
输出：4.00000
解释：如图所示，你可以选 [xcentre, ycentre] = [1, 1] 作为新中心的位置，这样一来到每个客户的距离就都是 1，所有距离之和为 4 ，这也是可以找到的最小值。

示例 2：

输入：positions = [[1,1],[3,3]]
输出：2.82843
解释：欧几里得距离可能的最小总和为 sqrt(2) + sqrt(2) = 2.82843

 

提示：

• 1 <= positions.length <= 50
• positions[i].length == 2
• 0 <= xi, yi <= 100

方法一：梯度下降法 · Go 实现

思考

几何中位（费马—韦伯点）使到各客户的欧氏距离之和最小，目标函数对平面坐标可微但没有简单闭式。客户数不大，允许迭代逼近，误差不超过 ${10}^{-5}$。

从质心出发做梯度下降：梯度是各点方向单位向量之和。学习率按 $0.999$ 衰减，并在距离为零处加上微小分母以免除零。步长分量均小于 ${10}^{-6}$ 时停止，返回当前距离和。

我们可以先设定一个初始的服务中心位置为所有客户坐标的几何中心 $(x,y)$。接下来，使用梯度下降法不断迭代，设定一个学习率 $\alpha =0.5$，衰减率 $decay=0.999$。每次一次迭代，计算当前位置到所有客户的距离之和，然后计算当前位置的梯度，最后更新当前位置。当梯度的绝对值都小于 ${10}^{-6}$ 时，停止迭代，返回当前位置到所有客户的距离之和。

func getMinDistSum(positions [][]int) float64 {
	n := len(positions)
	var x, y float64
	for _, p := range positions {
		x += float64(p[0])
		y += float64(p[1])
	}
	x /= float64(n)
	y /= float64(n)
	const decay float64 = 0.999
	const eps float64 = 1e-6
	var alpha float64 = 0.5
	for {
		var gradX, gradY float64
		var dist float64
		for _, p := range positions {
			a := x - float64(p[0])
			b := y - float64(p[1])
			c := math.Sqrt(a*a + b*b)
			gradX += a / (c + 1e-8)
			gradY += b / (c + 1e-8)
			dist += c
		}
		dx := gradX * alpha
		dy := gradY * alpha
		if math.Abs(dx) <= eps && math.Abs(dy) <= eps {
			return dist
		}
		x -= dx
		y -= dy
		alpha *= decay
	}
}

力扣原题 · Doocs 题解来源

1518. 换水问题

简单1 种解法

标签：数学、模拟

题目、示例与约束

超市正在促销，你可以用 numExchange 个空水瓶从超市兑换一瓶水。最开始，你一共购入了 numBottles 瓶水。

如果喝掉了水瓶中的水，那么水瓶就会变成空的。

给你两个整数 numBottles 和 numExchange ，返回你 最多 可以喝到多少瓶水。

 

示例 1：

输入：numBottles = 9, numExchange = 3
输出：13
解释：你可以用 3 个空瓶兑换 1 瓶水。
所以最多能喝到 9 + 3 + 1 = 13 瓶水。

示例 2：

输入：numBottles = 15, numExchange = 4
输出：19
解释：你可以用 4 个空瓶兑换 1 瓶水。
所以最多能喝到 15 + 3 + 1 = 19 瓶水。

 

 

提示：

• 1 <= numBottles <= 100
• 2 <= numExchange <= 100

方法一：模拟 · Go 实现

思考

喝完的空瓶可按 $numExchange$ 个兑换一瓶新酒，问总共能喝多少瓶。数值上限不大，按轮次模拟兑换即可，无需闭式。

先喝掉手上的 $numBottles$ 瓶。每当空瓶数不少于兑换阈值，就拿出 $numExchange$ 个空瓶换回一瓶，喝完后又多一个空瓶，净减少 $numExchange-1$ 个空瓶并给答案加一。直到不够兑换为止。

我们可以直接模拟整个过程。

初始时，我们有 numBottles 瓶水，因此可以喝到 ans = numBottles 瓶水，然后得到 numBottles 个空瓶子。

接下来，如果我们有 numExchange 个空瓶子，那么我们可以用它们兑换一瓶水并喝掉，此时我们剩余的空瓶子数量为 numBottles - numExchange + 1，然后我们累加喝到的水的数量，即 $ans=ans+1$。

最后，返回 ans 即可。

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

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

力扣原题 · Doocs 题解来源

1523. 在区间范围内统计奇数数目

简单1 种解法

标签：数学

题目、示例与约束

给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。

 

示例 1：

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。

示例 2：

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9] 。

 

提示：

• 0 <= low <= high <= 10^9

方法一：前缀和思想 · Go 实现

思考

统计闭区间 $[low,high]$ 中的奇数个数。区间长度可达 ${10}^9$，不能逐个数判断奇偶。

$[0,x]$ 中奇数的个数为 $\lfloor (x+1)/2\rfloor$。因此答案等于 $[0,high]$ 的奇数个数减去 $[0,low-1]$ 的奇数个数，即 $\lfloor (high+1)/2\rfloor -\lfloor low/2\rfloor$，可用移位在常数时间内求出。

我们知道，在 $[0,x]$ 范围内奇数的个数为 $\lfloor \frac{x+1}{2}\rfloor$。因此， $[low,high]$ 范围内奇数的个数为 $\lfloor \frac{high+1}{2}\rfloor -\lfloor \frac{low}{2}\rfloor$。

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

func countOdds(low int, high int) int {
	return ((high + 1) >> 1) - (low >> 1)
}

力扣原题 · Doocs 题解来源

1538. 找出隐藏数组中出现次数最多的元素 🔒

中等1 种解法

标签：数组、数学、交互、摩尔投票算法

题目、示例与约束

给定一个整数数组 nums，且 nums 中的所有整数都为 0 或 1。你不能直接访问这个数组，你需要使用 API ArrayReader ，该 API 含有下列成员函数：

• int query(int a, int b, int c, int d)：其中 0 <= a < b < c < d < ArrayReader.length() 。此函数查询以这四个参数为下标的元素并返回：
  • 4 : 当这四个元素相同（0 或 1）时。
  • 2 : 当其中三个元素的值等于 0 且一个元素等于 1 时，或当其中三个元素的值等于 1 且一个元素等于 0 时。
  • 0 : 当其中两个元素等于 0 且两个元素等于 1 时。
• int length()：返回数组的长度。

你可以调用 query() 最多 2 * n 次，其中 n 等于 ArrayReader.length()。

返回 nums 中出现次数最多的值的任意索引，若所有的值出现次数均相同，返回 -1。

 

示例 1：

输入: nums = [0,0,1,0,1,1,1,1]
输出: 5
解释: API 的调用情况如下：
reader.length() // 返回 8，因为隐藏数组中有 8 个元素。
reader.query(0,1,2,3) // 返回 2，查询元素 nums[0], nums[1], nums[2], nums[3] 间的比较。
// 三个元素等于 0 且一个元素等于 1 或出现相反情况。
reader.query(4,5,6,7) // 返回 4，因为 nums[4], nums[5], nums[6], nums[7] 有相同值。
我们可以推断，最常出现的值在最后 4 个元素中。
索引 2, 4, 6, 7 也是正确答案。

示例 2:

输入: nums = [0,0,1,1,0]
输出: 0

示例 3:

输入: nums = [1,0,1,0,1,0,1,0]
输出: -1

 

提示:

• 5 <= nums.length <= 105
• 0 <= nums[i] <= 1

 

进阶：要找到出现次数最多的元素，需要至少调用 query() 多少次？

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

思考

隐藏数组只含 $0/1$，每次查询四个互异下标返回其中多数情况的编码，要找出多数值的一个下标，查询次数还受限制。不能读出全部元素。

以 $query(0,1,2,3)$ 为基准 $x$。对 $i\ge 4$，若 $query(0,1,2,i)=x$，则 $i$ 与 $3$ 同类，否则与 $3$ 异类。再用三次查询把 $0,1,2$ 分别与 $3$ 比较。较大的一类即多数；两类相等则返回 $-1$。除下标 $3$ 外，异类下标记在 $k$ 中以便输出。

我们先调用 reader.query(0, 1, 2, 3)，将得到的结果记为 $x$。

接下来，我们从下标 $4$ 开始遍历，每次调用 reader.query(0, 1, 2, i)，如果结果与 $x$ 相同，我们就将 $a$ 的值加一，否则将 $b$ 的值加一，同时将 $k$ 的值更新为 $i$。

然后，我们还需要判断下标 $0,1,2$ 与下标 $3$ 的元素是否相同，如果相同，我们将 $a$ 的值加一，否则将 $b$ 的值加一，同时将 $k$ 的值更新为对应的下标。

最后，如果 $a=b$，说明数组中 $0$ 和 $1$ 的个数相同，我们返回 $-1$；否则，如果 $a>b$，返回 $3$，否则返回 $k$。

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

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * type ArrayReader struct {
 * }
 * // Compares 4 different elements in the array
 * // return 4 if the values of the 4 elements are the same (0 or 1).
 * // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
 * // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
 * func (this *ArrayReader) query(a, b, c, d int) int {}
 *
 * // Returns the length of the array
 * func (this *ArrayReader) length() int {}
 */

func guessMajority(reader *ArrayReader) int {
	n := reader.length()
	x := reader.query(0, 1, 2, 3)
	a, b := 1, 0
	k := 0
	for i := 4; i < n; i++ {
		if reader.query(0, 1, 2, i) == x {
			a++
		} else {
			b++
			k = i
		}
	}

	y := reader.query(0, 1, 2, 4)
	if reader.query(1, 2, 3, 4) == y {
		a++
	} else {
		b++
		k = 0
	}
	if reader.query(0, 2, 3, 4) == y {
		a++
	} else {
		b++
		k = 1
	}
	if reader.query(0, 1, 3, 4) == y {
		a++
	} else {
		b++
		k = 2
	}
	if a == b {
		return -1
	}
	if a > b {
		return 3
	}
	return k
}

力扣原题 · Doocs 题解来源

1551. 使数组中所有元素相等的最小操作数

中等1 种解法

标签：数学

题目、示例与约束

存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。

一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的所有元素都 相等 。题目测试用例将会 保证 ：在执行若干步操作后，数组中的所有元素最终可以全部相等。

给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。

 

示例 1：

输入：n = 3
输出：2
解释：arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]

示例 2：

输入：n = 6
输出：9

 

提示：

• 1 <= n <= 10^4

方法一：数学 · Go 实现

思考

数组为 $1,3,5,\dots ,2n-1$，每次把一个数加一、另一个减一，要使所有值相等。模拟每次操作在 $n\le {10}^4$ 时偏慢，且总和守恒给出了目标值。

元素之和为 $n^2$，平均值为 $n$。只需把小于 $n$ 的前一半元素补到 $n$，第 $i$ 个奇数 $2i+1$ 需要 $n-(2i+1)$ 次。对这些缺口求和即得最少操作数。

根据题目描述，数组 $arr$ 是一个首项为 $1$，公差为 $2$ 的等差数列。那么数组前 $n$ 项的和为：

$$\begin{array}{rl}{S}_n& =\frac{n}{2}\times (a_1+a_n)\\ & =\frac{n}{2}\times (1+(2n-1))\\ & =n^2\end{array}$$

由于一次操作中，一个数减一，另一个数加一，数组中所有元素的和不变。因此，数组中所有元素相等时，每个元素的值为 $S_n/n=n$。那么，数组中所有元素相等所需的最小操作数为：

$$\sum _{i=0}\frac{n}{2}(n-(2i+1))$$

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

func minOperations(n int) (ans int) {
	for i := 0; i < n>>1; i++ {
		ans += n - (i<<1 | 1)
	}
	return
}

力扣原题 · Doocs 题解来源

1573. 分割字符串的方案数

中等1 种解法

标签：数学、字符串

题目、示例与约束

给你一个二进制串 s  （一个只包含 0 和 1 的字符串），我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 （s1 + s2 + s3 = s）。

请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。

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

 

示例 1：

输入：s = "10101"
输出：4
解释：总共有 4 种方法将 s 分割成含有 '1' 数目相同的三个子字符串。
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"

示例 2：

输入：s = "1001"
输出：0

示例 3：

输入：s = "0000"
输出：3
解释：总共有 3 种分割 s 的方法。
"0|0|00"
"0|00|0"
"00|0|0"

示例 4：

输入：s = "100100010100110"
输出：12

 

提示：

• s[i] == '0' 或者 s[i] == '1'
• 3 <= s.length <= 10^5

方法一：计数 · Go 实现

思考

把字符串切成三段，使每段中 $1$ 的个数相同。 $n\le {10}^5$，不能枚举两个切点。三段的 $1$ 数必须都等于总数的三分之一。

总数不能被 $3$ 整除则无解；全 $0$ 时任意两个切点都合法，方案为 $C_{n-1}^2$。否则找到第 $cnt$ 与第 $cnt+1$ 个 $1$ 的位置作为第一刀的可选区间，第 $2cnt$ 与第 $2cnt+1$ 个 $1$ 作为第二刀的可选区间，两段长度相乘即方案数。

我们先遍历字符串 $s$，统计其中字符 $1$ 的个数 $cnt$，如果 $cnt$ 不能被 $3$ 整除，那么无法分割，直接返回 $0$。如果 $cnt$ 为 $0$，说明字符串中没有字符 $1$，我们可以在 $n-1$ 个位置中任意选择两个位置，将字符串分割成三个子串，那么方案数就是 $C_{n-1}^2$。

如果 $cnt>0$，我们将 $cnt$ 更新为 $\frac{cnt}{3}$，即每个子串中字符 $1$ 的个数。

接下来我们找到第一个子字符串的右边界的最小下标，记为 $i_1$，第一个子字符串的右边界的最大下标（不包含），记为 $i_2$；第二个子字符串的右边界的最小下标，记为 $j_1$，第二个子字符串的右边界的最大下标（不包含），记为 $j_2$。那么方案数就是 $(i_2-i_1)\times (j_2-j_1)$。

注意答案可能很大，需要对 ${10}^9+7$ 取模。

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

相似题目：

• 927. 三等分

func numWays(s string) int {
	cnt := 0
	for _, c := range s {
		if c == '1' {
			cnt++
		}
	}
	m := cnt % 3
	if m != 0 {
		return 0
	}
	const mod = 1e9 + 7
	n := len(s)
	if cnt == 0 {
		return (n - 1) * (n - 2) / 2 % mod
	}
	cnt /= 3
	find := func(x int) int {
		t := 0
		for i := 0; ; i++ {
			if s[i] == '1' {
				t++
				if t == x {
					return i
				}
			}
		}
	}
	i1, i2 := find(cnt), find(cnt+1)
	j1, j2 := find(cnt*2), find(cnt*2+1)
	return (i2 - i1) * (j2 - j1) % mod
}

力扣原题 · Doocs 题解来源

1688. 比赛中的配对次数

简单1 种解法

标签：数学、模拟

题目、示例与约束

给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：

• 如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
• 如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。

返回在比赛中进行的配对次数，直到决出获胜队伍为止。

 

示例 1：

输入：n = 7
输出：6
解释：比赛详情：
- 第 1 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
- 第 2 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 3 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6

示例 2：

输入：n = 14
输出：13
解释：比赛详情：
- 第 1 轮：队伍数 = 14 ，配对次数 = 7 ，7 支队伍晋级。
- 第 2 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。 
- 第 3 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 4 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 7 + 3 + 2 + 1 = 13

 

提示：

• 1 <= n <= 200

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

思考

每场比赛淘汰一支队伍，产生一名冠军需要淘汰 $n-1$ 支，因此比赛场数恒为 $n-1$，不必按奇偶模拟。

根据题目描述我们知道，一共有 $n$ 支队伍，每一次的配对，都会淘汰一支队伍，所以配对次数就是淘汰的队伍数，即 $n-1$。

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

func numberOfMatches(n int) int {
	return n - 1
}

力扣原题 · Doocs 题解来源

1716. 计算力扣银行的钱

简单1 种解法

标签：数学

题目、示例与约束

Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。

最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。

给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。

 

示例 1：

输入：n = 4
输出：10
解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。

示例 2：

输入：n = 10
输出：37
解释：第 10 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37 。注意到第二个星期一，Hercy 存入 2 块钱。

示例 3：

输入：n = 20
输出：96
解释：第 20 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96 。

 

提示：

• 1 <= n <= 1000

方法一：数学 · Go 实现

思考

第 $k$ 周每天比上一周多存 $1$，完整周与零头都是等差数列。 $n\le 1000$ 虽可逐日累加，闭式求和更直接。

$k=\lfloor n/7\rfloor$ 个完整周的首周和为 $28$，公差 $7$；余下 $b=nmod7$ 天从 $k+1$ 起连续递增。

两段分别用等差求和公式，相加即总存款。

根据题目描述，每周的存款情况如下：

第 1 周：1, 2, 3, 4, 5, 6, 7
第 2 周：2, 3, 4, 5, 6, 7, 8
第 3 周：3, 4, 5, 6, 7, 8, 9
...
第 k 周：k, k+1, k+2, k+3, k+4, k+5, k+6

存款天数为 $n$，那么完整的周数为 $k=\lfloor n/7\rfloor$，剩余天数为 $b=n\mathrm{mod}7$。

完整的 $k$ 周的存款总额，可以通过等差数列求和公式计算：

$$S_1=\frac{k}{2}\times (28+28+7\times (k-1))$$

剩余的 $b$ 天的存款总额，同样可以通过等差数列求和公式计算：

$$S_2=\frac{b}{2}\times (k+1+k+1+b-1)$$

最终的总存款金额为 $S=S_1+S_2$。

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

func totalMoney(n int) int {
	k, b := n/7, n%7
	s1 := (28 + 28 + 7*(k-1)) * k / 2
	s2 := (k + 1 + k + 1 + b - 1) * b / 2
	return s1 + s2
}

力扣原题 · Doocs 题解来源

1742. 盒子中小球的最大数量

简单1 种解法

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

题目、示例与约束

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

 

示例 1：

输入：lowLimit = 1, highLimit = 10
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：2 1 1 1 1 1 1 1 1 0  0  ...
编号 1 的盒子放有最多小球，小球数量为 2 。

示例 2：

输入：lowLimit = 5, highLimit = 15
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：1 1 1 1 2 2 1 1 1 0  0  ...
编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。

示例 3：

输入：lowLimit = 19, highLimit = 28
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...
小球数量：0 1 1 1 1 1 1 1 1 2  0  0  ...
编号 10 的盒子放有最多小球，小球数量为 2 。

 

提示：

• 1 <= lowLimit <= highLimit <= 105

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

思考

盒子编号为各位数字之和。编号不超过 ${10}^5$，数位和小于 $50$，可开定长计数数组。

枚举 $[\mathit{\text{lowLimit}},\mathit{\text{highLimit}}]$，累加数位后 $cnt[y]++$，答案为 $cnt$ 的最大值。

观察题目的数据范围，小球的编号最大不超过 ${10}^5$，那么每个编号的各个位数之和的最大值小于 $50$。因此，我们可以直接开一个长度为 $50$ 的数组 $\mathit{\text{cnt}}$ 来统计每个编号的各个位数之和的数量。

答案就是数组 $\mathit{\text{cnt}}$ 中的最大值。

时间复杂度 $O(n\times {\log }_{10}m)$。其中 $n=\mathit{\text{highLimit}}-\mathit{\text{lowLimit}}+1$，而 $m=\mathit{\text{highLimit}}$。

func countBalls(lowLimit int, highLimit int) (ans int) {
	cnt := [50]int{}
	for i := lowLimit; i <= highLimit; i++ {
		y := 0
		for x := i; x > 0; x /= 10 {
			y += x % 10
		}
		cnt[y]++
		if ans < cnt[y] {
			ans = cnt[y]
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1759. 统计同质子字符串的数目

中等2 种解法

标签：数学、字符串

题目、示例与约束

给你一个字符串 s ，返回 s 中 同质子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。

同质字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同质字符串。

子字符串 是字符串中的一个连续字符序列。

 

示例 1：

输入：s = "abbcccaa"
输出：13
解释：同质子字符串如下所列：
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

示例 2：

输入：s = "xy"
输出：2
解释：同质子字符串是 "x" 和 "y" 。

示例 3：

输入：s = "zzzzz"
输出：15

 

提示：

• 1 <= s.length <= 105
• s 由小写字符串组成。

方法一：双指针 · Go 实现

思考

同构子串必落在一段连续相同字符内。长为 $cnt$ 的段贡献 $cnt(cnt+1)/2$。 $n\le {10}^5$，按段扫描即可。

双指针圈出每段，累加三角形数并对 ${10}^9+7$ 取模。

遍历字符串 $s$，用指针 $i$ 指向当前字符，指针 $j$ 指向下一个不同的字符，那么 $[i,..j-1]$ 区间内的字符都是相同的，假设 $cnt=j-i$，那么该区间内的同构子字符串个数为 $\frac{(1+cnt)\times cnt}{2}$，将其累加到答案中即可。继续遍历，直到指针 $i$ 到达字符串末尾。

遍历完字符串 $s$ 后，返回答案即可。注意答案的取模操作。

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

func countHomogenous(s string) (ans int) {
	n := len(s)
	const mod int = 1e9 + 7
	for i, j := 0, 0; i < n; i = j {
		j = i
		for j < n && s[j] == s[i] {
			j++
		}
		cnt := j - i
		ans += (1 + cnt) * cnt / 2
		ans %= mod
	}
	return
}

方法二 · Go 实现

思考

方法一按段整段求和。也可线性扫：相邻相同则段长加一，否则重置为 $1$，并把当前段长加入答案。避免显式求段边界。

func countHomogenous(s string) int {
	n := len(s)
	const mod int = 1e9 + 7
	ans, cnt := 1, 1
	for i := 1; i < n; i++ {
		if s[i] == s[i-1] {
			cnt++
		} else {
			cnt = 1
		}
		ans = (ans + cnt) % mod
	}
	return ans
}

力扣原题 · Doocs 题解来源

1780. 判断一个数字是否可以表示成三的幂的和

中等1 种解法

标签：数学

题目、示例与约束

给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。

 

示例 1：

输入：n = 12
输出：true
解释：12 = 31 + 32

示例 2：

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

示例 3：

输入：n = 21
输出：false

 

提示：

• 1 <= n <= 107

方法一：数学分析 · Go 实现

思考

判断 $n$ 能否写成若干互异三的幂之和。这等价于三进制里每一位只能是 $0$ 或 $1$，不能出现 $2$。

反复取 $nmod3$，若余数大于 $1$ 则失败，否则整除 $3$ 继续，直到 $n$ 变为 $0$。

我们发现，如果一个数 $n$ 可以表示成若干个“不同的”三的幂之和，那么 $n$ 的三进制表示中，每一位上的数字只能是 $0$ 或者 $1$。

因此，我们将 $n$ 转换成三进制，然后判断每一位上的数字是否是 $0$ 或者 $1$。如果不是，那么 $n$ 就不可以表示成若干个三的幂之和，直接返回 $\mathit{\text{false}}$；否则 $n$ 可以表示成若干个三的幂之和，返回 $\mathit{\text{true}}$。

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

func checkPowersOfThree(n int) bool {
	for n > 0 {
		if n%3 > 1 {
			return false
		}
		n /= 3
	}
	return true
}

力扣原题 · Doocs 题解来源

1806. 还原排列的最少操作步数

中等1 种解法

标签：数组、数学、模拟

题目、示例与约束

给你一个偶数 n​​​​​​ ，已知存在一个长度为 n 的排列 perm ，其中 perm[i] == i​（下标 从 0 开始 计数）。

一步操作中，你将创建一个新数组 arr ，对于每个 i ：

• 如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
• 如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]

然后将 arr​​ 赋值​​给 perm 。

要想使 perm 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。

 

示例 1：

输入：n = 2
输出：1
解释：最初，perm = [0,1]
第 1 步操作后，perm = [0,1]
所以，仅需执行 1 步操作

示例 2：

输入：n = 4
输出：2
解释：最初，perm = [0,1,2,3]
第 1 步操作后，perm = [0,2,1,3]
第 2 步操作后，perm = [0,1,2,3]
所以，仅需执行 2 步操作

示例 3：

输入：n = 6
输出：4

 

提示：

• 2 <= n <= 1000
• n​​​​​​ 是一个偶数

方法一：找规律 + 模拟 · Go 实现

思考

每次操作把前半段映射到偶数下标、后半段映射到奇数下标，问最少几次回到初始排列。若完整模拟整个数组，单轮为 $O(n)$，轮数最坏也是 $O(n)$ 量级，虽然可通过，但不必维护全部位置。

一次操作对每个下标的映射是固定的，除 $0$ 与 $n-1$ 外任意位置回到原处即意味着整个排列复原。跟踪下标 $1$：落在前半则变为 $i\ll 1$，否则变为 $(i-(n\gg 1))\ll 1\mid 1$，直至再次等于 $1$，步数即为答案。

我们观察数字的变化规律，发现：

1. 新数组的偶数位数字依次是原数组的前半段数字；
2. 新数组的奇数位数字依次是原数组的后半段数字。

即，如果原数组的某个数字下标 $i$ 在 [0, n >> 1) 范围内，那么这个数字的新下标就是 i << 1；否则，新下标就是 (i - (n >> 1)) << 1 | 1。

另外，每一轮操作，数字移动的路径都是一样的，只要有一个数字（数字 $0$ 和 $n-1$ 除外）回到了它原来的位置，那么整个序列就和之前的一致了。

因此，我们选择数字 $1$，初始时下标也是 $1$，每次将数字 $1$ 移动到新的位置，直到数字 $1$ 回到原来的位置，就可以得到最小的操作次数。

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

func reinitializePermutation(n int) (ans int) {
	for i := 1; ; {
		ans++
		if i < (n >> 1) {
			i <<= 1
		} else {
			i = (i-(n>>1))<<1 | 1
		}
		if i == 1 {
			return ans
		}
	}
}

力扣原题 · Doocs 题解来源

1808. 好因子的最大数目

困难1 种解法

标签：递归、数学、数论

题目、示例与约束

给你一个正整数 primeFactors 。你需要构造一个正整数 n ，它满足以下条件：

• n 质因数（质因数需要考虑重复的情况）的数目 不超过 primeFactors 个。
• n 好因子的数目最大化。如果 n 的一个因子可以被 n 的每一个质因数整除，我们称这个因子是 好因子 。比方说，如果 n = 12 ，那么它的质因数为 [2,2,3] ，那么 6 和 12 是好因子，但 3 和 4 不是。

请你返回 n 的好因子的数目。由于答案可能会很大，请返回答案对 109 + 7 取余 的结果。

请注意，一个质数的定义是大于 1 ，且不能被分解为两个小于该数的自然数相乘。一个数 n 的质因子是将 n 分解为若干个质因子，且它们的乘积为 n 。

 

示例 1：

输入：primeFactors = 5
输出：6
解释：200 是一个可行的 n 。
它有 5 个质因子：[2,2,2,5,5] ，且有 6 个好因子：[10,20,40,50,100,200] 。
不存在别的 n 有至多 5 个质因子，且同时有更多的好因子。

示例 2：

输入：primeFactors = 8
输出：18

 

提示：

• 1 <= primeFactors <= 109

方法一：问题转换 + 快速幂 · Go 实现

思考

好因子必须含全部质因子各至少一次，其个数等于各质因子指数的乘积，且指数之和不超过 $\mathit{\text{primeFactors}}$。直接枚举分拆方案的数量随 $n$ 增长过快。

问题化为：把整数拆成若干正整数使乘积最大。由整数拆分的经典结论，应尽量拆成 $3$，并避开单独的 $1$（余 $1$ 时改为两个 $2$）。对 $n<4$ 直接返回；否则按 $nmod3$ 分类，用快速幂计算 $3$ 的幂并对 ${10}^9+7$ 取模。

我们可以将 $n$ 进行质因数分解，即 $n=a_1^{k_1}\times a_2^{k_2}\times \cdots \times a_m^{k_m}$，其中 $a_i$ 为质因子，而 $k_i$ 为质因子 $a_i$ 的指数。由于 $n$ 的质因子个数不超过 $primeFactors$ 个，因此 $k_1+k_2+\cdots +k_m\le primeFactors$。

而根据题意描述，我们知道 $n$ 的好因子要满足能被所有的质因子整除，也即是说 $n$ 的好因子需要包含 $a_1\times a_2\times \cdots \times a_m$ 作为因数。那么好因子的个数 $k=k_1\times k_2\times \cdots \times k_m$，即 $k$ 为 $k_1,k_2,\cdots ,k_m$ 的乘积。要最大化好因子的个数，也即是说我们要将 primeFactors 拆分成 $k_1,k_2,\cdots ,k_m$，使得 $k_1\times k_2\times \cdots \times k_m$ 最大。因此问题转换为：将整数 primeFactors 拆分成若干个整数的乘积，使得乘积最大。

接下来，我们只需要分情况讨论。

• 如果 $primeFactors<4$，那么直接返回 primeFactors 即可。
• 如果 $primeFactors$ 为 $3$ 的倍数，那么我们将 primeFactors 拆分成 $3$ 的倍数个 $3$，即 $3^{\frac{primeFactors}{3}}$。
• 如果 $primeFactors$ 除以 $3$ 余 $1$，那么我们将 primeFactors 拆分成 $\frac{primeFactors}{3}-1$ 个 $3$，再乘以 $4$，即 $3^{\frac{primeFactors}{3}-1}\times 4$。
• 如果 $primeFactors$ 除以 $3$ 余 $2$，那么我们将 primeFactors 拆分成 $\frac{primeFactors}{3}$ 个 $3$，再乘以 $2$，即 $3^{\frac{primeFactors}{3}}\times 2$。

以上过程中，我们利用快速幂取模求解。

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

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

力扣原题 · Doocs 题解来源

1812. 判断国际象棋棋盘中一个格子的颜色

简单1 种解法

标签：数学、字符串

题目、示例与约束

给你一个坐标 coordinates ，它是一个字符串，表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。

如果所给格子的颜色是白色，请你返回 true，如果是黑色，请返回 false 。

给定坐标一定代表国际象棋棋盘上一个存在的格子。坐标第一个字符是字母，第二个字符是数字。

 

示例 1：

输入：coordinates = "a1"
输出：false
解释：如上图棋盘所示，"a1" 坐标的格子是黑色的，所以返回 false 。

示例 2：

输入：coordinates = "h3"
输出：true
解释：如上图棋盘所示，"h3" 坐标的格子是白色的，所以返回 true 。

示例 3：

输入：coordinates = "c7"
输出：false

 

提示：

• coordinates.length == 2
• 'a' <= coordinates[0] <= 'h'
• '1' <= coordinates[1] <= '8'

方法一：找规律 · Go 实现

思考

国际象棋棋盘黑白相间，给定坐标判断是否为白格。若按行画出整盘再查表，对单次查询并无必要。

相邻格颜色相反，等价于行号与列号之和的奇偶性交替。把字母与数字转成整数后相加，奇则为白、偶则为黑，常数时间即可判定。

观察棋盘我们发现，颜色相同的两个格子 $(x_1,y_1)$ 和 $(x_2,y_2)$ 满足 $x_1+y_1$ 和 $x_2+y_2$ 均为奇数或偶数。

因此，我们可以根据 $\mathit{\text{coordinates}}$ 获取对应的坐标 $(x,y)$，如果 $x+y$ 为奇数，则格子为白色，返回 $\mathit{\text{true}}$，否则返回 $\mathit{\text{false}}$。

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

func squareIsWhite(coordinates string) bool {
	return (coordinates[0]+coordinates[1])%2 == 1
}

力扣原题 · Doocs 题解来源

1814. 统计一个数组中好对子的数目

中等2 种解法

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

题目、示例与约束

给你一个数组 nums ，数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 ， rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是 好的 ：

• 0 <= i < j < nums.length
• nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

请你返回好下标对的数目。由于结果可能会很大，请将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：nums = [42,11,1,97]
输出：2
解释：两个坐标对为：
 - (0,3)：42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
 - (1,2)：11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。

示例 2：

输入：nums = [13,10,35,24,76]
输出：4

 

提示：

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

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

思考

好数对满足 $nums[i]+rev(nums[j])=nums[j]+rev(nums[i])$。直接枚举 $(i,j)$ 再计算翻转，时间为 $O(n^2\log M)$。 $n\le {10}^5$，无法通过。

移项后条件变为 $nums[i]-rev(nums[i])=nums[j]-rev(nums[j])$。对每个数计算该差值并计数，答案即各差值出现次数的组合数 $C(v,2)$，再对 ${10}^9+7$ 取模。

对于下标对 $(i,j)$，如果满足条件，那么有 $nums[i]+rev(nums[j])=nums[j]+rev(nums[i])$，即 $nums[i]-nums[j]=rev(nums[j])-rev(nums[i])$。

因此，我们可以将 $nums[i]-rev(nums[i])$ 作为哈希表的键，统计每个键出现的次数。最后计算每个键对应的值的组合数，相加得到最终的答案。

注意答案的取模操作。

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

func countNicePairs(nums []int) (ans int) {
	rev := func(x int) (y int) {
		for ; x > 0; x /= 10 {
			y = y*10 + x%10
		}
		return
	}
	cnt := map[int]int{}
	for _, x := range nums {
		y := x - rev(x)
		cnt[y]++
	}
	const mod int = 1e9 + 7
	for _, v := range cnt {
		ans = (ans + v*(v-1)/2) % mod
	}
	return
}

方法二 · Go 实现

思考

方法一先完整计数再求组合数，需要两次遍历哈希表。本题只需无序对数目，可以在从左到右扫描时，用当前差值已经出现的次数累加答案，再把该差值写入表中，避免事后再算 $C(v,2)$。

func countNicePairs(nums []int) (ans int) {
	rev := func(x int) (y int) {
		for ; x > 0; x /= 10 {
			y = y*10 + x%10
		}
		return
	}
	cnt := map[int]int{}
	const mod int = 1e9 + 7
	for _, x := range nums {
		y := x - rev(x)
		ans = (ans + cnt[y]) % mod
		cnt[y]++
	}
	return
}

力扣原题 · Doocs 题解来源

1819. 序列中不同最大公约数的数目

困难1 种解法

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

题目、示例与约束

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

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

• 例如，序列 [4,6,16] 的最大公约数是 2 。

数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

• 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。

 

示例 1：

输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。

示例 2：

输入：nums = [5,15,40,5,6]
输出：7

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 2 * 105

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

思考

子序列的 GCD 种类数最多不超过数组最大值 $mx$，但子序列有 $2^n$ 个， $n\le {10}^5$，不能枚举。

一个数 $x$ 能成为某子序列的 GCD，当且仅当数组中 $x$ 的若干倍数的 GCD 恰好为 $x$。对每个 $x\in [1,mx]$ 枚举其倍数并累积 gcd，一旦得到 $x$ 即可计数并停止。倍数枚举的调和级数总复杂度为 $O(mx\log mx)$。

对于数组 $nums$ 的所有子序列，其最大公约数一定不超过数组中的最大值 $mx$。

因此我们可以枚举 $[1,..mx]$ 中的每个数 $x$，判断 $x$ 是否为数组 $nums$ 的子序列的最大公约数，如果是，则答案加一。

那么问题转换为：判断 $x$ 是否为数组 $nums$ 的子序列的最大公约数。我们可以通过枚举 $x$ 的倍数 $y$，判断 $y$ 是否在数组 $nums$ 中，如果 $y$ 在数组 $nums$ 中，则计算 $y$ 的最大公约数 $g$，如果出现 $g=x$，则 $x$ 是数组 $nums$ 的子序列的最大公约数。

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

func countDifferentSubsequenceGCDs(nums []int) (ans int) {
	mx := slices.Max(nums)
	vis := make([]bool, mx+1)
	for _, x := range nums {
		vis[x] = true
	}
	for x := 1; x <= mx; x++ {
		g := 0
		for y := x; y <= mx; y += x {
			if vis[y] {
				g = gcd(g, y)
				if g == x {
					ans++
					break
				}
			}
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

1822. 数组元素积的符号

简单1 种解法

标签：数组、数学

题目、示例与约束

已知函数 signFunc(x) 将会根据 x 的正负返回特定值：

• 如果 x 是正数，返回 1 。
• 如果 x 是负数，返回 -1 。
• 如果 x 是等于 0 ，返回 0 。

给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。

返回 signFunc(product) 。

 

示例 1：

输入：nums = [-1,-2,-3,-4,3,2,1]
输出：1
解释：数组中所有值的乘积是 144 ，且 signFunc(144) = 1

示例 2：

输入：nums = [1,5,0,2,-3]
输出：0
解释：数组中所有值的乘积是 0 ，且 signFunc(0) = 0

示例 3：

输入：nums = [-1,1,-1,1,-1]
输出：-1
解释：数组中所有值的乘积是 -1 ，且 signFunc(-1) = -1

 

提示：

• 1 <= nums.length <= 1000
• -100 <= nums[i] <= 100

方法一：直接遍历 · Go 实现

思考

乘积的符号只取决于是否出现 $0$ 以及负数的个数。若先算出全部乘积再取符号，中间结果可能溢出。

从左到右维护符号 $ans$，遇 $0$ 立即返回，遇负数则翻转 $ans$。遍历结束即得乘积符号，全程使用常数空间且无需乘法。

题目要求返回数组元素乘积的符号，即正数返回 $1$，负数返回 $-1$， 等于 $0$ 则返回 $0$。

我们可以定义一个答案变量 ans，初始值为 $1$。

然后遍历数组每个元素 $v$，如果 $v$ 为负数，则将 ans 乘上 $-1$，如果 $v$ 为 $0$，则提前返回 $0$。

遍历结束后，返回 ans 即可。

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

func arraySign(nums []int) int {
	ans := 1
	for _, v := range nums {
		if v == 0 {
			return 0
		}
		if v < 0 {
			ans *= -1
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1828. 统计一个圆中点的数目

中等1 种解法

标签：几何、数组、数学

题目、示例与约束

给你一个数组 points ，其中 points[i] = [xi, yi] ，表示第 i 个点在二维平面上的坐标。多个点可能会有 相同 的坐标。

同时给你一个数组 queries ，其中 queries[j] = [xj, yj, rj] ，表示一个圆心在 (xj, yj) 且半径为 rj 的圆。

对于每一个查询 queries[j] ，计算在第 j 个圆 内 点的数目。如果一个点在圆的 边界上 ，我们同样认为它在圆 内 。

请你返回一个数组 answer ，其中 answer[j]是第 j 个查询的答案。

 

示例 1：

输入：points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
输出：[3,2,2]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆。

示例 2：

输入：points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
输出：[2,3,2,4]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆，queries[3] 是紫色的圆。

 

提示：

• 1 <= points.length <= 500
• points[i].length == 2
• 0 <= x​​​​​​i, y​​​​​​i <= 500
• 1 <= queries.length <= 500
• queries[j].length == 3
• 0 <= xj, yj <= 500
• 1 <= rj <= 500
• 所有的坐标都是整数。

方法一：枚举 · Go 实现

思考

对每个询问圆统计有多少给定点落在圆内。点数与询问数均不超过 $500$，平方距离判断为 $O(1)$，双重枚举即可。

不必建空间索引：对每个圆遍历全部点，用 $d{x}^2+d{y}^2\le r^2$ 避免开方。总时间 $O(mn)$ 符合约束。

枚举所有的圆点 $(x,y,r)$，对于每个圆点，计算在圆内的点的个数，即可得到答案。

时间复杂度 $O(m\times n)$，其中 $m$ 和 $n$ 分别为数组 queries 的长度和 points 的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

func countPoints(points [][]int, queries [][]int) (ans []int) {
	for _, q := range queries {
		x, y, r := q[0], q[1], q[2]
		cnt := 0
		for _, p := range points {
			i, j := p[0], p[1]
			dx, dy := i-x, j-y
			if dx*dx+dy*dy <= r*r {
				cnt++
			}
		}
		ans = append(ans, cnt)
	}
	return
}

力扣原题 · Doocs 题解来源

1830. 使字符串有序的最少操作次数

困难1 种解法

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

题目、示例与约束

给你一个字符串 s （下标从 0 开始）。你需要对 s 执行以下操作直到它变为一个有序字符串：

1. 找到 最大下标 i ，使得 1 <= i < s.length 且 s[i] < s[i - 1] 。
2. 找到 最大下标 j ，使得 i <= j < s.length 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] < s[i - 1] 。
3. 交换下标为 i - 1​​​​ 和 j​​​​ 处的两个字符。
4. 将下标 i 开始的字符串后缀反转。

请你返回将字符串变成有序的最少操作次数。由于答案可能会很大，请返回它对 109 + 7 取余 的结果。

 

示例 1：

输入：s = "cba"
输出：5
解释：模拟过程如下所示：
操作 1：i=2，j=2。交换 s[1] 和 s[2] 得到 s="cab" ，然后反转下标从 2 开始的后缀字符串，得到 s="cab" 。
操作 2：i=1，j=2。交换 s[0] 和 s[2] 得到 s="bac" ，然后反转下标从 1 开始的后缀字符串，得到 s="bca" 。
操作 3：i=2，j=2。交换 s[1] 和 s[2] 得到 s="bac" ，然后反转下标从 2 开始的后缀字符串，得到 s="bac" 。
操作 4：i=1，j=1。交换 s[0] 和 s[1] 得到 s="abc" ，然后反转下标从 1 开始的后缀字符串，得到 s="acb" 。
操作 5：i=2，j=2。交换 s[1] 和 s[2] 得到 s="abc" ，然后反转下标从 2 开始的后缀字符串，得到 s="abc" 。

示例 2：

输入：s = "aabaa"
输出：2
解释：模拟过程如下所示：
操作 1：i=3，j=4。交换 s[2] 和 s[4] 得到 s="aaaab" ，然后反转下标从 3 开始的后缀字符串，得到 s="aaaba" 。
操作 2：i=4，j=4。交换 s[3] 和 s[4] 得到 s="aaaab" ，然后反转下标从 4 开始的后缀字符串，得到 s="aaaab" 。

示例 3：

输入：s = "cdbea"
输出：63

示例 4：

输入：s = "leetcodeleetcodeleetcode"
输出：982157772

 

提示：

• 1 <= s.length <= 3000
• s​ 只包含小写英文字母。

方法一：计数 + 排列组合 + 预处理 · Go 实现

思考

一次操作是变成上一个字典序排列，问要多少次才能变成最小排列，即有多少个排列严格小于 $s$。 $|s|\le 3000$，不能枚举排列。

从左到右看每一位：比 $s[i]$ 更小的字母放在该位时，后面是剩余字母的多重排列。用预处理的阶乘与逆元在模 ${10}^9+7$ 下计算 $m\times (n-i-1)!/\prod n_c!$，再从计数中去掉当前字母。各位贡献之和即为答案。

题目中的操作实际上是求当前排列的上一个字典序排列，因此，我们只需要求出比当前排列小的排列的数量，就是答案。

这里我们需要考虑一个问题，给定每一种字母的频率，我们可以构造出多少种不同的排列？

假设总共有 $n$ 个字母，其中字母 $a$ 有 $n_1$ 个，字母 $b$ 有 $n_2$ 个，字母 $c$ 有 $n_3$ 个，那么我们可以构造出 $\frac{n!}{n_1!\times n_2!\times n_3!}$ 种不同的排列。其中 $n=n_1+n_2+n_3$。

我们可以通过预处理的方式，预先计算出所有的阶乘 $f$ 和阶乘的逆元 $g$。其中阶乘的逆元可以通过费马小定理求得。

接下来，我们从左到右遍历字符串 $s$，对于每一个位置 $i$，我们需要求出当前总共有多少个比 $s[i]$ 小的字母，记为 $m$。那么，我们可以构造出 $m\times \frac{(n-i-1)!}{n_1!\times n_2!\cdots \times n_k!}$ 种不同的排列，其中 $k$ 为字母的种类数，累加到答案中。接下来，我们将 $s[i]$ 的频率减一，继续遍历下一个位置。

遍历完整个字符串后，即可得到答案。注意答案的取模操作。

时间复杂度 $O(n\times k)$，空间复杂度 $O(n)$。其中 $n$ 和 $k$ 分别为字符串的长度和字母的种类数。

const n = 3010
const mod = 1e9 + 7

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

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

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

func makeStringSorted(s string) (ans int) {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	for i, c := range s {
		m := 0
		for j := int(c-'a') - 1; j >= 0; j-- {
			m += cnt[j]
		}
		t := m * f[len(s)-i-1] % mod
		for _, v := range cnt {
			t = t * g[v] % mod
		}
		ans = (ans + t + mod) % mod
		cnt[c-'a']--
	}
	return
}

力扣原题 · Doocs 题解来源

1837. K 进制表示下的各位数字总和

简单1 种解法

标签：数学

题目、示例与约束

给你一个整数 n（10 进制）和一个基数 k ，请你将 n 从 10 进制表示转换为 k 进制表示，计算并返回转换后各位数字的 总和 。

转换后，各位数字应当视作是 10 进制数字，且它们的总和也应当按 10 进制表示返回。

 

示例 1：

输入：n = 34, k = 6
输出：9
解释：34 (10 进制) 在 6 进制下表示为 54 。5 + 4 = 9 。

示例 2：

输入：n = 10, k = 10
输出：1
解释：n 本身就是 10 进制。 1 + 0 = 1 。

 

提示：

• 1 <= n <= 100
• 2 <= k <= 10

方法一：数学 · Go 实现

思考

求 $n$ 在 $k$ 进制下各位数字之和。不必先转成字符串。

反复取 $nmodk$ 并整除 $k$，把余数累加直到 $n=0$，即按位展开。

我们将 $n$ 除 $k$ 取余，直至为 $0$，余数相加即可得到结果。

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

func sumBase(n int, k int) (ans int) {
	for n > 0 {
		ans += n % k
		n /= k
	}
	return
}

力扣原题 · Doocs 题解来源

1840. 最高建筑高度

困难1 种解法

标签：数组、数学、排序

题目、示例与约束

在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。

这座城市对这些新建筑有一些规定：

• 每栋建筑的高度必须是一个非负整数。
• 第一栋建筑的高度 必须 是 0 。
• 任意两栋相邻建筑的高度差 不能超过  1 。

除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出，其中 restrictions[i] = [idi, maxHeighti] ，表示建筑 idi 的高度 不能超过 maxHeighti 。

题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在 restrictions 中。

请你返回 最高 建筑能达到的 最高高度 。

 

示例 1：

输入：n = 5, restrictions = [[2,1],[4,1]]
输出：2
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,1,2] ，最高建筑的高度为 2 。

示例 2：

输入：n = 6, restrictions = []
输出：5
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,3,4,5] ，最高建筑的高度为 5 。

示例 3：

输入：n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
输出：5
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,3,3,4,4,5,4,3] ，最高建筑的高度为 5 。

 

提示：

• 2 <= n <= 109
• 0 <= restrictions.length <= min(n - 1, 105)
• 2 <= idi <= n
• idi 是 唯一的 。
• 0 <= maxHeighti <= 109

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

思考

相邻楼高度差至多为 $1$，若干位置还有上限，求可能出现的最大高度。楼数 $n$ 可达 ${10}^9$，不能逐栋模拟。

限制点把数轴分成 $O(m)$ 段。先按编号排序，再左右各传一遍「高度差不能超过距离」，得到每个限制点的真实上界。两限制点之间最优轮廓先升后降，峰高由两端上界与间距的闭式给出，取最大即可。

首先，我们将所有的限制条件按照建筑物的编号从小到大排序。

然后我们从左到右遍历所有的限制条件，对于每个限制条件，我们可以得到一个最高高度的上界，即 $r_i[1]=min(r_i[1],r_{i-1}[1]+r_i[0]-r_{i-1}[0])$，其中 $r_i$ 表示第 $i$ 个限制条件，而 $r_i[0]$ 和 $r_i[1]$ 分别表示建筑物的编号以及建筑物的最高高度的上界。

然后我们从右到左遍历所有的限制条件，对于每个限制条件，我们可以得到一个最高高度的上界，即 $r_i[1]=min(r_i[1],r_{i+1}[1]+r_{i+1}[0]-r_i[0])$。

这样，我们就得到了每个限制建筑物的最高高度的上界。

题目求的是最高建筑物的高度，我们可以枚举相邻两个限制条件之间的建筑物 $i$ 和 $i+1$，要使得高度最大，那么高度应该是先增大后减小，假设最大高度为 $t$，那么 $t-r_i[1]+t-r_{i+1}[1]\le r_{i+1}[0]-r_i[0]$，即 $t\le \frac{r_i[1]+r_{i+1}[1]+r_{i+1}[0]-r_i[0]}{2}$，我们取所有的 $t$ 中的最大值即可。

时间复杂度 $O(m\times \log m)$，空间复杂度 $O(m)$。其中 $m$ 为限制条件的数量。

func maxBuilding(n int, restrictions [][]int) (ans int) {
	r := restrictions
	r = append(r, []int{1, 0})
	sort.Slice(r, func(i, j int) bool { return r[i][0] < r[j][0] })
	if r[len(r)-1][0] != n {
		r = append(r, []int{n, n - 1})
	}
	m := len(r)
	for i := 1; i < m; i++ {
		r[i][1] = min(r[i][1], r[i-1][1]+r[i][0]-r[i-1][0])
	}
	for i := m - 2; i > 0; i-- {
		r[i][1] = min(r[i][1], r[i+1][1]+r[i+1][0]-r[i][0])
	}
	for i := 0; i < m-1; i++ {
		t := (r[i][1] + r[i+1][1] + r[i+1][0] - r[i][0]) / 2
		ans = max(ans, t)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1860. 增长的内存泄露

中等1 种解法

标签：数学、模拟

题目、示例与约束

给你两个整数 memory1 和 memory2 分别表示两个内存条剩余可用内存的位数。现在有一个程序每秒递增的速度消耗着内存。

在第 i 秒（秒数从 1 开始），有 i 位内存被分配到 剩余内存较多 的内存条（如果两者一样多，则分配到第一个内存条）。如果两者剩余内存都不足 i 位，那么程序将 意外退出 。

请你返回一个数组，包含 [crashTime, memory1crash, memory2crash] ，其中 crashTime是程序意外退出的时间（单位为秒）， memory1crash 和 memory2crash 分别是两个内存条最后剩余内存的位数。

 

示例 1：

输入：memory1 = 2, memory2 = 2
输出：[3,1,0]
解释：内存分配如下：
- 第 1 秒，内存条 1 被占用 1 位内存。内存条 1 现在有 1 位剩余可用内存。
- 第 2 秒，内存条 2 被占用 2 位内存。内存条 2 现在有 0 位剩余可用内存。
- 第 3 秒，程序意外退出，两个内存条分别有 1 位和 0 位剩余可用内存。

示例 2：

输入：memory1 = 8, memory2 = 11
输出：[6,0,4]
解释：内存分配如下：
- 第 1 秒，内存条 2 被占用 1 位内存，内存条 2 现在有 10 位剩余可用内存。
- 第 2 秒，内存条 2 被占用 2 位内存，内存条 2 现在有 8 位剩余可用内存。
- 第 3 秒，内存条 1 被占用 3 位内存，内存条 1 现在有 5 位剩余可用内存。
- 第 4 秒，内存条 2 被占用 4 位内存，内存条 2 现在有 4 位剩余可用内存。
- 第 5 秒，内存条 1 被占用 5 位内存，内存条 1 现在有 0 位剩余可用内存。
- 第 6 秒，程序意外退出，两个内存条分别有 0 位和 4 位剩余可用内存。

 

提示：

• 0 <= memory1, memory2 <= 231 - 1

方法一：模拟 · Go 实现

思考

第 $i$ 秒消耗 $i$ 单位内存，优先从当前较大的一根扣除，直到两根都不够。内存可达 $2^{31}-1$，但消耗是平方增长，秒数约为 $\sqrt{m_1+m_2}$，直接模拟即可。

从 $i=1$ 开始，比较两根剩余量，够则减去 $i$ 并递增，否则返回当前秒与剩余。

我们直接模拟内存的分配。

假设 $t$ 为意外退出的时刻，那么两个内存条一定可以容纳 $t-1$ 时刻及以前消耗的内存，因此有：

$$\sum _{i=1}^{t-1}i=\frac{t\times (t-1)}{2}\le (m_1+m_2)$$

时间复杂度 $O(\sqrt{m_1+m_2})$，其中 $m_1$, $m_2$ 分别为两个内存条的内存大小。

func memLeak(memory1 int, memory2 int) []int {
	i := 1
	for ; i <= memory1 || i <= memory2; i++ {
		if memory1 >= memory2 {
			memory1 -= i
		} else {
			memory2 -= i
		}
	}
	return []int{i, memory1, memory2}
}

力扣原题 · Doocs 题解来源

1904. 你完成的完整对局数

中等1 种解法

标签：数学、字符串

题目、示例与约束

一款新的在线电子游戏在近期发布，在该电子游戏中，以 刻钟 为周期规划若干时长为 15 分钟 的游戏对局。这意味着，在 HH:00、HH:15、HH:30 和 HH:45 ，将会开始一个新的对局，其中 HH 用一个从 00 到 23 的整数表示。游戏中使用 24 小时制的时钟 ，所以一天中最早的时间是 00:00 ，最晚的时间是 23:59 。

给你两个字符串 startTime 和 finishTime ，均符合 "HH:MM" 格式，分别表示你 进入 和 退出 游戏的确切时间，请计算在整个游戏会话期间，你完成的 完整对局的对局数 。

• 例如，如果 startTime = "05:20" 且 finishTime = "05:59" ，这意味着你仅仅完成从 05:30 到 05:45 这一个完整对局。而你没有完成从 05:15 到 05:30 的完整对局，因为你是在对局开始后进入的游戏；同时，你也没有完成从 05:45 到 06:00 的完整对局，因为你是在对局结束前退出的游戏。

如果 finishTime 早于 startTime ，这表示你玩了个通宵（也就是从 startTime 到午夜，再从午夜到 finishTime）。

假设你是从 startTime 进入游戏，并在 finishTime 退出游戏，请计算并返回你完成的 完整对局的对局数 。

 

示例 1：

输入：startTime = "12:01", finishTime = "12:44"
输出：1
解释：你完成了从 12:15 到 12:30 的一个完整对局。
你没有完成从 12:00 到 12:15 的完整对局，因为你是在对局开始后的 12:01 进入的游戏。
你没有完成从 12:30 到 12:45 的完整对局，因为你是在对局结束前的 12:44 退出的游戏。

示例 2：

输入：startTime = "20:00", finishTime = "06:00"
输出：40
解释：你完成了从 20:00 到 00:00 的 16 个完整的对局，以及从 00:00 到 06:00 的 24 个完整的对局。
16 + 24 = 40

示例 3：

输入：startTime = "00:00", finishTime = "23:59"
输出：95
解释：除最后一个小时你只完成了 3 个完整对局外，其余每个小时均完成了 4 场完整对局。

 

提示：

• startTime 和 finishTime 的格式为 HH:MM
• 00 <= HH <= 23
• 00 <= MM <= 59
• startTime 和 finishTime 不相等

方法一：转换为分钟数 · Go 实现

思考

完整回合对齐到 $15$ 分钟整点，直接按字符串比较跨日区间容易出错。将时刻化为当天分钟数后，区间长度至多再加 $1440$。

登录时刻须向上取整到下一回合起点，登出时刻须向下取整到上一回合终点，二者之差除以 $15$ 即为完整回合数。

实现上对起点加 $14$ 再整除 $15$，对终点直接整除 $15$，并与 $0$ 取最大，避免登出早于第一个完整回合时得到负数。

我们可以将输入的字符串转换为分钟数 $a$ 和 $b$，如果 $a>b$，则说明跨越了午夜，需要将 $b$ 加上一天的分钟数 $1440$。

然后我们将 $a$ 向上取整到 $15$ 的倍数，将 $b$ 向下取整到 $15$ 的倍数，最后返回 $b$ 与 $a$ 的差值即可，注意要取 $0$ 和 $b-a$ 中的较大值。

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

func numberOfRounds(loginTime string, logoutTime string) int {
	f := func(s string) int {
		var h, m int
		fmt.Sscanf(s, "%d:%d", &h, &m)
		return h*60 + m
	}
	a, b := f(loginTime), f(logoutTime)
	if a > b {
		b += 1440
	}
	return max(0, b/15-(a+14)/15)
}

力扣原题 · Doocs 题解来源

1922. 统计好数字的数目

中等1 种解法

标签：递归、数学

题目、示例与约束

我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。

• 比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是 好数字，因为 3 在偶数下标处但不是偶数。

给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。

一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

 

示例 1：

输入：n = 1
输出：5
解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。

示例 2：

输入：n = 4
输出：400

示例 3：

输入：n = 50
输出：564908303

 

提示：

• 1 <= n <= 1015

方法一：快速幂 · Go 实现

思考

偶下标 $5$ 种选择、奇下标 $4$ 种选择，各位独立相乘。 $n\le {10}^{15}$，不能按位循环累乘。

好数字个数为 $5^{\lceil n/2\rceil }\cdot 4^{\lfloor n/2\rfloor }$。快速幂在模 ${10}^9+7$ 下于对数时间内求出。

长度为 $n$ 的好数字，偶数下标一共有 $\lceil \frac{n}{2}\rceil =\lfloor \frac{n+1}{2}\rfloor$ 位，偶数下标可以填入 $5$ 种数字（ $0,2,4,6,8$）；奇数下标一共有 $\lfloor \frac{n}{2}\rfloor$ 位，奇数下标可以填入 $4$ 种数字（ $2,3,5,7$）。因此长度为 $n$ 的好数字的个数为：

$$ans=5^{\lceil \frac{n}{2}\rceil }\times 4^{\lfloor \frac{n}{2}\rfloor }$$

我们可以使用快速幂来计算 $5^{\lceil \frac{n}{2}\rceil }$ 和 $4^{\lfloor \frac{n}{2}\rfloor }$，时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$。

const mod int64 = 1e9 + 7

func countGoodNumbers(n int64) int {
	return int(myPow(5, (n+1)>>1) * myPow(4, n>>1) % mod)
}

func myPow(x, n int64) int64 {
	var res int64 = 1
	for n != 0 {
		if (n & 1) == 1 {
			res = res * x % mod
		}
		x = x * x % mod
		n >>= 1
	}
	return res
}

力扣原题 · Doocs 题解来源

1924. 安装栅栏 II 🔒

困难1 种解法

标签：几何、数组、数学、最小圆覆盖

题目、示例与约束

给你一个二维整数数组 trees，其中 trees[i] = [xi, yi] 表示花园中第 i 棵树的坐标。

你需要用最少的原材料给花园安装一个 圆形 的栅栏，使花园中所有的树都在被 围在栅栏内部（在栅栏边界上的树也算在内）。

正式地说，你需要求出栅栏的圆心坐标 (x,y) 和半径 r，使花园中所有的树都在圆的内部或边界上，并且让半径 r 最小。

请用一个长度为 3 的数组 [x,y,r] 来返回圆心坐标和半径。如果答案与正确答案的误差不超过 10-5，则该答案将被视为正确答案通过。

 

示例 1:

输入: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [2.00000,2.00000,2.00000]
解释: 栅栏的圆心应当在 (2, 2) 处，半径为 2。

示例 2:

输入: trees = [[1,2],[2,2],[4,2]]
输出: [2.50000,2.00000,1.50000]
解释: 栅栏的圆心应当在 (2.5, 2) 处，半径为 1.5。

 

提示:

• 1 <= trees.length <= 3000
• trees[i].length == 2
• 0 <= xi, yi <= 3000

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

根据题意整理：源文只有最小包围圆思考，没有非空实现。随机打乱后增量维护圆：新点在圆外时令它成为边界点，再逐层固定第二、第三个边界点。两点用直径圆，三点用外接圆；共线时取最远两点的直径圆。圆的比较保留微小绝对容差，计算均用 float64。n 为点数，随机增量期望时间 O(n)，最坏 O(n³)，空间 O(n)；固定局部随机种子使结果可复现。入口 outerTrees 返回 [圆心横坐标, 圆心纵坐标, 半径]，不修改输入。

出处：Doocs 原题与题解，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；题意、参考及本 Go 改写采用 CC BY-SA 4.0。

// 题意与参考：Doocs LeetCode，CC BY-SA 4.0。
// https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1900-1999/1924.Erect%20the%20Fence%20II/README.md
// Go 实现与测试沿用 CC BY-SA 4.0；来源性质见配套说明。
import (
	"math"
	"math/rand"
)

type point struct{ x, y float64 }
type circle struct{ x, y, r float64 }

func contains(c circle, p point) bool { return math.Hypot(c.x-p.x, c.y-p.y) <= c.r+1e-8 }
func diameter(a, b point) circle {
	return circle{(a.x + b.x) / 2, (a.y + b.y) / 2, math.Hypot(a.x-b.x, a.y-b.y) / 2}
}
func throughThree(a, b, c point) circle {
	bx, by, cx, cy := b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y
	d := 2 * (bx*cy - by*cx)
	if math.Abs(d) < 1e-12 {
		best := diameter(a, b)
		for _, v := range []circle{diameter(a, c), diameter(b, c)} {
			if v.r > best.r {
				best = v
			}
		}
		return best
	}
	b2, c2 := bx*bx+by*by, cx*cx+cy*cy
	x := (cy*b2 - by*c2) / d
	y := (bx*c2 - cx*b2) / d
	return circle{a.x + x, a.y + y, math.Hypot(x, y)}
}
func outerTrees(trees [][]int) []float64 {
	ps := make([]point, len(trees))
	for i, p := range trees {
		ps[i] = point{float64(p[0]), float64(p[1])}
	}
	rng := rand.New(rand.NewSource(1924))
	rng.Shuffle(len(ps), func(i, j int) { ps[i], ps[j] = ps[j], ps[i] })
	c := circle{r: -1}
	for i, p := range ps {
		if contains(c, p) {
			continue
		}
		c = circle{p.x, p.y, 0}
		for j := 0; j < i; j++ {
			q := ps[j]
			if contains(c, q) {
				continue
			}
			c = diameter(p, q)
			for k := 0; k < j; k++ {
				if !contains(c, ps[k]) {
					c = throughThree(p, q, ps[k])
				}
			}
		}
	}
	return []float64{c.x, c.y, c.r}
}

力扣原题 · Doocs 题解来源

1925. 统计平方和三元组的数目

简单1 种解法

标签：数学、枚举

题目、示例与约束

一个 平方和三元组 (a,b,c) 指的是满足 a2 + b2 = c2 的 整数 三元组 a，b 和 c 。

给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。

 

示例 1：

输入：n = 5
输出：2
解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。

示例 2：

输入：n = 10
输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。

 

提示：

• 1 <= n <= 250

方法一：枚举 · Go 实现

思考

$n$ 通常不超过 $250$，枚举 $a,b$ 再检验 $a^2+b^2$ 是否为不超过 $n$ 的完全平方，次数为 $O(n^2)$，可以接受。

对每个数对取整数平方根 $c$，若 $c\cdot c$ 还原且 $c\le n$ 则计入。 $a$、 $b$ 独立枚举，故 $(a,b,c)$ 与 $(b,a,c)$ 均统计。

我们在 $[1,n)$ 的范围内枚举 $a$ 和 $b$，然后计算 $c=\sqrt{a^2+b^2}$，如果 $c$ 是整数且 $c\le n$，那么就找到了一个平方和三元组，答案加一。

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

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

func countTriples(n int) (ans int) {
	for a := 1; a < n; a++ {
		for b := 1; b < n; b++ {
			x := a*a + b*b
			c := int(math.Sqrt(float64(x)))
			if c <= n && c*c == x {
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源