LeetCode Go · 数学与几何（2）

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

来源与许可

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

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

415. 字符串相加

简单1 种解法

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

题目、示例与约束

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

 

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

示例 2：

输入：num1 = "456", num2 = "77"
输出："533"

示例 3：

输入：num1 = "0", num2 = "0"
输出："0"

 

 

提示：

• 1 <= num1.length, num2.length <= 104
• num1 和num2 都只包含数字 0-9
• num1 和num2 都不包含任何前导零

方法一：双指针 · Go 实现

思考

大整数以字符串给出，不能先转成整型。加法从低位开始，与竖式相同。

双指针从尾部取数字，连同进位求和，个位写入缓冲区、十位作为新进位。某一串耗尽则当 $0$，直到两串与进位都结束，最后反转。

从低位处理才能正确传播进位；结果先逆序收集，避免反复在头部插入。

我们用两个指针 $i$ 和 $j$ 分别指向两个字符串的末尾，从末尾开始逐位相加。每次取出对应位的数字 $a$ 和 $b$，计算它们的和 $a+b+c$，其中 $c$ 表示上一次相加的进位，最后将 $a+b+c$ 的个位数添加到追加到答案字符串的末尾，然后将 $a+b+c$ 的十位数作为进位 $c$ 的值，循环此过程直至两个字符串的指针都已经指向了字符串的开头并且进位 $c$ 的值为 $0$。

最后将答案字符串反转并返回即可。

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

以下代码还实现了字符串相减，参考 subStrings(num1, num2) 函数。

func addStrings(num1 string, num2 string) string {
	i, j := len(num1)-1, len(num2)-1
	ans := []byte{}
	for c := 0; i >= 0 || j >= 0 || c > 0; i, j = i-1, j-1 {
		if i >= 0 {
			c += int(num1[i] - '0')
		}
		if j >= 0 {
			c += int(num2[j] - '0')
		}
		ans = append(ans, byte(c%10+'0'))
		c /= 10
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return string(ans)
}

func subStrings(num1 string, num2 string) string {
	m, n := len(num1), len(num2)
	neg := m < n || (m == n && num1 < num2)
	if neg {
		num1, num2 = num2, num1
	}
	i, j := len(num1)-1, len(num2)-1
	ans := []byte{}
	for c := 0; i >= 0; i, j = i-1, j-1 {
		c = int(num1[i]-'0') - c
		if j >= 0 {
			c -= int(num2[j] - '0')
		}
		ans = append(ans, byte((c+10)%10+'0'))
		if c < 0 {
			c = 1
		} else {
			c = 0
		}
	}
	for len(ans) > 1 && ans[len(ans)-1] == '0' {
		ans = ans[:len(ans)-1]
	}
	if neg {
		ans = append(ans, '-')
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

423. 从英文中重建数字

中等1 种解法

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

题目、示例与约束

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

 

示例 1：

输入：s = "owoztneoer"
输出："012"

示例 2：

输入：s = "fviefuro"
输出："45"

 

提示：

• 1 <= s.length <= 105
• s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
• s 保证是一个符合题目要求的字符串

方法一 · Go 实现

思考

英文数字的字母互相重叠，不能按单词顺序贪心匹配。若干字母却只属于一个数字。

$\mathtt{\text{z}}$ 只在 zero， $\mathtt{\text{w}}$ 只在 two， $\mathtt{\text{u}}$ 只在 four， $\mathtt{\text{x}}$ 只在 six， $\mathtt{\text{g}}$ 只在 eight。扣掉这些之后， $\mathtt{\text{h}}$、 $\mathtt{\text{f}}$、 $\mathtt{\text{s}}$ 分别确定 three、five、seven，最后用 $\mathtt{\text{o}}$、 $\mathit{\text{i}}$ 确定 one、nine。

按「唯一字母」的偏序计数，每个数字的个数被线性方程组唯一确定，再按 $0$ 到 $9$ 拼回字符串。

func originalDigits(s string) string {
	counter := make([]int, 26)
	for _, c := range s {
		counter[c-'a']++
	}
	cnt := make([]int, 10)
	cnt[0] = counter['z'-'a']
	cnt[2] = counter['w'-'a']
	cnt[4] = counter['u'-'a']
	cnt[6] = counter['x'-'a']
	cnt[8] = counter['g'-'a']

	cnt[3] = counter['h'-'a'] - cnt[8]
	cnt[5] = counter['f'-'a'] - cnt[4]
	cnt[7] = counter['s'-'a'] - cnt[6]

	cnt[1] = counter['o'-'a'] - cnt[0] - cnt[2] - cnt[4]
	cnt[9] = counter['i'-'a'] - cnt[5] - cnt[6] - cnt[8]

	ans := []byte{}
	for i, c := range cnt {
		ans = append(ans, bytes.Repeat([]byte{byte('0' + i)}, c)...)
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

447. 回旋镖的数量

中等2 种解法

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

题目、示例与约束

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的欧式距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

 

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

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

示例 3：

输入：points = [[1,1]]
输出：0

 

提示：

• n == points.length
• 1 <= n <= 500
• points[i].length == 2
• -104 <= xi, yi <= 104
• 所有点都 互不相同

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

思考

回旋镖是有序三元组，枚举三点是 $O(n^3)$。 $i$ 固定后，到 $i$ 距离相同的点可以任意排列成 $j,k$。

枚举中心 $p_1$，用哈希表统计到其余点的距离。每遇到一个已出现 $x$ 次的距离，可与这 $x$ 个点组成 $x$ 个有序对，再乘 $2$ 得到两个方向。

边插入边累加，避免对每个距离再扫一遍哈希表。

我们可以枚举 points 中的每个点作为回旋镖的点 $i$，然后用一个哈希表 $cnt$ 记录其他点到 $i$ 的距离出现的次数。

如果有 $x$ 个点到 $i$ 的距离相等，那么我们可以任选其中 $2$ 个点作为回旋镖的 $j$ 和 $k$，方案数为 $A_x^2=x\times (x-1)$。因此，我们对哈希表中的每个值 $x$，都计算并累加 $A_x^2$，就可以得到满足题目要求的回旋镖数量之和。

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

func numberOfBoomerangs(points [][]int) (ans int) {
	for _, p1 := range points {
		cnt := map[int]int{}
		for _, p2 := range points {
			d := (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
			ans += cnt[d]
			cnt[d]++
		}
	}
	ans <<= 1
	return
}

方法二 · Go 实现

思考

方法一边走边加。也可以先把距离全部计入，再对每个次数 $x$ 累加 $x(x-1)$，即 $A_x^2$。实现更直白，渐近相同。

func numberOfBoomerangs(points [][]int) (ans int) {
	for _, p1 := range points {
		cnt := map[int]int{}
		for _, p2 := range points {
			d := (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
			cnt[d]++
		}
		for _, x := range cnt {
			ans += x * (x - 1)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

453. 最小操作次数使数组元素相等

中等1 种解法

标签：数组、数学

题目、示例与约束

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

 

示例 1：

输入：nums = [1,2,3]
输出：3
解释：
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

示例 2：

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

 

提示：

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 答案保证符合 32-bit 整数

方法一：数学 · Go 实现

思考

每次把 $n-1$ 个数加一，等价于把剩下那个数减一，直到全部等于最小值。模拟加一会改动整个数组。

因此答案是每个数减到最小值的次数之和，即 $\sum nums-n\cdot min(nums)$。

一次求最小与总和即可，不必真的执行操作。

我们不妨记数组 $\mathit{\text{nums}}$ 的最小值为 $\mathit{\text{mi}}$，数组的和为 $\mathit{\text{s}}$，数组的长度为 $\mathit{\text{n}}$。

假设最小操作次数为 $\mathit{\text{k}}$，最终数组的所有元素都为 $\mathit{\text{x}}$，则有：

$$\begin{array}{rl}\mathit{\text{s}}+(\mathit{\text{n}}-1)\times \mathit{\text{k}}& =\mathit{\text{n}}\times \mathit{\text{x}}\\ \mathit{\text{x}}& =\mathit{\text{mi}}+\mathit{\text{k}}\end{array}$$

将第二个式子代入第一个式子，得到：

$$\begin{array}{rl}\mathit{\text{s}}+(\mathit{\text{n}}-1)\times \mathit{\text{k}}& =\mathit{\text{n}}\times (\mathit{\text{mi}}+\mathit{\text{k}})\\ \mathit{\text{s}}+(\mathit{\text{n}}-1)\times \mathit{\text{k}}& =\mathit{\text{n}}\times \mathit{\text{mi}}+\mathit{\text{n}}\times \mathit{\text{k}}\\ \mathit{\text{k}}& =\mathit{\text{s}}-\mathit{\text{n}}\times \mathit{\text{mi}}\end{array}$$

因此，最小操作次数为 $\mathit{\text{s}}-\mathit{\text{n}}\times \mathit{\text{mi}}$。

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

func minMoves(nums []int) int {
	mi := 1 << 30
	s := 0
	for _, x := range nums {
		s += x
		if x < mi {
			mi = x
		}
	}
	return s - mi*len(nums)
}

力扣原题 · Doocs 题解来源

462. 最小操作次数使数组元素相等 II

中等1 种解法

标签：数组、数学、排序

题目、示例与约束

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。

在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。

测试用例经过设计以使答案在 32 位 整数范围内。

 

示例 1：

输入：nums = [1,2,3]
输出：2
解释：
只需要两次操作（每次操作指南使一个元素加 1 或减 1）：
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

示例 2：

输入：nums = [1,10,2,9]
输出：16

 

提示：

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

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

思考

每次把一个数加一或减一，求变成相等的最少次数。目标值若选两端，距离之和会变大。

一维点到汇合点的距离之和在中位数处最小：两端点到汇合点的贡献是常数，问题缩小到内部点。排序后取中位数，累加绝对差。

不必关心最终值是奇数长度的正中还是偶数长度的两个中位之一，二者距离和相同。

这个问题可以抽象为，在数轴上有 $n$ 个点，找到一个点使得所有点到该点的距离之和最小。答案为 $n$ 个点的中位数。

中位数有这样的性质：所有数与中位数的距离之和最小。

证明：

首先，给定一个从小到大的数列 $a_1,a_2,\cdots ,a_n$，我们假设 $x$ 是从 $a_1$ 到 $a_n$ 与其距离之和最小的点，显然 $x$ 必须位于 $a_1$ 和 $a_n$ 之间。而由于 $a_1$ 与 $a_n$ 与 $x$ 的距离之和都相等，都等于 $a_n-a_1$，因此，接下来不考虑 $a_1$ 和 $a_n$，我们只考虑 $a_2,a_3,\cdots ,a_{n-1}$，这样的话，我们就可以把问题转化为在 $a_2,a_3,\cdots ,a_{n-1}$ 中找到一个点与其距离之和最小，依此类推，我们最后可以得出结论：在一个数列中，中位数与其余数的距离之和最小。

在这个问题中，我们可以先对数组进行排序，然后找到中位数，最后计算所有数与中位数的距离之和即可。

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

相似题目：

• 296. 最佳的碰头地点
• 2448. 使数组相等的最小开销

func minMoves2(nums []int) int {
	sort.Ints(nums)
	k := nums[len(nums)>>1]
	ans := 0
	for _, v := range nums {
		ans += abs(v - k)
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

469. 凸多边形 🔒

中等1 种解法

标签：几何、数组、数学、多边形

题目、示例与约束

给定 X-Y 平面上的一组点 points ，其中 points[i] = [xi, yi] 。这些点按顺序连成一个多边形。

如果该多边形为 凸 多边形（凸多边形的定义）则返回 true ，否则返回 false 。

你可以假设由给定点构成的多边形总是一个 简单的多边形（简单多边形的定义）。换句话说，我们要保证每个顶点处恰好是两条边的汇合点，并且这些边 互不相交 。

 

示例 1：

输入: points = [[0,0],[0,5],[5,5],[5,0]]
输出: true

示例 2：

输入: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
输出: false

 

提示:

• 3 <= points.length <= 104
• points[i].length == 2
• -104 <= xi, yi <= 104
• 所有点都 不同

 

方法一：数学（向量叉积） · Go 实现

思考

凸多边形要求所有转向同号。枚举每三个顶点的夹角方向即可，不必求凸包。

对顶点 $i$，算 $\overrightarrow{p_i{p}_{i+1}}\times \overrightarrow{p_i{p}_{i+2}}$。叉积非零时若与上一次非零叉积异号，则出现凹角。共线（叉积为 $0$）不更新方向。

下标对 $n$ 取模封闭多边形。只在转向真正发生时比较符号，共线点不会误判。

假设当前连续的三个顶点分别为 $p_1,p_2,p_3$，我们可以计算向量 $\overrightarrow{p_1{p}_2}$ 和 $\overrightarrow{p_1{p}_3}$ 的叉积，记为 $cur$。如果 $cur$ 的方向与之前的 $pre$ 方向不一致，说明多边形不是凸多边形 🔒。否则，我们更新 $pre=cur$，继续遍历下一个顶点。

遍历结束，如果没有发现不一致的情况，说明多边形是凸多边形 🔒。

时间复杂度 $O(n)$，其中 $n$ 是顶点的数量。空间复杂度 $O(1)$。

func isConvex(points [][]int) bool {
	n := len(points)
	pre, cur := 0, 0
	for i := range points {
		x1 := points[(i+1)%n][0] - points[i][0]
		y1 := points[(i+1)%n][1] - points[i][1]
		x2 := points[(i+2)%n][0] - points[i][0]
		y2 := points[(i+2)%n][1] - points[i][1]
		cur = x1*y2 - x2*y1
		if cur != 0 {
			if cur*pre < 0 {
				return false
			}
			pre = cur
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

470. 用 Rand7() 实现 Rand10()

中等1 种解法

标签：数学、拒绝采样、概率与统计、随机化

题目、示例与约束

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

 

示例 1:

输入: 1
输出: [2]

示例 2:

输入: 2
输出: [2,8]

示例 3:

输入: 3
输出: [3,8,10]

 

提示:

• 1 <= n <= 105

 

进阶:

• rand7()调用次数的 期望值 是多少 ?
• 你能否尽量少调用 rand7() ?

方法一：拒绝采样 · Go 实现

思考

用均匀的 $rand7$ 造均匀的 $rand10$。直接 $\mathit{\text{rand7}}mod10$ 会偏斜。两次调用可生成 $[1,49]$ 的均匀整数。

拒绝采样：保留 $[1,40]$，映射为 $xmod10+1$；落在 $41$– $49$ 则重来。 $40$ 能被 $10$ 整除，十个残差各出现四次，因而均匀。

期望调用次数为常数。拒绝区间保证每个结果概率相同。

我们可以使用拒绝采样的方法实现等概率生成任意区间的随机数。拒绝采样的思路是如果生成的随机数落在我们希望的区间内，那么就返回该随机数，否则会不断生成直到生成一个落在区间内的随机数为止。

对于本题，我们可以通过调用 $rand7()$ 两次来实现生成 $[1,10]$ 以内的随机数，具体如下：

我们生成一个大于等于 $1$ 且小于等于 $40$ 的整数 $x$，其中等概率生成的方式为 $x=(rand7()-1)\times 7+rand7()$，然后，我们返回 $xmod10+1$ 即可。

期望时间复杂度为 $O(1)$，但是最坏情况下会达到无穷大的时间复杂度。空间复杂度为 $O(1)$。

func rand10() int {
	for {
		i := rand7() - 1
		j := rand7()
		x := i*7 + j
		if x <= 40 {
			return x%10 + 1
		}
	}
}

力扣原题 · Doocs 题解来源

478. 在圆内随机生成点

中等1 种解法

标签：几何、数学、拒绝采样、随机化

题目、示例与约束

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。

实现 Solution 类:

• Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
• randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。

 

示例 1：

输入: 
["Solution","randPoint","randPoint","randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
输出: [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]
解释:
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint ();//返回[-0.02493，-0.38077]
solution.randPoint ();//返回[0.82314,0.38945]
solution.randPoint ();//返回[0.36572,0.17248]

 

提示：

• 0 < radius <= 108
• -107 <= x_center, y_center <= 107
• randPoint 最多被调用 3 * 104 次

方法一：Go 实现（halfrost） · Go 实现

halfrost · 源码 · MIT 许可

本次根据原始 Go 源码整理的中文说明，非 halfrost 书籍原文。

构造对象时记录半径和圆心。RandPoint 在圆的外接正方形内随机生成坐标，拒绝圆外点，接受后平移到给定圆心；实际运行的是拒绝采样分支。文件中的极坐标片段处于注释中，angle 辅助函数仍按原文保留。

import (
	"math"
	"math/rand"
	"time"
)

type Solution struct {
	r float64
	x float64
	y float64
}

func Constructor(radius float64, x_center float64, y_center float64) Solution {
	rand.Seed(time.Now().UnixNano())
	return Solution{radius, x_center, y_center}
}

func (this *Solution) RandPoint() []float64 {
	/*
	   a := angle()
	   r := this.r * math.Sqrt(rand.Float64())
	   x := r * math.Cos(a) + this.x
	   y := r * math.Sin(a) + this.y
	   return []float64{x, y}*/
	for {
		rx := 2*rand.Float64() - 1.0
		ry := 2*rand.Float64() - 1.0
		x := this.r * rx
		y := this.r * ry
		if x*x+y*y <= this.r*this.r {
			return []float64{x + this.x, y + this.y}
		}
	}
}

func angle() float64 {
	return rand.Float64() * 2 * math.Pi
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(radius, x_center, y_center);
 * param_1 := obj.RandPoint();
 */

力扣原题 · Doocs 题解来源

479. 最大回文数乘积

困难1 种解法

标签：数学、枚举

题目、示例与约束

给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。

 

示例 1：

输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987

示例 2：

输入：n = 1
输出：9

 

提示:

• 1 <= n <= 8

方法一 · Go 实现

思考

求两个 $n$ 位整数乘积中最大的回文，再模 $1337$。 $n\le 8$，枚举所有乘积再判回文过大。

从大到小枚举回文的前半 $a$，镜像得到回文 $x$，再检查是否存在 $n$ 位因子 $t$（从 ${10}^n-1$ 向下， $t^2\ge x$）。第一个成功的 $x$ 即为最大。

先构造回文再试因子，比枚举乘积更早遇到最大值。 $n=1$ 的哨兵返回 $9$。

func largestPalindrome(n int) int {
	mx := int(math.Pow10(n)) - 1
	for a := mx; a > mx/10; a-- {
		x := a
		for b := a; b != 0; b /= 10 {
			x = x*10 + b%10
		}
		for t := mx; t*t >= x; t-- {
			if x%t == 0 {
				return x % 1337
			}
		}
	}
	return 9
}

力扣原题 · Doocs 题解来源

492. 构造矩形

简单1 种解法

标签：数学

题目、示例与约束

作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 所以，现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：

1. 你设计的矩形页面必须等于给定的目标面积。
2. 宽度 W 不应大于长度 L ，换言之，要求 L >= W 。
3. 长度 L 和宽度 W 之间的差距应当尽可能小。

返回一个 数组 [L, W]，其中 L 和 W 是你按照顺序设计的网页的长度和宽度。
 

示例1：

输入: 4
输出: [2, 2]
解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。

示例 2:

输入: area = 37
输出: [37,1]

示例 3:

输入: area = 122122
输出: [427,286]

 

提示:

• 1 <= area <= 107

方法一 · Go 实现

思考

面积固定，要求 $L\ge W$ 且 $L-W$ 最小，即尽量接近正方形。从 $1$ 扫到 $\mathit{\text{area}}$ 找因子偏慢。

从 $W=\lfloor \sqrt{\mathit{\text{area}}}\rfloor$ 向下找能整除的 $W$，则 $L=\mathit{\text{area}}/W$ 自动不小于 $W$，差值最小。

从平方根向下保证第一组因子就是最接近的一对。

func constructRectangle(area int) []int {
	w := int(math.Sqrt(float64(area)))
	for area%w != 0 {
		w--
	}
	return []int{area / w, w}
}

力扣原题 · Doocs 题解来源

504. 七进制数

简单1 种解法

标签：数学、字符串

题目、示例与约束

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

 

示例 1:

输入: num = 100
输出: "202"

示例 2:

输入: num = -7
输出: "-10"

 

提示：

• -107 <= num <= 107

方法一：模拟 · Go 实现

思考

七进制转换就是反复除 $7$ 取余。负数可先转绝对值再补符号； $0$ 单独返回。余数序列是低位在前，拼接前需要反转。

除法次数与位数成正比，位数为 $O(\log |num|)$，远小于任何更重的字符串模拟。

我们不妨假设 num 大于等于 $0$，那么，如果 num 等于 $0$，只需要返回 $0$ 即可。否则，我们将 $num$ 模 $7$ 的结果保存起来，最后逆序拼接成字符串即可。

时间复杂度 $O(\log n)$，忽略答案的空间消耗，空间复杂度 $O(1)$。其中 $n$ 是 num 的绝对值大小。

func convertToBase7(num int) string {
	if num == 0 {
		return "0"
	}
	if num < 0 {
		return "-" + convertToBase7(-num)
	}
	ans := []byte{}
	for num != 0 {
		ans = append([]byte{'0' + byte(num%7)}, ans...)
		num /= 7
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

507. 完美数

简单1 种解法

标签：数学

题目、示例与约束

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。

 

示例 1：

输入：num = 28
输出：true
解释：28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2：

输入：num = 7
输出：false

 

提示：

• 1 <= num <= 108

方法一：枚举 · Go 实现

思考

完美数要求真因子之和等于自身。枚举 $1$ 到 $num-1$ 的因子在 $num\le {10}^8$ 时过慢。

因子成对出现：若 $i$ 整除 $num$，则 $num/i$ 也是因子，枚举上界可收到 $\sqrt{num}$。 $1$ 的真因子之和为 $0$，需单独排除。累加全部真因子后与 $num$ 比较即可。

我们首先判断 $\mathit{\text{num}}$ 是否为 1，如果为 1，则 $\mathit{\text{num}}$ 不是完美数，返回 $\text{false}$。

然后，我们从 2 开始枚举 $\mathit{\text{num}}$ 的所有正因子，如果 $\mathit{\text{num}}$ 能被 $\mathit{\text{num}}$ 的某个正因子 $i$ 整除，那么我们将 $i$ 加入到答案 $\mathit{\text{s}}$ 中。如果 $\mathit{\text{num}}$ 除以 $i$ 得到的商不等于 $i$，我们也将 $\mathit{\text{num}}$ 除以 $i$ 得到的商加入到答案 $\mathit{\text{s}}$ 中。

最后，我们判断 $\mathit{\text{s}}$ 是否等于 $\mathit{\text{num}}$ 即可。

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

func checkPerfectNumber(num int) bool {
	if num == 1 {
		return false
	}
	s := 1
	for i := 2; i <= num/i; i++ {
		if num%i == 0 {
			s += i
			if j := num / i; i != j {
				s += j
			}
		}
	}
	return s == num
}

力扣原题 · Doocs 题解来源

519. 随机翻转矩阵

中等1 种解法

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

题目、示例与约束

给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现 Solution 类：

• Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
• int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
• void reset() 将矩阵中所有的值重置为 0

 

示例：

输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip();  // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

 

提示：

• 1 <= m, n <= 104
• 每次调用flip 时，矩阵中至少存在一个值为 0 的格子。
• 最多调用 1000 次 flip 和 reset 方法。

方法一：Go 实现（halfrost） · Go 实现

halfrost · 源码 · MIT 许可

本次根据原始 Go 源码整理的中文说明，非 halfrost 书籍原文。

将矩阵位置映射为一维下标。Flip 从尚未使用的下标范围随机取一个位置，通过映射取得实际格子，然后把范围末尾的映射移到该位置并缩小范围；返回值再转换成行列坐标。Reset 恢复总数并清空映射，避免显式存储整个矩阵。

import (
	"math/rand"
)

type Solution struct {
	r     int
	c     int
	total int
	mp    map[int]int
}

func Constructor(m int, n int) Solution {
	return Solution{
		r:     m,
		c:     n,
		total: m * n,
		mp:    map[int]int{},
	}
}

func (this *Solution) Flip() []int {
	k := rand.Intn(this.total)
	val := k
	if v, ok := this.mp[k]; ok {
		val = v
	}
	if _, ok := this.mp[this.total-1]; ok {
		this.mp[k] = this.mp[this.total-1]
	} else {
		this.mp[k] = this.total - 1
	}
	delete(this.mp, this.total-1)
	this.total--
	newR, newC := val/this.c, val%this.c
	return []int{newR, newC}
}

func (this *Solution) Reset() {
	this.total = this.r * this.c
	this.mp = map[int]int{}
}

力扣原题 · Doocs 题解来源

537. 复数乘法

中等1 种解法

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

题目、示例与约束

复数 可以用字符串表示，遵循 "实部+虚部i" 的形式，并满足下述条件：

• 实部 是一个整数，取值范围是 [-100, 100]
• 虚部 也是一个整数，取值范围是 [-100, 100]
• i2 == -1

给你两个字符串表示的复数 num1 和 num2 ，请你遵循复数表示形式，返回表示它们乘积的字符串。

 

示例 1：

输入：num1 = "1+1i", num2 = "1+1i"
输出："0+2i"
解释：(1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。

示例 2：

输入：num1 = "1+-1i", num2 = "1+-1i"
输出："0+-2i"
解释：(1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。 

 

提示：

• num1 和 num2 都是有效的复数表示。

方法一：模拟 · Go 实现

思考

复数乘法有闭式 $(a+bi)(c+di)=(ac-bd)+(ad+bc)i$。输入已是 a+bi 形式，拆出四个整数即可套公式。

去掉末尾 i 再按 + 分割，得到实部虚部；按公式计算后格式化回去。无需模拟多项式展开。

我们可以将复数字符串转换成对应的实部 $a$ 和虚部 $b$，然后根据复数乘法的公式 $(a_1+b_{1}i)\times (a_2+b_{2}i)=(a_1{a}_2-b_1{b}_2)+(a_1{b}_2+a_2{b}_1)i$ 计算出结果。

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

func complexNumberMultiply(num1 string, num2 string) string {
	x, _ := strconv.ParseComplex(num1, 64)
	y, _ := strconv.ParseComplex(num2, 64)
	return fmt.Sprintf("%d+%di", int(real(x*y)), int(imag(x*y)))
}

力扣原题 · Doocs 题解来源

539. 最小时间差

中等1 种解法

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

题目、示例与约束

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

 

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

 

提示：

• 2 <= timePoints.length <= 2 * 104
• timePoints[i] 格式为 "HH:MM"

方法一：排序 · Go 实现

思考

最小时间差出现在排序后的相邻时刻，还要比较「最后一个与第一个跨午夜」的差。时刻只有 $1440$ 种，点数超过 $1440$ 必有重复，差为 $0$。

化成分钟后排序，再把首元素加 $1440$ 接到末尾，相邻差的最小值即为答案。排序决定总复杂度。

我们注意到，时间点最多只有 $24\times 60=1440$ 个，因此，当 $timePoints$ 长度超过 $1440$，说明有重复的时间点，提前返回 $0$。

接下来，我们首先遍历时间列表，将其转换为“分钟制”列表 $nums$，比如，对于时间点 13:14，将其转换为 $13\times 60+14$。

接着将“分钟制”列表按升序排列，然后将此列表的最小时间 $nums[0]$ 加上 $1440$ 追加至列表尾部，用于处理最大值、最小值的差值这种特殊情况。

最后遍历“分钟制”列表，找出相邻两个时间的最小值即可。

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

func findMinDifference(timePoints []string) int {
	if len(timePoints) > 1440 {
		return 0
	}

	n := len(timePoints)
	nums := make([]int, n+1)
	for i, time := range timePoints {
		parts := strings.Split(time, ":")
		hours, _ := strconv.Atoi(parts[0])
		minutes, _ := strconv.Atoi(parts[1])
		nums[i] = hours*60 + minutes
	}

	sort.Ints(nums[:n])
	nums[n] = nums[0] + 1440

	ans := 1 << 30
	for i := 1; i <= n; i++ {
		ans = min(ans, nums[i]-nums[i-1])
	}

	return ans
}

力扣原题 · Doocs 题解来源

564. 寻找最近的回文数

困难1 种解法

标签：数学、字符串

题目、示例与约束

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

 

示例 1:

输入: n = "123"
输出: "121"

示例 2:

输入: n = "1"
输出: "0"
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。

 

提示:

• 1 <= n.length <= 18
• n 只由数字组成
• n 不含前导 0
• n 代表在 [1, 1018 - 1] 范围内的整数

方法一 · Go 实现

思考

要找与 $n$ 数值最接近且不等于 $n$ 的回文数。在附近枚举整数再判断回文，范围漫无边界。

最近回文只可能来自「镜像前半」及其 $\pm 1$，再加上位数变化的 $99\dots 9$ 与 $100\dots 001$。对前半加减一后按长度镜像，丢掉 $n$ 本身，再按距离、再按数值选取。候选只有常数个。

func nearestPalindromic(n string) string {
	x := new(big.Int)
	x.SetString(n, 10)
	l := len(n)
	ten := big.NewInt(10)
	base := new(big.Int).Exp(ten, big.NewInt(int64(l-1)), nil)
	res := []*big.Int{
		new(big.Int).Sub(new(big.Int).Set(base), big.NewInt(1)),
		new(big.Int).Add(new(big.Int).Mul(new(big.Int).Set(base), ten), big.NewInt(1)),
	}
	left := new(big.Int)
	left.SetString(n[:(l+1)/2], 10)
	for d := int64(-1); d <= 1; d++ {
		i := new(big.Int).Add(left, big.NewInt(d))
		j := new(big.Int).Set(i)
		if l&1 == 1 {
			j.Quo(j, ten)
		}
		for j.Sign() > 0 {
			i.Mul(i, ten)
			i.Add(i, new(big.Int).Mod(j, ten))
			j.Quo(j, ten)
		}
		res = append(res, i)
	}
	var ans *big.Int
	for _, t := range res {
		if t.Cmp(x) == 0 {
			continue
		}
		dist := new(big.Int).Abs(new(big.Int).Sub(t, x))
		if ans == nil {
			ans = new(big.Int).Set(t)
			continue
		}
		best := new(big.Int).Abs(new(big.Int).Sub(ans, x))
		if dist.Cmp(best) < 0 || (dist.Cmp(best) == 0 && t.Cmp(ans) < 0) {
			ans = new(big.Int).Set(t)
		}
	}
	return ans.String()
}

力扣原题 · Doocs 题解来源

573. 松鼠模拟 🔒

中等1 种解法

标签：数组、数学

题目、示例与约束

给你两个整数 height 和 width ，代表一个大小为 height x width 的花园。你还得到了以下信息：

• 一个数组 tree ，其中 tree = [treer, treec] 是花园中树的位置，
• 一个数组 squirrel ，其中 squirrel = [squirrelr, squirrelc] 是花园中松鼠的位置，
• 一个数组 nuts ，其中 nuts[i] = [nutir, nutic] 是花园中第 ith 个坚果的位置。

松鼠一次最多只能携带一个坚果，并且能够向上、下、左、右四个方向移动到相邻的单元格。

返回松鼠收集所有坚果并逐一放在树下的 最小距离 。

距离 是指移动的次数。

 

示例 1：

输入：height = 5, width = 7, tree = [2,2], squirrel = [4,4], nuts = [[3,0], [2,5]]
输出：12
解释：为实现最小的距离，松鼠应该先摘 [2, 5] 位置的坚果。

示例 2：

输入：height = 1, width = 3, tree = [0,1], squirrel = [0,0], nuts = [[0,2]]
输出：3

 

提示：

• 1 <= height, width <= 100
• tree.length == 2
• squirrel.length == 2
• 1 <= nuts.length <= 5000
• nuts[i].length == 2
• 0 <= treer, squirrelr, nutir <= height
• 0 <= treec, squirrelc, nutic <= width

方法一：数学 · Go 实现

思考

松鼠先衔一颗坚果上树，之后每颗坚果都是树往返。若枚举第一颗坚果再模拟全部路径，只是在重复加同一组往返。

全部坚果到树的往返之和为 $s$。若第一颗是 $(r,c)$，则少走一次该坚果到树的距离 $a$，多走松鼠到该坚果的距离 $b$，总长 $s-a+b$。枚举第一颗取最小即可。

我们观察松鼠的移动路径，可以发现，松鼠会首先移动到某个坚果的位置，然后移动到树的位置。接下来，松鼠的移动路径之和等于“其余坚果到树的位置之和”再乘以 $2$。

因此，我们只需要选出一个坚果，作为松鼠的第一个目标，使得其到树的位置之和最小，即可得到最小路径。

时间复杂度 $O(n)$，其中 $n$ 为坚果的数量。空间复杂度 $O(1)$。

func minDistance(height int, width int, tree []int, squirrel []int, nuts [][]int) int {
	tr, tc := tree[0], tree[1]
	sr, sc := squirrel[0], squirrel[1]
	s := 0
	for _, e := range nuts {
		s += abs(e[0]-tr) + abs(e[1]-tc)
	}
	s <<= 1
	ans := math.MaxInt32
	for _, e := range nuts {
		a := abs(e[0]-tr) + abs(e[1]-tc)
		b := abs(e[0]-sr) + abs(e[1]-sc)
		ans = min(ans, s-a+b)
	}
	return ans
}

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

力扣原题 · Doocs 题解来源

587. 安装栅栏

困难1 种解法

标签：几何、数组、数学、凸包、多边形

题目、示例与约束

给定一个数组 trees，其中 trees[i] = [xi, yi] 表示树在花园中的位置。

你被要求用最短长度的绳子把整个花园围起来，因为绳子很贵。只有把 所有的树都围起来，花园才围得很好。

返回恰好位于围栏周边的树木的坐标。

示例 1:

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

示例 2:

输入: points = [[1,2],[2,2],[4,2]]
输出: [[4,2],[2,2],[1,2]]

 

注意:

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

• 所有给定的点都是 唯一 的。

方法一：Andrew 算法 · Go 实现

思考

围栏是点集的凸包。 $n$ 不大时 Jarvis 可以，Andrew 扫描在排序后线性围一圈，更稳。边上的点也要留下，因此叉积用严格 $<0$ 才弹出，共线点保留。

按坐标排序后先走下凸壳，再用访问标记走上凸壳，避免重复。最后弹出起点。点数少于 $4$ 时全部返回。

原理：

利用夹角，让整个图形保持左转。先将最左边的前两个点加入栈中，每次加入新点时判断是否左拐（叉积大于 0），如果是就将新点直接加入；如果不是，就弹出栈顶，直到左拐，将新点加入栈中。

流程：

1. 将所有点 (x, y) 进行排序，以 x 为第一关键字，y 为第二关键字升序排序；
2. 先从左至右维护凸包的下半部分，然后再从右至左维护上半部分；
3. 将第一个点放入栈中，这个点一定时凸包的最左边的点了，是不会清理掉的，然后再将第二个点放入栈中。当栈中元素大于等于 2 的时候，就要判断栈顶元素是否还要保留：
   • 如果新点在栈顶元素和次栈顶元素所组成的直线的逆时针方向上，那么直接将新点加入栈中；
   • 否则，将栈顶元素不断弹出，直至新点的位置出现在栈顶元素与次栈顶元素所在直线的逆时针方向。

这个过程，是从左往右走的，并且得到的凸包是凸壳的下半部分。求上半部分的时候，从右往左遍历。

时间复杂度 O(nlogn)。

func outerTrees(trees [][]int) [][]int {
	n := len(trees)
	if n < 4 {
		return trees
	}
	sort.Slice(trees, func(i, j int) bool {
		if trees[i][0] == trees[j][0] {
			return trees[i][1] < trees[j][1]
		}
		return trees[i][0] < trees[j][0]
	})
	cross := func(i, j, k int) int {
		a, b, c := trees[i], trees[j], trees[k]
		return (b[0]-a[0])*(c[1]-b[1]) - (b[1]-a[1])*(c[0]-b[0])
	}
	vis := make([]bool, n)
	stk := []int{0}
	for i := 1; i < n; i++ {
		for len(stk) > 1 && cross(stk[len(stk)-1], stk[len(stk)-2], i) < 0 {
			vis[stk[len(stk)-1]] = false
			stk = stk[:len(stk)-1]
		}
		vis[i] = true
		stk = append(stk, i)
	}
	m := len(stk)
	for i := n - 1; i >= 0; i-- {
		if vis[i] {
			continue
		}
		for len(stk) > m && cross(stk[len(stk)-1], stk[len(stk)-2], i) < 0 {
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, i)
	}
	var ans [][]int
	for i := 0; i < len(stk)-1; i++ {
		ans = append(ans, trees[stk[i]])
	}
	return ans
}

力扣原题 · Doocs 题解来源

592. 分数加减运算

中等1 种解法

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

题目、示例与约束

给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。 

这个结果应该是不可约分的分数，即 最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

 

示例 1:

输入: expression = "-1/2+1/2"
输出: "0/1"

 示例 2:

输入: expression = "-1/2+1/2+1/3"
输出: "1/3"

示例 3:

输入: expression = "1/3-1/2"
输出: "-1/6"

 

提示:

• 输入和输出字符串只包含 '0' 到 '9' 的数字，以及 '/', '+' 和 '-'。 
• 输入和输出分数格式均为 ±分子/分母。如果输入的第一个分数或者输出的分数是正数，则 '+' 会被省略掉。
• 输入只包含合法的 最简分数，每个分数的分子与分母的范围是 [1,10]。 如果分母是 1，意味着这个分数实际上是一个整数。
• 输入的分数个数范围是 [1,10]。
• 最终结果 的分子与分母保证是 32 位整数范围内的有效整数。

方法一：数学 · Go 实现

思考

若干分数相加减，分母在 $2$ 到 $10$。通分后再约分即可，不必用分数类。

取 $2$ 到 $10$ 的最小公倍数 $y$ 作公共分母，扫描带符号的 $a/b$ 累加到分子 $x$。最后与 $y$ 求 gcd 约分。表达式若不以符号开头则先补 +，便于统一解析。

func fractionAddition(expression string) string {
	x, y := 0, 6*7*8*9*10
	if unicode.IsDigit(rune(expression[0])) {
		expression = "+" + expression
	}
	i, n := 0, len(expression)
	for i < n {
		sign := 1
		if expression[i] == '-' {
			sign = -1
		}
		i++
		j := i
		for j < n && expression[j] != '+' && expression[j] != '-' {
			j++
		}
		s := expression[i:j]
		t := strings.Split(s, "/")
		a, _ := strconv.Atoi(t[0])
		b, _ := strconv.Atoi(t[1])
		x += sign * a * y / b
		i = j
	}
	z := gcd(abs(x), y)
	x /= z
	y /= z
	return fmt.Sprintf("%d/%d", x, y)
}

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

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

力扣原题 · Doocs 题解来源

593. 有效的正方形

中等1 种解法

标签：几何、数学

题目、示例与约束

给定2D空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true 。

点的坐标 pi 表示为 [xi, yi] 。 输入没有任何顺序 。

一个 有效的正方形 有四条等边和四个等角(90度角)。

 

示例 1:

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: true

示例 2:

输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出：false

示例 3:

输入：p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
输出：true

 

提示:

• p1.length == p2.length == p3.length == p4.length == 2
• -104 <= xi, yi <= 104

方法一：数学 · Go 实现

思考

四点能否构成正方形：四边相等且邻边垂直，或等价地任意三点都是等腰直角三角形。枚举排列再判断 quadrilateral 较繁。

对每三个点检查三条边是否满足两边相等且勾股（并排除零边长）。四个三点组都成立则四点构成正方形。用平方距离避免开方。

若任选三个点，都能构成等腰直角三角形，说明是有效的正方形。

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

func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
	check := func(a, b, c []int) bool {
		x1, y1 := a[0], a[1]
		x2, y2 := b[0], b[1]
		x3, y3 := c[0], c[1]
		d1 := (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
		d2 := (x1-x3)*(x1-x3) + (y1-y3)*(y1-y3)
		d3 := (x2-x3)*(x2-x3) + (y2-y3)*(y2-y3)
		if d1 == d2 && d1+d2 == d3 && d1 > 0 {
			return true
		}
		if d1 == d3 && d1+d3 == d2 && d1 > 0 {
			return true
		}
		if d2 == d3 && d2+d3 == d1 && d2 > 0 {
			return true
		}
		return false
	}
	return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4)
}

力扣原题 · Doocs 题解来源

598. 区间加法 II

简单1 种解法

标签：数组、数学

题目、示例与约束

给你一个 m x n 的矩阵 M 和一个操作数组 op 。矩阵初始化时所有的单元格都为 0 。ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。

在 执行完所有操作后 ，计算并返回 矩阵中最大整数的个数 。

 

示例 1:

输入: m = 3, n = 3，ops = [[2,2],[3,3]]
输出: 4
解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

示例 2:

输入: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
输出: 4

示例 3:

输入: m = 3, n = 3, ops = []
输出: 9

 

提示:

• 1 <= m, n <= 4 * 104
• 0 <= ops.length <= 104
• ops[i].length == 2
• 1 <= ai <= m
• 1 <= bi <= n

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

思考

每次给左上角子矩阵加一，最后的最大值等于操作次数，其出现次数等于所有操作子矩阵的交集面积。子矩阵都从 $(0,0)$ 出发，交集就是最小的 $a$ 与最小的 $b$。

扫一遍操作取 $min{a}_i$ 与 $min{b}_i$，乘积即答案。无需真正建 $m\times n$ 的差分数组。

我们注意到，所有操作子矩阵的交集就是最终的最大整数所在的子矩阵，并且每个操作子矩阵都是从左上角 $(0,0)$ 开始的，因此，我们遍历所有操作子矩阵，求出行数和列数的最小值，最后返回这两个值的乘积即可。

注意，如果操作数组为空，那么矩阵中的最大整数个数就是 $m\times n$。

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

func maxCount(m int, n int, ops [][]int) int {
	for _, op := range ops {
		m = min(m, op[0])
		n = min(n, op[1])
	}
	return m * n
}

力扣原题 · Doocs 题解来源

628. 三个数的最大乘积

简单2 种解法

标签：数组、数学、排序

题目、示例与约束

给你一个整型数组 nums。

在数组中找出由三个数组成的 最大 乘积，并返回这个 最大 乘积。

 

示例 1：

输入：nums = [1,2,-3]
输出：-6
解释：只有三个数字 1、2 和 -3，因此最大乘积是 1 * 2 * -3 = -6。

示例 2：

输入：nums = [1,2,3,4]
输出：24
解释：最大的乘积来自三个最大的数字：2 * 3 * 4 = 24。

示例 3：

输入：nums = [-1,-2,-3]
输出：-6
解释：只有三个数字 -1、-2 和 -3，因此最大乘积是 (-1) * (-2) * (-3) = -6。

 

提示：

• 3 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

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

思考

三个数乘积的最大者，可能来自三个最大正数，也可能来自两个绝对值很大的负数再乘最大正数。 $n\le {10}^4$，排序后分类即可。

排序后比较 $nums[-1]\times nums[-2]\times nums[-3]$ 与 $nums[-1]\times nums[0]\times nums[1]$，覆盖全正、全负与正负并存。

我们先对数组 $\mathit{\text{nums}}$ 进行排序，接下来分两种情况讨论：

• 如果 $\mathit{\text{nums}}$ 中全是非负数或者全是非正数，那么答案即为最后三个数的乘积，即 $\mathit{\text{nums}}[n-1]\times \mathit{\text{nums}}[n-2]\times \mathit{\text{nums}}[n-3]$；
• 如果 $\mathit{\text{nums}}$ 中既有正数也有负数，那么答案可能是两个最小负数和一个最大整数的乘积，即 $\mathit{\text{nums}}[n-1]\times \mathit{\text{nums}}[0]\times \mathit{\text{nums}}[1]$；也可能是最后三个数的乘积，即 $\mathit{\text{nums}}[n-1]\times \mathit{\text{nums}}[n-2]\times \mathit{\text{nums}}[n-3]$。

最后返回两种情况的最大值即可。

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

func maximumProduct(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	a := nums[n-1] * nums[n-2] * nums[n-3]
	b := nums[n-1] * nums[0] * nums[1]
	if a > b {
		return a
	}
	return b
}

方法二：一次遍历 · Go 实现

思考

方法一付出排序的 $O(n\log n)$。乘积只依赖最小两个与最大三个数，一次遍历（或 nlargest）维护这五个极值即可降到线性。

我们可以不用对数组进行排序，而是维护五个变量，其中 $\mathit{\text{mi1}}$ 和 $\mathit{\text{mi2}}$ 表示数组中最小的两个数，而 $\mathit{\text{mx1}}$, $\mathit{\text{mx2}}$ 和 $\mathit{\text{mx3}}$ 表示数组中最大的三个数。

最后返回 $max(\mathit{\text{mi1}}\times \mathit{\text{mi2}}\times \mathit{\text{mx1}},\mathit{\text{mx1}}\times \mathit{\text{mx2}}\times \mathit{\text{mx3}})$ 即可。

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

func maximumProduct(nums []int) int {
	const inf = 1 << 30
	mi1, mi2 := inf, inf
	mx1, mx2, mx3 := -inf, -inf, -inf
	for _, x := range nums {
		if x < mi1 {
			mi1, mi2 = x, mi1
		} else if x < mi2 {
			mi2 = x
		}
		if x > mx1 {
			mx1, mx2, mx3 = x, mx1, mx2
		} else if x > mx2 {
			mx2, mx3 = x, mx2
		} else if x > mx3 {
			mx3 = x
		}
	}
	return max(mi1*mi2*mx1, mx1*mx2*mx3)
}

力扣原题 · Doocs 题解来源

640. 求解方程

中等1 种解法

标签：数学、字符串、线性代数、模拟

题目、示例与约束

求解一个给定的方程，将x以字符串 "x=#value" 的形式返回。该方程仅包含 '+' ， '-' 操作，变量 x 和其对应系数。

如果方程没有解或存在的解不为整数，请返回 "No solution" 。如果方程有无限解，则返回 “Infinite solutions” 。

题目保证，如果方程中只有一个解，则 'x' 的值是一个整数。

 

示例 1：

输入: equation = "x+5-3+x=6+x-2"
输出: "x=2"

示例 2:

输入: equation = "x=x"
输出: "Infinite solutions"

示例 3:

输入: equation = "2x=x"
输出: "x=0"

 

提示:

• 3 <= equation.length <= 1000
• equation 只有一个 '='. 
• 方程由绝对值在 [0, 100]  范围内且无任何前导零的整数和变量 'x' 组成。​​​

方法一：数学 · Go 实现

思考

一元一次方程要化成 $ax+b=0$ 再讨论解的个数。字符串里系数可省、符号相连，按字符手写状态机容易漏。

以 = 切开左右，各自扫描带符号项：以 x 结尾计入系数，否则计入常数。比较两侧系数与常数即可判定无穷解、无解或唯一整数解。

将方程 $equation$ 按照等号 “=” 切分为左右两个式子，分别算出左右两个式子中 "x" 的系数 $x_i$，以及常数的值 $y_i$。

那么方程转换为等式 $x_1\times x+y_1=x_2\times x+y_2$。

• 当 $x_1=x_2$：若 $y_1\ne y_2$，方程无解；若 $y_1=y_2$，方程有无限解。
• 当 $x_1\ne x_2$：方程有唯一解 $x=\frac{y_2-y_1}{x_1-x_2}$。

相似题目：

• 592. 分数加减运算

func solveEquation(equation string) string {
	f := func(s string) []int {
		x, y := 0, 0
		if s[0] != '-' {
			s = "+" + s
		}
		i, n := 0, len(s)
		for i < n {
			sign := 1
			if s[i] == '-' {
				sign = -1
			}
			i++
			j := i
			for j < n && s[j] != '+' && s[j] != '-' {
				j++
			}
			v := s[i:j]
			if s[j-1] == 'x' {
				a := 1
				if len(v) > 1 {
					a, _ = strconv.Atoi(v[:len(v)-1])
				}
				x += sign * a
			} else {
				a, _ := strconv.Atoi(v)
				y += sign * a
			}
			i = j
		}
		return []int{x, y}
	}

	es := strings.Split(equation, "=")
	a, b := f(es[0]), f(es[1])
	x1, y1 := a[0], a[1]
	x2, y2 := b[0], b[1]
	if x1 == x2 {
		if y1 == y2 {
			return "Infinite solutions"
		} else {
			return "No solution"
		}
	}
	return fmt.Sprintf("x=%d", (y2-y1)/(x1-x2))
}

力扣原题 · Doocs 题解来源

660. 移除 9 🔒

困难1 种解法

标签：数学

题目、示例与约束

从 1 开始，移除包含数字 9 的所有整数，例如 9，19，29，……

这样就获得了一个新的整数数列：1，2，3，4，5，6，7，8，10，11，……

给你一个整数 n，请你返回新数列中第 n 个数字是多少（下标从 1 开始）。

 

示例 1：

输入：n = 9
输出：10

示例 2：

输入：n = 10
输出：11

 

提示：

• 1 <= n <= 8 * 108

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

Doocs 参考题解 · CC BY-SA 4.0

本站根据题意与 Doocs 参考思路整理为 Go，非上游原文。按 CC BY-SA 4.0 共享。

根据题意补写：把 n 转成九进制，再把九进制的各位当作十进制数字。这样每一位只会出现 0 到 8，且顺序与所有不含 9 的正整数一致。时间 O(log₉ n)，额外空间 O(1)；Go 的整数范围应能够容纳结果。

func newInteger(n int) int {
	answer, place := 0, 1
	for n > 0 {
		answer += (n % 9) * place
		place *= 10
		n /= 9
	}
	return answer
}

力扣原题 · Doocs 题解来源

667. 优美的排列 II

中等1 种解法

标签：数组、数学

题目、示例与约束

给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：

• 假设该列表是 answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。

返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。

 

示例 1：

输入：n = 3, k = 1
输出：[1, 2, 3]
解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1

示例 2：

输入：n = 3, k = 2
输出：[1, 3, 2]
解释：[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2

 

提示：

• 1 <= k < n <= 104

 

方法一：构造 · Go 实现

思考

$1..n$ 的排列要使相邻差恰好出现 $k$ 种。随机搜索不可靠。

前 $k$ 项按 $1,n,2,n-1,\dots$ 交错，先产生 $k-1$ 个不同差；余下按 $k$ 的奇偶沿当前左端或右端单调填完，不再引入新差。

先按照 1, n, 2, n-1, 3,... 构造答案数据 ans 的前 $k$ 个数，共产生 $k-1$ 个不同的整数。然后根据 $k$ 的奇偶性确定从哪个数开始构造下一个数。

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

func constructArray(n int, k int) []int {
	l, r := 1, n
	ans := make([]int, n)
	for i := 0; i < k; i++ {
		if i%2 == 0 {
			ans[i] = l
			l++
		} else {
			ans[i] = r
			r--
		}
	}
	for i := k; i < n; i++ {
		if k%2 == 0 {
			ans[i] = r
			r--
		} else {
			ans[i] = l
			l++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

728. 自除数

简单1 种解法

标签：数学

题目、示例与约束

自除数 是指可以被它包含的每一位数整除的数。

• 例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。

自除数 不允许包含 0 。

给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right]（包括两个端点）内所有的 自除数 。

 

示例 1：

输入：left = 1, right = 22
输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

示例 2:

输入：left = 47, right = 85
输出：[48,55,66,77]

 

提示：

• 1 <= left <= right <= 104

方法一：模拟 · Go 实现

思考

区间上界为 ${10}^4$，判断一个数是否能被自己的每一位整除只需拆位。线性枚举区间内每个数完全可行。

含 $0$ 的数无法整除对应位，应直接排除。其余位则检查 $x$ 能否被该位整除。

对每个 $x$ 用 $y$ 逐位取末位，遇 $0$ 或不能整除则否，全部通过则收入答案。

我们定义一个函数 $\mathit{\text{check}}(x)$，用来判断 $x$ 是否是自除数。函数的实现思路如下：

我们用 $y$ 来记录 $x$ 的值，然后不断地对 $y$ 除以 $10$，直到 $y$ 为 $0$。在这个过程中，我们判断 $y$ 的末位是否为 $0$，或者 $x$ 是否不能被 $y$ 的末位整除，如果满足这两个条件中的任意一个，那么 $x$ 就不是自除数，返回 $\text{false}$。否则遍历完所有的位数后，返回 $\text{true}$。

最后，我们遍历区间 $[\mathit{\text{left}},\mathit{\text{right}}]$ 中的所有数，对每个数调用 $\mathit{\text{check}}(x)$，如果返回 $\text{true}$，那么我们就将这个数加入答案数组中。

时间复杂度 $O(n\times {\log }_{10}M)$，其中 $n$ 是区间 $[\mathit{\text{left}},\mathit{\text{right}}]$ 中的元素个数，而 $M=\mathit{\text{right}}$，表示区间中的最大值。

func selfDividingNumbers(left int, right int) (ans []int) {
	check := func(x int) bool {
		for y := x; y > 0; y /= 10 {
			if y%10 == 0 || x%(y%10) != 0 {
				return false
			}
		}
		return true
	}
	for x := left; x <= right; x++ {
		if check(x) {
			ans = append(ans, x)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

775. 全局倒置与局部倒置

中等2 种解法

标签：数组、数学

题目、示例与约束

给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。

全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：

• 0 <= i < j < n
• nums[i] > nums[j]

局部倒置 的数目等于满足下述条件的下标 i 的数目：

• 0 <= i < n - 1
• nums[i] > nums[i + 1]

当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [1,0,2]
输出：true
解释：有 1 个全局倒置，和 1 个局部倒置。

示例 2：

输入：nums = [1,2,0]
输出：false
解释：有 2 个全局倒置，和 1 个局部倒置。

 

提示：

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] < n
• nums 中的所有整数 互不相同
• nums 是范围 [0, n - 1] 内所有数字组成的一个排列

方法一：维护前缀最大值 · Go 实现

思考

判断全局逆序是否等于局部（相邻）逆序。 $n\le {10}^5$，数全部逆序对可以，但更弱的条件是：不存在跨度大于 $1$ 的逆序。

即不存在 $i\le j-2$ 且 $nums[i]>nums[j]$。维护 $nums[0..i-2]$ 的最大值，一旦大于 $nums[i]$ 则失败。

根据题意，我们可以发现，一个数组中的局部倒置一定是全局倒置，但是全局倒置不一定是局部倒置。也就是说，全局倒置的数量一定大于等于局部倒置的数量。

因此，我们枚举每个数 $nums[i]$，其中 $2\le i\le n-1$，维护前缀数组 $nums[0,..i-2]$ 中的最大值，记为 $mx$。如果存在 $mx$ 大于 $nums[i]$，则说明全局倒置的数量大于局部倒置的数量，返回 false 即可。

遍历结束后，返回 true。

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

func isIdealPermutation(nums []int) bool {
	mx := 0
	for i := 2; i < len(nums); i++ {
		mx = max(mx, nums[i-2])
		if mx > nums[i] {
			return false
		}
	}
	return true
}

方法二：树状数组 · Go 实现

思考

方法一用充要条件直接判断。若要分别计数，局部逆序扫相邻即可，全局逆序用树状数组数左侧更大的个数。

边走边比较两者之差，一旦全局更多即可返回。复杂度多一个对数。

这道题目实际上是一个“逆序对”问题。

局部倒置的数量等于相邻元素之间逆序对的个数，可以在遍历数组 nums 的过程中直接求出；而全局倒置的数量等于逆序对的个数，求解逆序对个数的一个常用做法是使用树状数组。

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作：

1. 单点更新：即函数 update(x, delta)，把序列 $x$ 位置的数加上一个值 $delta$。时间复杂度 $O(\log n)$。
2. 前缀和查询：即函数 query(x)，查询序列 [1,...x] 区间的区间和，即位置 $x$ 的前缀和。时间复杂度 $O(\log n)$。

对于本题，我们定义一个变量 $cnt$ 记录局部倒置的数量与全局倒置的数量之差。如果遍历过程中， $cnt$ 的值小于 $0$，则说明全局倒置的数量大于局部倒置的数量，返回 false 即可。

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

func isIdealPermutation(nums []int) bool {
	n := len(nums)
	tree := newBinaryIndexedTree(n)
	cnt := 0
	for i, v := range nums {
		if i < n-1 && v > nums[i+1] {
			cnt++
		}
		cnt -= (i - tree.query(v))
		if cnt < 0 {
			break
		}
		tree.update(v+1, 1)
	}
	return cnt == 0
}

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) BinaryIndexedTree {
	c := make([]int, n+1)
	return BinaryIndexedTree{n, c}
}

func (this BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += x & -x
	}
}

func (this BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= x & -x
	}
	return s
}

力扣原题 · Doocs 题解来源

780. 到达终点

困难1 种解法

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

题目、示例与约束

给定四个整数 sx , sy ，tx 和 ty，如果通过一系列的转换可以从起点 (sx, sy) 到达终点 (tx, ty)，则返回 true，否则返回 false。

从点 (x, y) 可以转换到 (x, x+y)  或者 (x+y, y)。

 

示例 1:

输入: sx = 1, sy = 1, tx = 3, ty = 5
输出: true
解释:
可以通过以下一系列转换从起点转换到终点：
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

示例 2:

输入: sx = 1, sy = 1, tx = 2, ty = 2 
输出: false

示例 3:

输入: sx = 1, sy = 1, tx = 1, ty = 1 
输出: true

 

提示:

• 1 <= sx, sy, tx, ty <= 109

方法一：逆向计算 · Go 实现

思考

从 $(sx,sy)$ 只能做 $(x,x+y)$ 或 $(x+y,y)$，终点坐标可以很大，正向搜索分支无法收敛。逆运算是从较大维减去若干个较小维，即取模。

当两维都还大于起点且不相等时，把大的对小的取模，相当于一次走完能减的步。落到某一维已对齐后，另一维若能被该维整除地减到起点，则可达。

相等且等于起点则成功；两维都对不上则失败。取模避免逐次减法。

从 (tx, ty) 开始逆向计算，判断是否可以到达状态 (sx, sy)。由于逆向计算是将 tx, ty 中的较大值减少，因此当 tx > ty 时可以直接将 tx 的值更新为 tx % ty，当 tx < ty 时可以将 ty 的值更新为 ty % tx。逆向计算需要满足 tx > sx && ty > sy && tx != ty。

当条件不成立时，根据此时 tx 和 ty 判断是否可以从起点转换到终点。

• 如果 tx == sx && ty == sy，说明此时已经到达起点状态，返回 true；
• 如果 tx == sx，若 ty > sy && (ty - sy) % tx == 0，返回 true，否则返回 false；
• 如果 ty == sy，若 tx > sx && (tx - sx) % ty == 0，返回 true，否则返回 false；
• 如果 tx ≠ sx && ty ≠ sy，则不可以从起点转换到终点。

func reachingPoints(sx int, sy int, tx int, ty int) bool {
	for tx > sx && ty > sy && tx != ty {
		if tx > ty {
			tx %= ty
		} else {
			ty %= tx
		}
	}
	if tx == sx && ty == sy {
		return true
	}
	if tx == sx {
		return ty > sy && (ty-sy)%tx == 0
	}
	if ty == sy {
		return tx > sx && (tx-sx)%ty == 0
	}
	return false
}

力扣原题 · Doocs 题解来源

789. 逃脱阻碍者

中等1 种解法

标签：数组、数学

题目、示例与约束

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [xtarget, ytarget] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [xi, yi] 出发。所有输入均为 整数坐标 。

每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位 的新位置。当然，也可以选择 不动 。所有动作 同时 发生。

如果你可以在任何阻碍者抓住你 之前 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者 同时 到达了一个位置（包括目的地） 都不算 是逃脱成功。

如果不管阻碍者怎么移动都可以成功逃脱时，输出 true ；否则，输出 false 。

 

示例 1：

输入：ghosts = [[1,0],[0,3]], target = [0,1]
输出：true
解释：你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。 

示例 2：

输入：ghosts = [[1,0]], target = [2,0]
输出：false
解释：你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。 

示例 3：

输入：ghosts = [[2,0]], target = [1,0]
输出：false
解释：阻碍者可以和你同时达到目的地。 

 

提示：

• 1 <= ghosts.length <= 100
• ghosts[i].length == 2
• -104 <= xi, yi <= 104
• 同一位置可能有 多个阻碍者 。
• target.length == 2
• -104 <= xtarget, ytarget <= 104

方法一：曼哈顿距离 · Go 实现

思考

你与鬼魂同时移动，问能否先到终点且不被抓。若某鬼到终点的曼哈顿距离不大于你的，它可以在终点或途中拦截。

因此只需你到终点的距离严格小于每一个鬼到终点的距离。你从原点出发。

对于任意一个阻碍者，如果它到目的地的曼哈顿距离小于等于你到目的地的曼哈顿距离，那么它就可以在你到达目的地之前抓住你。因此，我们只需要判断所有阻碍者到目的地的曼哈顿距离是否都大于你到目的地的曼哈顿距离即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为阻碍者的数量。

func escapeGhosts(ghosts [][]int, target []int) bool {
	tx, ty := target[0], target[1]
	for _, g := range ghosts {
		x, y := g[0], g[1]
		if abs(tx-x)+abs(ty-y) <= abs(tx)+abs(ty) {
			return false
		}
	}
	return true
}

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

力扣原题 · Doocs 题解来源

800. 相似 RGB 颜色 🔒

简单1 种解法

标签：数学、字符串、枚举

题目、示例与约束

RGB 颜色 "#AABBCC" 可以简写成 "#ABC" 。

• 例如，"#15c" 其实是 "#1155cc" 的简写。

现在，假如我们分别定义两个颜色 "#ABCDEF" 和 "#UVWXYZ"，则他们的相似度可以通过这个表达式 -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2 来计算。

那么给你一个按 "#ABCDEF" 形式定义的字符串 color 表示 RGB 颜色，请你以字符串形式，返回一个与它相似度最大且可以简写的颜色。（比如，可以表示成类似 "#XYZ" 的形式）

任何 具有相同的（最大）相似度的答案都会被视为正确答案。

 

示例 1：

输入：color = "#09f166"
输出："#11ee66"
解释： 
因为相似度计算得出 -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73
这已经是所有可以简写的颜色中最相似的了

示例 2：

输入：color = "#4e3fe1"
输出："#5544dd"

 

提示：

• color.length == 7
• color[0] == '#'
• 对于任何 i > 0，color[i] 都是一个在范围 ['0', 'f'] 内的 16 进制数

方法一 · Go 实现

思考

可简写颜色的每个通道只能取 $00,11,\dots ,ff$，即 $17$ 的倍数。相似度按三个通道平方差之和衡量，而通道之间互不影响，因此不必在 ${16}^3$ 种简写色上穷举。

对单个通道 $q$，将其表示为 $17y+z$ 后，余数 $z>8$ 时向最近的下一档进位，否则取当前档。三个通道各自取最近简写值再拼接，即得到题目所求颜色。

func similarRGB(color string) string {
	f := func(x string) string {
		q, _ := strconv.ParseInt(x, 16, 64)
		if q%17 > 8 {
			q = q/17 + 1
		} else {
			q = q / 17
		}
		return fmt.Sprintf("%02x", 17*q)

	}
	a, b, c := color[1:3], color[3:5], color[5:7]
	return "#" + f(a) + f(b) + f(c)
}

力扣原题 · Doocs 题解来源