ได้ n จุดบนระนาบ (ไม่ซ้ำกัน) "บุเมรัง" คือ 3 จุด (i,j,k) ที่ระยะห่าง i-j = i-k นับจำนวนบุเมรังทั้งหมด (ลำดับสำคัญ)
ตัวอย่าง
[[0,0],[1,0],[2,0]] → บุเมรัง: ([1,0],[0,0],[2,0]) และ ([1,0],[2,0],[0,0]) → 2
ขั้นตอนการแก้ปัญหา
- วนแต่ละจุดเป็น
i(จุดศูนย์กลาง) - คำนวณระยะยกกำลังสองไปยังจุดอื่นทั้งหมด เก็บจำนวนใน dict
- แต่ละระยะที่มี
nจุด → เพิ่มn * (n-1)บุเมรัง - รวมทั้งหมด
การติดตั้งใน Python
from collections import defaultdict
class Solution:
def numberOfBoomerangs(self, points):
ans = 0
for x1, y1 in points:
dist_count = defaultdict(int)
for x2, y2 in points:
dx, dy = x2 - x1, y2 - y1
dist_count[dx*dx + dy*dy] += 1
for n in dist_count.values():
ans += n * (n - 1)
return ans
ob = Solution()
print(ob.numberOfBoomerangs([[0,0],[1,0],[2,0]])) # 2
อินพุต / เอาต์พุต
Input: [[0,0],[1,0],[2,0]] Output: 2
