博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode 447 Number of Boomerangs
阅读量:5742 次
发布时间:2019-06-18

本文共 1687 字,大约阅读时间需要 5 分钟。

Problem:

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:2Explanation:The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Summary:

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

Analysis:

若在一组点集{a, b, c, d, ...}中,以点a为一个端点,与dis(a, b)相等的点存在n个(包含点b),那么在这n个点中任意选出两个点与点a构成三元组,则有n(n - 1) / 2种情况。但因为三元组[a, b, c]与三元组[a, c, b]并不相同,所以实际为排列问题,答案为n(n - 1)。

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

1 class Solution { 2 public: 3     int numberOfBoomerangs(vector
>& points) { 4 int len = points.size(), res = 0; 5 unordered_map
m; 6 7 for (int i = 0; i < len; i++) { 8 for (int j = 0; j < len; j++) { 9 int x = points[i].first - points[j].first;10 int y = points[i].second - points[j].second;11 m[x * x + y * y]++;12 }13 14 unordered_map
:: iterator it;15 for (it = m.begin(); it != m.end(); it++) {16 int tmp = it->second;17 res += tmp * (tmp - 1);18 }19 m.clear();20 }21 22 return res;23 }24 };

转载于:https://www.cnblogs.com/VickyWang/p/6065236.html

你可能感兴趣的文章
SharedPreferences
查看>>
系统session超时时间的设置
查看>>
load
查看>>
as 快捷键
查看>>
郑捷《机器学习算法原理与编程实践》学习笔记(第六章 神经网络初步)6.2 BP神经网络...
查看>>
2_C语言中的数据类型 (九)逻辑运算符与if语句、switch、条件运算符?、goto语句与标号...
查看>>
左右相等
查看>>
linux 客户端 Socket 非阻塞connect编程
查看>>
Design Diagram
查看>>
Modernizr——为HTML5和CSS3而生!
查看>>
hdu 2852 KiKi's K-Number (线段树)
查看>>
网关通讯
查看>>
HDU 1069:Monkey and Banana(DP)
查看>>
[论文]Sketch-based 3D model retrieval by viewpoint entropy-based adaptive view clustering
查看>>
总结五个小技巧定位数据库性能问题
查看>>
Metasploit one test
查看>>
ECMAScript5新特性之Object.isExtensible、Object.preventExtensions
查看>>
zlhome.com Deal
查看>>
解决android studio引用远程仓库下载慢(JCenter下载慢)
查看>>
关于书中堆积的程序修改
查看>>