題目

難度：★★☆☆☆
類型：數(shù)組

給定平面上 n 對不同的點(diǎn)，“回旋鏢” 是由點(diǎn)表示的元組 (i, j, k) ，其中 i 和 j 之間的距離和 i 和 k 之間的距離相等（需要考慮元組的順序）。

找到所有回旋鏢的數(shù)量。你可以假設(shè) n 最大為 500，所有點(diǎn)的坐標(biāo)在閉區(qū)間 [-10000, 10000] 中。

示例

輸入:
[[0,0],[1,0],[2,0]]
輸出:
2
解釋:
兩個回旋鏢為 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

解答

為了獲得回旋鏢的數(shù)量，我們需要留意：

1. 回旋鏢的含義。回旋鏢可以看做一個包含三個點(diǎn)的元組，物理含義是一條等腰三角形頂點(diǎn)的記錄（這里的等腰三角形可以是一條線），而且交換底邊上的兩個端點(diǎn)會產(chǎn)生新的記錄；

2. 本題思路。我們需要對所有點(diǎn)進(jìn)行遍歷，用一個字典統(tǒng)計(jì)該點(diǎn)與其他點(diǎn)的距離，字典的鍵是兩點(diǎn)歐氏距離的平方，字典的值是該距離出現(xiàn)的次數(shù)；

3. 重復(fù)問題。如果遇到有兩個以上點(diǎn)與當(dāng)前考察點(diǎn)的距離超過相等（均為val），則需要通過val*(val-1)來計(jì)算所有組合的可能性。

編碼如下：

class Solution:
    def numberOfBoomerangs(self, points):
        res = 0
        for p1 in points:

            # 定義一個距離計(jì)數(shù)器，用于統(tǒng)計(jì)每一個距離出現(xiàn)的次數(shù)
            dist_dict = {}

            for p2 in points:

                dist = (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2      # 計(jì)算p1和p2點(diǎn)距離的平方

                dist_dict[dist] = dist_dict[dist] + 1 if dist in dist_dict else 1   # 更新字典中距離計(jì)數(shù)器

            for val in dist_dict.values():                      # 遍歷每一個出現(xiàn)的距離
                if val >= 2:                                    # 如果出現(xiàn)次數(shù)大于等于2
                    res += val*(val-1)                          # 那么把當(dāng)前兩兩組合的結(jié)果加入res中
        return res

如有疑問或建議，歡迎評論區(qū)留言~