LeetCode 447*. 回旋镖的数量(Python)

本文阅读 2 分钟
首页 代码,Java 正文

给定平面上 n 对不同的点,“回旋镖” 是由点表示的元组 (i, j, k) ,其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)

找到所有回旋镖的数量。你可以假设 n 最大为500,所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输入:

[[0,0],[1,0],[2,0]]

输出:

2

解释:

两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

思路:

①利用查找表方法,由于数据规模不超过500 ,所以可以设计一个O(n^2)的算法

②对于元组(i, j, k),要判断的是 i 和 j、i 和 k 之间的距离,所以以 i 建立查找表,以 i 到剩余点的距离为key,每有一个数该key的value就加1

③最后根据每一个距离对应的点的个数来计算输出,即,img

④由于是距离作为key,所以应该避免小数的出现,因此在计算距离时省去开方操作

⑤由于点的坐标区间在 [-10000, 10000] 中,所以距离的平方不会超过int的范围

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        res = 0       
        for i in points:
            record = dict()
            for j in points:    # 先初始化字典
                if i != j:
                    record[self.dis(i, j)] = 0
            for j in points:
                if i != j:
                    record[self.dis(i, j)] = record[self.dis(i, j)] + 1
            
            for key in record:
                res = res + record[key]*(record[key] - 1)
        
        return res
    
    
    # 返回距离,避免出现小数此时使用平方值作为距离
    def dis(self, pointa, pointb):
        return (pointa[0] - pointb[0])*(pointa[0] - pointb[0]) + (pointa[1] - pointb[1])*(pointa[1] - pointb[1])

 

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://wangjiawei.blog.csdn.net/article/details/103205335
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复