Giả sử chúng ta có một danh sách các điểm và một số k. Các điểm có dạng (x, y) biểu diễn tọa độ Descartes. Chúng ta có thể nhóm hai điểm p1 và p2 bất kỳ nếu khoảng cách Euclide giữa chúng là <=k, chúng ta phải tìm tổng số nhóm rời rạc.
Vì vậy, nếu đầu vào giống như điểm =[[2, 2], [3, 3], [4, 4], [11, 11], [12, 12]], k =2, thì đầu ra sẽ là 2, vì nó có thể tạo thành hai nhóm:([2,2], [3,3], [4,4]) và ([11,11], [12,12])
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm dfs (). Điều này sẽ mất tôi
-
nếu tôi được nhìn thấy, thì
-
trở lại
-
chèn tôi vào thấy
-
đối với mỗi nb trong adj [i], thực hiện
-
dfs (nb)
-
Từ phương thức chính, hãy thực hiện như sau−
-
adj:=một bản đồ
-
n:=kích thước của điểm
-
đối với j trong phạm vi từ 0 đến n, thực hiện
-
đối với tôi trong phạm vi từ 0 đến j, hãy làm
-
p1:=điểm [i]
-
p2:=điểm [j]
-
nếu khoảng cách Euclide giữa p1 và p2
-
chèn j vào cuối adj [i]
-
chèn tôi vào cuối adj [j]
-
-
-
-
đã thấy:=một tập hợp mới
-
ans:=0
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
nếu tôi không thấy, thì
-
ans:=ans + 1
-
dfs (i)
-
-
-
trả lại ans
-
-
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
[[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]],2
Đầu ra
2