Giả sử ta có n điểm trên mặt phẳng mà tất cả đều khác nhau từng cặp một. Một "boomerang" là một bộ ba điểm như (i, j, k) sao cho khoảng cách giữa i và j bằng khoảng cách giữa i và k. Ta cần tìm số lượng boomerang.
Ví dụ, nếu đầu vào là [[0,0],[1,0],[2,0]], thì đầu ra sẽ là 2, vì hai boomerang là [[1,0],[0,0],[2,0]] và [[1,0],[2,0],[0,0]].
Để giải quyết, ta thực hiện các bước sau:
- counter_of_boomerangs := 0
- Với mỗi point_1 trong mảng points, thực hiện:
- x1, y1 = point_1
- Định nghĩa một map gọi là distance_count_dict
- Với mỗi point_2 trong mảng points, thực hiện:
- x2, y2 = point_2
- diff_x := x2 - x1
- diff_y := y2 - y1
- dist := diff_x^2 + diff_y^2
- distance_count_dict[dist] := distance_count_dict[dist] + 1
- Với mỗi d trong distance_count_dict:
- n := distance_count_dict[d]
- counter_of_boomerangs := counter_of_boomerangs + n * (n - 1)
- Trả về counter_of_boomerangs
Ví dụ
Hãy xem triển khai sau để hiểu rõ hơn:
from collections import defaultdict class Solution: def numberOfBoomerangs(self, points): counter_of_boomerangs = 0 for point_1 in points: x1, y1 = point_1 distance_count_dict = defaultdict(int) for point_2 in points: x2, y2 = point_2 diff_x = x2-x1 diff_y = y2-y1 dist = diff_x ** 2 + diff_y ** 2 distance_count_dict[dist] += 1 for d in distance_count_dict: n = distance_count_dict[d] counter_of_boomerangs += n * (n-1) return counter_of_boomerangs ob = Solution() print(ob.numberOfBoomerangs([[0,0],[1,0],[2,0]]))
Đầu vào
[[0,0],[1,0],[2,0]]
Đầu ra
0