2021-09-13 LeetCode每日一題

鏈接：https://leetcode-cn.com/problems/number-of-boomerangs/

標簽：數(shù)組、數(shù)學、哈希表

題目

給定平面上 n 對 互不相同 的點 points ，其中 points[i] = [xi, yi] 。回旋鏢 是由點 (i, j, k) 表示的元組 ，其中 i 和 j 之間的距離和 i 和 k 之間的距離相等（需要考慮元組的順序）。

返回平面上所有回旋鏢的數(shù)量。

示例 1：

輸入：points = [[0,0],[1,0],[2,0]]
輸出：2
解釋：兩個回旋鏢為 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

輸入：points = [[1,1],[2,2],[3,3]]
輸出：2

示例 3：

輸入：points = [[1,1]]
輸出：0

提示：

• n == points.length
• 1 <= n <= 500
• points[i].length == 2
• -104 <= xi, yi <= 10 ^ 4
• 所有點都 互不相同

分析

以某個坐標為圓心，在同一個圓上的任意兩點，可以和圓心組成一個回旋鏢。所以我們求出以某點為圓心，和其他點可以畫出幾個同心圓。對于同一個圓上的點，我們在知道有幾個點在這個圓上的情況下，利用排列組合，從num個點中有順序的選出兩個點，總共有A(num, 2)種情況。最后把所有的情況加起來就行了。

編碼

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if (points.length < 3) {
            return 0;
        }
        int len = points.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            Map<Double, Integer> map = new HashMap<>();
            for (int j = 0; j < len; j++) {
                if (i == j) {
                    continue;
                }
                Double key = Math.pow(points[i][0] - points[j][0], 2) + 
                            Math.pow(points[i][1] - points[j][1], 2);
                map.put(key, map.getOrDefault(key, 0) + 1);
            }

            for (Map.Entry<Double, Integer> entry : map.entrySet()) {
                if (entry.getValue() >= 2) {
                    // A(val, 2)，有順序的在val個數(shù)里選兩個數(shù)
                    count += (factorial(entry.getValue()) / factorial(entry.getValue() - 2));
                }
            }
        }

        return count;
    }

    private int factorial(int n) {
        int res = 1;
        while (n > 0) {
            res *= n;
            n--;
        }
        return res;
    }
}

請?zhí)砑訄D片描述