leetcode [#415]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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

---

解决方案

public class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int count = 0;
        for (int i = 0; i < points.length; i++) {
            HashMap<Double, Integer> map = new HashMap<Double, Integer>();
            for (int j = 0; j < points.length; j++) {
                double dis = distance(points[i], points[j]);
                if (!map.containsKey(dis)) {
                    map.put(dis, 0);
                }
                count += map.get(dis) * 2;
                map.put(dis, map.get(dis) + 1);
            }
        }
        return count;
    }
    private static double distance(int[] first, int[] second){
        int a1 = first[0];
        int b1 = first[1];
        int a2 = second[0];
        int b2 = second[1];
        return Math.pow((a1-a2), 2) + Math.pow((b1-b2), 2);
    }
}

---

注意事项

1. 本题题意是：在二维直角坐标系中给出一组坐标点，若存在三个点[i,j,k],i和j的距离与i和k的距离相等，则记为“一组”，求所都点中共有多少这样的组。
2. 计算距离单独抽出函数。
3. 两次遍历该二维数组，使用数据结构HashMap，计算两点间距离，如果map中不包含该距离值，将其存入map(作为key)，对应的值为0；如果map中已包含该距离值，则要将对应value更新：加一。表明截止目前，互相距离满足[i,j,k]关系的有value组。
4. 不能使用比如HashSet这样的数据结构，虽然可以存储距离且去重，但是无法记录重复次数，导致求和无法进行。