Leetcode 447. Number of Boomerangs

周国辉发布于2019-08-14 17:16 / 1575人阅读

摘要：所以给定一个点的数组，要依次选择每个点当做第一个点，依次求出它跟其他点的距离，如果相等则给结果加一，最后返回总数。数据结构去存储距离和这个距离出现的次数。代码满足条件的点的排列组合结果数

题目：

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]]

解法：

这道题主要条件是计算三点中第一个点到第二个点的距离和第一个点到第三个点的距离是否相等，因为顺序有关，所以要返回到底有多少排列满足这个条件。所以给定一个点的数组，
要依次选择每个点当做第一个点，依次求出它跟其他点的距离，如果相等则给结果加一，最后返回总数。

数据结构：

HashMap去存储距离和这个距离出现的次数。

代码：

public int numberOfBoomerangs(int[][] points){
    int result = 0;
    HashMap() map= 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]);
            map.put(distance, map.getOrDefault(distance,0)+1);
        }
        for(int val : map.values()){
            result += val*(val-1); //满足条件的点的排列组合结果数
        }
        map.clear();
    }

    return result;
}

public int getDistance(int[] point1, int[] point2){
    int x = point1[0] - point2[0];
    int y = point1[1] - point2[1];
    return x*x + y*y;
}

私有云云服务器 Boomerangs LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66529.html

447. Number of Boomerangs

摘要：题目链接遍历每个，然后找和它等距离的其他，按距离来保存，比如有一个点，和它距离都是的点有，，，那么一共的组合就有种，包括。这么算是不考重复的情况下。还有可能坐标完全相同，那么和会被当成两个点算两次。 447. Number of Boomerangs 题目链接：https://leetcode.com/problems... 遍历每个point，然后找和它等距离的其他point，按距离...

baukh789 2019-08-14 17:28 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode[191] Number of 1 Bits

摘要：依次移位复杂度思路依次移动位数进行计算。代码利用性质复杂度，思路代码 LeetCode[191] Number of 1 Bits Write a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Fo...

Scliang 2019-08-14 15:00 评论0 收藏0