2021-09-13 LeetCode每日一题
链接：https://leetcode-cn.com/problems/number-of-boomerangs/
标签：数组、数学、哈希表
题目
给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
返回平面上所有回旋镖的数量。
示例 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个数里选两个数
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;
}
}
请添加图片描述
