作者: 负雪明烛
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