64. LeetCode 447. 回旋镖的数量.

• 标签： 哈希表
• 难度： 中等

• 题目描述

• 我的解法

遍历每个点，计算其他点到自身的距离，得到一个二维矩阵 dist。 对 dist 每行的值用字典计数， 若计数值 val 大于等于 2, 则结果数加上 . 这么暴力的解法击败了 的用户。

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        n = len(points)
        dist = [[0]*len(points) for _ in range(n)]
        for i in range(n):
            for j in range(n):
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]
                dist[i][j] = dx**2 + dy**2   
        result = 0
        for i in range(n):
            ctr = {}
            for j in range(n):
                if ctr.get(dist[i][j], 0) == 0:
                    ctr[dist[i][j]] = 1
                else:
                    ctr[dist[i][j]] += 1
            for key, val in ctr.items():
                num = 1
                if val >= 2:
                    for i in range(val - 1, val + 1):
                        num *= i
                    result += num
        return result

• 其他解法

暂略。