文档章节

“回形镖”的个数 Number of Boomerangs

叶枫啦啦
 叶枫啦啦
发布于 2017/06/12 13:37
字数 623
阅读 6
收藏 0

问题:

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

【解析】

定义一种类似“回形镖”的三元组结构,即在三元组(i, j, k)中i和j之间的距离与i和k之间的距离相等。找到一组坐标数据中,可构成几组这样的“回形镖”结构。

解决:

①点(x,y)与(x1,y1)之间的距离为(x1 - x) * (x1 - x) + (y1 - y) * (y1 - y),将与点(x,y)距离相同的点保存在hashmap中,这样就找到了n个与与点(x,y)距离相同的点。那么在这n个点中任意选出两个点与点(x,y)构成三元组,有n*(n -1)种排列组合方式(与排列顺序有关)。

代码中正是以此为基本思想,找到以每一个点为端点时,与其余点共组成多少种不同的距离,此处用hashmap记录,key为距离长度,value为距离出现次数。再根据前面的公式计算即可。耗时265 ms

public class Solution {
    public int numberOfBoomerangs(int[][] points) {  
        int count = 0;  
        for (int i = 0;i < points.length ;i ++ ) {//记录下(x1,y1)相对于点(x,y)
            int x = points[i][0];
            int y = points[i][1];
            Map<Long,Integer> map = new HashMap<>();//键---距离,值---距离相同的点的个数,必须放在循环内
            for (int j = 0;j < points.length ;j ++ ) {
                int x1 = points[j][0];
                int y1 = points[j][1];
                long distance = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
                map.put(distance,map.getOrDefault(distance,0) + 1); 
            }
            for (Map.Entry<Long,Integer> entry : map.entrySet()) {//必须放在循环内计算
                int val = entry.getValue();
                count += val * (val - 1);//距离相同的点有n*(n-1)种排列组合方式
            }
        }
        return count;
    }  
}

②直接统计可以进行的排列个数,耗时107ms。

public class Solution {
    public int numberOfBoomerangs(int[][] points) {  
        int count = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int[] p1 : points){//遍历节点
            for(int[] p2 :points){
                if(p1 == p2) continue;//同一个点则略过
                int distance = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);//计算两点间的距离
                int preCount = map.getOrDefault(distance,0);
                count += 2 * preCount;//p1,p2两个位置可以颠倒
                map.put(distance,preCount + 1);
            }
            map.clear();
        }
        return count;
    }  
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
LeetCode算法题-Number of Boomerangs(Java实现)

这是悦乐书的第231次更新,第244篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第98题(顺位题号是447)。给定平面中的n个点都是成对不同的,“回旋镖”是点(i,j,k)的元组...

小川94
01/15
0
0
Leetcode PHP题解--D103 447. Number of Boomerangs

D103 447. Number of Boomerangs 题目链接 447. Number of Boomerangs 题目分析 给定一个坐标数组,从中任意取3个坐标,使得从i到j的距离等于i到k的距离。且与不是同一个组合,需单独计算。 ...

skys215
07/14
13
0
leetcode题解(查找表问题)

查找,是使用计算机处理问题时的一个最基本的任务,因此也是面试中非常常见的一类问题。很多算法问题的本质,就是要能够高效查找。学会使用系统库中的map和set,就已经成功了一半。 set的使用...

吴小琪
2018/06/21
0
0
窥探 Swift 之 函数与闭包的应用实例

窥探 Swift 之 函数与闭包的应用实例 今天的博客算是比较基础的,还是那句话,基础这东西在什么时候都是最重要的。说到函数,只要是写过程序就肯定知道函数是怎么回事,今天就来讨论一下Swi...

法斗斗
2016/06/22
9
0
程序员逆天改命之被破解

西门吹雪原创 因“我去”语气助词的误解以及闯荡江湖的躁动,程班云在经历冷酷的逻辑面试后,在德威镖局的监控部门开始了新的悟道修炼。 悟道 相比在c++山庄每日背读“代码大全”或“Linux高...

奇哥十年程序
2017/12/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

记一次项目启动报java.lang.StackOverflowError

项目是spring boot,之前没有问题,突然有一次debug方式启动的时候报这个错误。 因为其他同事没有问题,线上也没有问题,所以先排除了是代码问题。 开始以为电脑开的软件太多,然后给jvm的内存...

chro008
21分钟前
12
0
idea 2019.2免费激活码

亲测有效到2020.6 812LFWMRSH-eyJsaWNlbnNlSWQiOiI4MTJMRldNUlNIIiwibGljZW5zZWVOYW1lIjoi5q2j54mIIOaOiOadgyIsImFzc2lnbmVlTmFtZSI6IiIsImFzc2lnbmVlRW1haWwiOiIiLCJsaWNlbnNlUmVzdHJpY3Rpb......

Iverson58
29分钟前
7
0
移动APP开发中的重要注意事项

您的移动app在变化吗?如果没有,请确保遵循这些提示进行移动app开发。大多数行业的IT领导者都优先考虑劳动力和消费者的移动性。实现成功的移动app开发具有挑战性,涉及在app功能开发的基础上...

a429011717
36分钟前
6
0
Qt编写自定义控件69-代码行数统计

一、前言 代码行数统计主要用来统计项目中的所有文件的代码行数,其中包括空行、注释行、代码行,可以指定过滤拓展名,比如只想统计.cpp的文件,也可以指定文件或者指定目录进行统计。写完这...

飞扬青云
55分钟前
12
0
驰骋工作流引擎-ccflow关于 “ 是否自动计算未来的处理人”的功能变更

关键字:流程未来节点处理人 工作流快速开发平台 工作流流设计 业务流程管理 asp.net 开源工作流 业务背景:一个流程在启动起来后,是可以对一些节点计算出来处理人是谁,流程的走向。对于另...

孟娟
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部