网站设计培训学校有哪些,深圳做购物网站,seo建站教程,长沙网站建设湘icp备LeetCode
回旋镖的数量
447. 回旋镖的数量 - 力扣#xff08;LeetCode#xff09;
题目描述
给定平面上 n 对 互不相同 的点 points #xff0c;其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 #xff0c;其中 i 和 j 之间的距离和 i 和 k 之间的欧式…LeetCode
回旋镖的数量
447. 回旋镖的数量 - 力扣LeetCode
题目描述
给定平面上 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.length1 n 500points[i].length 2-104 xi, yi 104所有点都 互不相同
思路
枚举 哈希表
代码
C
#include vector
#include unordered_mapclass Solution {
public:// 计算回旋镖的数量int numberOfBoomerangs(std::vectorstd::vectorint points) {int length points.size();if (length 3) return 0;int ans 0;// 遍历所有点for (int i 0; i length; i) {std::unordered_mapint, int counter;// 计算距离并统计相同距离的点for (int j 0; j length; j) {int dist (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);int same counter[dist];ans same;counter[dist];}}// 每组回旋镖的数量乘以2因为可以交换点的顺序return ans * 2;}
};Java
class Solution {public int numberOfBoomerangs(int[][] points) {int length points.length;if(length 3) return 0;int ans 0;for(int i 0; i length; i){MapInteger,Integer counter new HashMap();for(int j 0; j length; j){int dist (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);int smae counter.getOrDefault(dist,0);ans smae;counter.put(dist, smae 1);}}return ans * 2;}
}
