0447. Number of Boomerangs

447. Number of Boomerangs #

题目 #

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 1:


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

题目大意 #

在一个 Point 的数组中求出 (i,j,k) 三元组,要求 j 和 i 的距离等于 k 和 i 的距离。这样的三元组有多少种?注意 (i,j,k) 和 (j,i,k) 是不同的解,即元素的顺序是有关系的。

解题思路 #

这道题考察的是哈希表的问题。

首先依次求出两两点之间的距离,然后把这些距离记录在 map 中,key 是距离,value 是这个距离出现了多少次。求距离一般都需要开根号,但是 key 如果为浮点数就会有一些误差,所以计算距离的时候最后一步不需要开根号,保留平方差即可。

最后求结果的时候,遍历 map,把里面距离大于 2 的 key 都拿出来,value 对应的是个数,在这些个数里面任取 2 个点就是解,所以利用排列组合,C n 2 就可以得到这个距离的结果,最后把这些排列组合的结果累积起来即可。

代码 #


package leetcode

func numberOfBoomerangs(points [][]int) int {
	res := 0
	for i := 0; i < len(points); i++ {
		record := make(map[int]int, len(points))
		for j := 0; j < len(points); j++ {
			if j != i {
				record[dis(points[i], points[j])]++
			}
		}
		for _, r := range record {
			res += r * (r - 1)
		}
	}
	return res
}

func dis(pa, pb []int) int {
	return (pa[0]-pb[0])*(pa[0]-pb[0]) + (pa[1]-pb[1])*(pa[1]-pb[1])
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者