给定平面上 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 <= 104
- 所有点都 互不相同
Related Topics
9月13日 今天的每日一题
就,摁解,遍历求解每一个点,和其他点距离相同的个数,比如有点的几个【P1,P2,P3,P4】,从P1开始,算出P1与所有点的距离情况,并统计出距离相同的情况个数。
假设有3个连线的距离相等,这3条线为L1(P1,P2),L2(P1,P3),L3(P1,P4),则这三条线仍然有不同的组合可能,(L1,L2)、(L1、L3)、(L2、L4),已知公式两两组合的可能性个数为n*(n-1)/2,又因为题面中提出了有顺序不同,可以反向也算一种,那么就可以把底部的除2约掉
则统计出有n条长度相同的线的话就可以得到 有n*(n-1)种可能组合
代码
class Solution {
public int numberOfBoomerangs(int[][] points) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
final int[] count = {0};
int[] point1,point2;
for (int i = 0; i < points.length; i++) {
point1 = points[i];
hashMap.clear();
for (int j = 0; j < points.length; j++) {
if (i==j)continue;
point2 = points[j];
int distance = (point1[0]-point2[0])*(point1[0]-point2[0]) + (point1[1]-point2[1])*(point1[1]-point2[1]);
hashMap.put(distance,hashMap.getOrDefault(distance,0)+1);
}
hashMap.forEach((key, value) -> {
if (value > 1) {
count[0] += value * (value - 1);
}
});
}
return count[0];
}
}
发表评论