【LeetCode】447. Number of Boomerangs 解题报告(Java & Python)

【LeetCode】447. Number of Boomerangs 解题报告(Java & Python)[LeetCode]https://leetcode.com/problems/number-of-boomerangs/Difficulty:EasyQuestionGivennpointsintheplaneth

作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/


[LeetCode]

题目地址:https://leetcode.com/problems/number-of-boomerangs/

  • Difficulty: Easy

题目描述

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

题目大意

如果一个三元组,第一个元素和第二个元素的距离 等于 第一个元素和第三个元素的距离,那么是一个回旋镖。问题目给出的n个长度的点中,有多少个回旋镖。

解题方法

题目的意思是找出距离到其他的点都相等的点,并且判断相等的路径的排列有多少条。

尝试暴力解决。

双重循环是没有问题的,因为题目要求出一个点到其余各个点的距离,因此,必须有双重循环。在存储距离的时候,要使用HashMap,这里有个技巧,可以节省代码:hashmap.put(distance, hashmap.getOrDefault(distance, 0) + 1);,如果没有这个距离的话,就放入1,有的话就把之前的值加1。

在这个大的循环里边,遍历完到其余个点的距离后,再把HashMap中的距离相等的值给拿出来,如果某个点到其他的点的距离都不相等,那么这个值是1,所以结果为0;否则是N*(N-1).

public class Solution { 
   
    public int numberOfBoomerangs(int[][] points) { 
   
        int res = 0;
        HashMap<Integer, Integer> hashmap=new HashMap<>();
        for(int i =0; i< points.length; i++){ 
   
            for(int j=0; j< points.length; j++){ 
   
                if(i == j){ 
   
                    continue;
                }
                int distance = getDistance(points[i], points[j]);
                hashmap.put(distance, hashmap.getOrDefault(distance, 0) + 1);
                
            }
            for(int val : hashmap.values()) { 
   
                res += val * (val-1);
            }            
            hashmap.clear();
        }
        return res;
    }
    public int getDistance(int[] point1, int[] point2){ 
   
        int dx= point2[0] - point1[0];
        int dy=point2[1] - point1[1];
        return dx*dx + dy*dy;
    }
}

AC: 188 ms 超过61%

python写法:

class Solution:
    def numberOfBoomerangs(self, points):
        """ :type points: List[List[int]] :rtype: int """
        res = 0
        for p0 in points:
            d = collections.defaultdict(int)
            for p1 in points:
                d[(p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2] += 1
            for d, v in d.items():
                res += v * (v - 1)
        return res

日期

2017 年 1 月 12 日
2018 年 11 月 14 日 —— 很严重的雾霾

今天的文章【LeetCode】447. Number of Boomerangs 解题报告(Java & Python)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/60526.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注