สมมติว่าเรามีรายการคะแนนและจำนวน k จุดอยู่ในรูปแบบ (x, y) แทนพิกัดคาร์ทีเซียน เราสามารถจัดกลุ่มจุดสองจุด p1 และ p2 ได้หากระยะห่างระหว่างจุดแบบยุคลิดระหว่างจุดทั้งสองคือ <=k เราต้องหาจำนวนกลุ่มที่ไม่ปะติดปะต่อกันทั้งหมด
ดังนั้น หากอินพุตเหมือนกับคะแนน =[[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]], k =2 ผลลัพธ์จะเป็น 2 เนื่องจากสามารถสร้างสองกลุ่ม:([2,2],[3,3],[4,4]) และ ([11,11],[12,12])
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน dfs() นี่จะใช้เวลาฉัน
-
ถ้าฉันอยู่ในสายตาแล้ว
-
กลับ
-
ใส่ฉันเข้าไปในที่เห็น
-
สำหรับแต่ละ nb ใน adj[i] ทำ
-
dfs(nb)
-
จากวิธีหลัก ให้ทำดังนี้−
-
adj :=แผนที่
-
n :=ขนาดของคะแนน
-
สำหรับ j ในช่วง 0 ถึง n ทำ
-
สำหรับผมอยู่ในช่วง 0 ถึง j ทำ
-
p1 :=คะแนน[i]
-
p2 :=คะแนน[j]
-
ถ้าระยะห่างระหว่าง p1 และ p2
-
ใส่ j ต่อท้าย adj[i]
-
ใส่ i ต่อท้าย adj[j]
-
-
-
-
เห็นแล้ว :=ชุดใหม่
-
ตอบ :=0
-
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
-
ถ้าฉันไม่เห็นแล้ว
-
ans :=ans + 1
-
dfs(i)
-
-
-
กลับมาอีกครั้ง
-
-
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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
