leetcode-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
2
3
4
5
6
7
8
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]]

分析

输入是一些点的集合，首先给出一个回旋镖的概念，假设有 a, b, c 三个点，如果 ab 的距离等于 ac 的距离，则称 [a, b, c] 为回旋镖结构，a b c 的顺序是需要考虑的。求满足回旋镖概念的个数。

我们可以遍历所有节点，每个节点都可以作为 a，然后计算其余节点与 a 节点的距离，以距离进行分组，比如与 a 距离 x 的点有 n 个，那么这一组节点可以组成 n(n-1) 个回旋镖结构。

解决方案1(Javascript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
    var result = 0;
    var length = points.length;
    
    for (let i = 0; i < length; i++) {
        var map = new Map();
        for (let j = 0; j < length; j++) {
            if (i == j) {
                continue;
            }
            var distance = (points[i][0]-points[j][0])*(points[i][0]-points[j][0]) + (points[i][1]-points[j][1])*(points[i][1]-points[j][1]);
            map.set(distance, (map.get(distance) || 0) + 1);
        }
        map.forEach(value => {
            result += value*(value-1);
        })
    }
    return result;
};

相关问题

(M) Line Reflection

题目来源