安阳+网站建设,湖南做网站 联系磐石网络,wordpress 回复下载插件,如何做微信小程序开发447. 回旋镖的数量
给定平面上 n 对 互不相同 的点 points #xff0c;其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 #xff0c;其中 i 和 j 之间的距离和 i 和 k 之间的距离相等#xff08;需要考虑元组的顺序#xff09;。
返回平面上所有回旋镖的…447. 回旋镖的数量
给定平面上 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解题思路
枚举哈希表
对于每个点我们计算出它与其他点的距离。对于到该点距离相同的点我们加入到该距离对应的list中该list中的任意两个点都可以与该点形成回旋镖通过排列组合我们可以计算出可以形成的回旋镖的个数
代码
class Solution {public int numberOfBoomerangs(int[][] points) {int npoints.length;MapInteger,ListInteger[] mapnew HashMap[n];for(int i0;in;i)map[i]new HashMap();for(int i0;in;i)for(int ji1;jn;j){int x1points[i][0],y1points[i][1],x2points[j][0],y2points[j][1];int d(x1-x2)*(x1-x2)(y1-y2)*(y1-y2);if(!map[i].containsKey(d))map[i].put(d,new ArrayList());if(!map[j].containsKey(d))map[j].put(d,new ArrayList());map[i].get(d).add(j);map[j].get(d).add(i);}int res0;for(int i0;in;i){for(List l:map[i].values()){if(l.size()2)resl.size()*(l.size()-1);}}return res;}
}
