一、题目
You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. 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).
Return the number of boomerangs.
Example 1:
Input: points = [[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]].
Example 2:
Input: points = [[1,1],[2,2],[3,3]]
Output: 2
Example 3:
Input: points = [[1,1]]
Output: 0
Constraints:
n == points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
All the points are unique.文章来源:https://www.toymoban.com/news/detail-786916.html
二、题解
对于每个数i,统计数组中除i以外的所有数到i的距离,并将个数保存到map中。文章来源地址https://www.toymoban.com/news/detail-786916.html
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int n = points.size();
int res = 0;
for(int i = 0;i < n;i++){
unordered_map<int,int> map;
for(int j = 0;j < n;j++){
if(i == j) continue;
int dist = pow(points[i][0] - points[j][0],2) + pow(points[i][1] - points[j][1],2);
map[dist]++;
}
for(auto it = map.begin();it != map.end();it++){
int m = it->second;
res += m * (m-1);
}
}
return res;
}
};
到了这里,关于LeetCode447. Number of Boomerangs的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!