【Leetcode】 447. 回旋镖的数量

本文主要是介绍【Leetcode】 447. 回旋镖的数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

447. 回旋镖的数量

思路

问题要求计算平面上所有回旋镖的数量，即找到满足题设条件的点组合 (i, j, k)。回旋镖的定义是指有两个相同的距离，分别从点 i 到 j 和点 i 到 k。具体思路是：

遍历每个点，以其为中心，计算它与其他点的距离，并将这些距离存储下来。

对于每个点 i，遍历其余所有点 j，计算点 i 到点 j 的距离，并将距离作为键，出现的频次作为值，存储在哈希表中。

针对每个点 i，遍历哈希表中记录的距离和频次，如果某个距离有至少两个点与点 i 的距离相等，则可以形成回旋镖。对于每个满足条件的距离 d，假设有 m 个点与点 i 的距离等于 d，则回旋镖的数量为 m * (m - 1)，因为对于第一个点有 m 种选择，对于第二个点有 m - 1 种选择。

统计所有点的回旋镖数量，并将其累加，最后得到所有回旋镖的总数。

代码

class Solution {
public:int numberOfBoomerangs(vector<vector<int>>& points) {int n = points.size(), res = 0;vector<unordered_map<int,int>>mapp(n);for(int i = 0;i < n; ++i){for(int j = i + 1; j < n; ++j){auto t = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2);res -= mapp[i][t] * (mapp[i][t] - 1);res -= mapp[j][t] * (mapp[j][t] - 1);mapp[i][t]++;mapp[j][t]++;res += mapp[i][t] * (mapp[i][t] - 1);res += mapp[j][t] * (mapp[j][t] - 1);}}return res;}
};

这篇关于【Leetcode】 447. 回旋镖的数量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---