LeetCode 题解工作台
带阈值的图连通性
有 n 座城市，编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是： x 和 y 的公因数中，至少有一个 严格大于 某个阈值 threshold 。更正式地说，如果存在整数 z ，且满足以下所有条件，则编号 x 和 y 的城市之间有一条道路： x % z == 0 y % z ==…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
我们可以枚举 以及 的倍数，用并查集将它们连通起来。这样，对于每个查询 $[a, b]$，我们只需要判断 和 是否在同一个连通块中即可。 时间复杂度 $O(n \times \log n \time (\alpha(n) + q))$，空间复杂度 。其中 和 分别是节点数和查询数，而 是阿克曼函数的反函数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
有 n 座城市，编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是： x 和 y 的公因数中，至少有一个 严格大于 某个阈值 threshold 。更正式地说，如果存在整数 z ，且满足以下所有条件，则编号 x 和 y 的城市之间有一条道路：
x % z == 0y % z == 0z > threshold
给你两个整数 n 和 threshold ，以及一个待查询数组，请你判断每个查询 queries[i] = [ai, bi] 指向的城市 ai 和 bi 是否连通（即，它们之间是否存在一条路径）。
返回数组 answer ，其中answer.length == queries.length 。如果第 i 个查询中指向的城市 ai 和 bi 连通，则 answer[i] 为 true ；如果不连通，则 answer[i] 为 false 。
示例 1：
输入：n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]] 输出：[false,false,true] 解释：每个数的因数如下： 1: 1 2: 1, 2 3: 1, 3 4: 1, 2, 4 5: 1, 5 6: 1, 2, 3, 6 所有大于阈值的的因数已经加粗标识，只有城市 3 和 6 共享公约数 3 ，因此结果是： [1,4] 1 与 4 不连通 [2,5] 2 与 5 不连通 [3,6] 3 与 6 连通，存在路径 3--6
示例 2：
输入：n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]] 输出：[true,true,true,true,true] 解释：每个数的因数与上一个例子相同。但是，由于阈值为 0 ，所有的因数都大于阈值。因为所有的数字共享公因数 1 ，所以所有的城市都互相连通。
示例 3：
输入：n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]] 输出：[false,false,false,false,false] 解释：只有城市 2 和 4 共享的公约数 2 严格大于阈值 1 ，所以只有这两座城市是连通的。 注意，同一对节点 [x, y] 可以有多个查询，并且查询 [x，y] 等同于查询 [y，x] 。
提示：
2 <= n <= 1040 <= threshold <= n1 <= queries.length <= 105queries[i].length == 21 <= ai, bi <= citiesai != bi
解题思路
方法一：并查集
我们可以枚举 以及 的倍数，用并查集将它们连通起来。这样，对于每个查询 ，我们只需要判断 和 是否在同一个连通块中即可。
时间复杂度 ，空间复杂度 。其中 和 分别是节点数和查询数，而 是阿克曼函数的反函数。
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def areConnected(
self, n: int, threshold: int, queries: List[List[int]]
) -> List[bool]:
uf = UnionFind(n + 1)
for a in range(threshold + 1, n + 1):
for b in range(a + a, n + 1, a):
uf.union(a, b)
return [uf.find(a) == uf.find(b) for a, b in queries]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should demonstrate understanding of divisor properties and efficient graph representation.
- question_mark
Look for clarity in explaining union-find data structure and its optimizations.
- question_mark
Assess candidate's ability to optimize by preprocessing divisors and minimizing redundant calculations.
常见陷阱
外企场景- error
Failure to preprocess divisors efficiently, leading to excessive computation for each query.
- error
Overcomplicating the solution with unnecessary data structures or algorithms.
- error
Not handling edge cases such as cities with no common divisors greater than the threshold.
进阶变体
外企场景- arrow_right_alt
Different thresholds or varying divisor conditions (e.g., prime numbers only).
- arrow_right_alt
Handling larger inputs with constraints on query counts and city numbers.
- arrow_right_alt
Optimizing for multiple threshold values in a single run to answer all queries efficiently.