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: 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<Integer, Integer>() 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;
}

评论

暂无评论