用 Python 将一组点分组为 k 个不同组的程序
pythonserver side programmingprogramming更新于 2026/1/15 1:16:17
假设我们有一个点列表和一个数字 k。这些点的形式为 (x, y)，表示笛卡尔坐标。如果任意两个点 p1 和 p2 之间的欧几里得距离小于等于 k，我们可以将它们分组，我们必须找到不相交组的总数。
因此，如果输入为 points = [[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]], k = 2，则输出将为 2，因为它可以组成两个组:([2,2],[3,3],[4,4]) 和 ([11,11],[12,12])
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 dfs() 。这将需要 i
如果 i 在 seen 中，则
返回
将 i 插入 seen
对于 adj[i] 中的每个 nb，执行
dfs(nb)
从主方法中，执行以下操作−
adj := 地图
n := 点的大小
对于 j 在 0 到 n 的范围内，执行
对于 i 在 0 到 j 的范围内，执行
p1 := points[i]
p2 := points[j]
如果 p1 和 p2 之间的欧几里得距离 < k，则
在 adj[i] 末尾插入 j
在 adj[j] 末尾插入 i
seen := 一个新集合
and := 0
对于范围从 0 到 n 的 i，执行
if i not seen, then
ans := ans + 1
dfs(i)
返回 ans
让我们看看下面的实现以便更好地理解 −
示例
from collections import defaultdict class Solution: def solve(self, points, k): adj = defaultdict(list) n = len(points) for j in range(n): for i in range(j): x1, y1 = points[i] x2, y2 = points[j] if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= k ** 2: adj[i].append(j) adj[j].append(i) seen = set() def dfs(i): if i in seen: return seen.add(i) for nb in adj[i]: dfs(nb) ans = 0 for i in range(n): if i not in seen: ans += 1 dfs(i) return ans ob = Solution() points = [ [2, 2], [3, 3], [4, 4], [11, 11], [12, 12] ] k = 2 print(ob.solve(points, k))
输入
[[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]],2
输出
2
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
