Số lượng Boomerang trong Python

Giả sử chúng ta có n điểm trong mặt phẳng phân biệt từng cặp. Bây giờ một "boomerang" là một tập hợp các điểm như (i, j, k) sao cho khoảng cách giữa i và j cũng giống như khoảng cách giữa i và k. Chúng ta phải tìm số lượng boomerang.

Vì vậy, 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 vấn đề này, chúng tôi sẽ làm theo các bước sau -

• counter_of_boomerangs:=0

• đối với mỗi điểm_1 trong mảng điểm, thực hiện

  • x1, y1 =point_1

  • xác định một bản đồ có tên là distance_count_dict

  • đối với mỗi điểm_2 trong mảng điểm, 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

  • cho mỗi d trong distance_count_dict -

    • n:=distance_count_dict [d]

    • counter_of_boomerangs:=counter_of_boomerangs + n * (n - 1)

• trả lại counter_of_boomerangs

Ví dụ

Hãy cùng chúng tôi xem cách 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