专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近在网上一后端开发工程师发出一奇葩言论：程序员工资太高了，建议降薪。这脑袋究竟长几个包，竟然发出这样的言论，工资的高低是有市场决定的，程序员这工资相比较明星，网红来说，简直不值一提。
实际上程序员的学历并不低，大部分都是本科以上学历，尤其是一线城市的大厂，211,985以上的随处可见，有些岗位比如大数据，人工智能，基本上都是硕士起步，搞不明白这点工资怎么就高了。就像评论区的一位网友说的：一个乞丐只会嫉妒另外一个乞丐饭碗里多了一根鸡腿。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第447题：回旋镖的数量。
问题描述
来源：LeetCode第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
n == points.length
1 <= n <= 500
points[i].length == 2
-10^4 <= xi, yi <= 10^4
所有点都 互不相同
问题分析
这题是让计算回旋镖的数量，回旋镖的形状如下，它有一个顶点，我们以当前顶点为起始点，计算当前顶点到其他所有点的距离。
假如到当前顶点距离为 m 的有 n 条边，这 n 条边随便选择两条即可构成回旋镖，那么这 n 条边构成总的回旋镖（必须以当前点为顶点）数量为n*(n-1)，如果还有其他距离相同的边也可以构成回旋镖，只需要累加即可计算以当前点为顶点所构成的回旋镖的数量。
如果要计算所有回旋镖的数量，我们需要以每一个点为顶点都计算一遍即可，代码如下。
JAVA：
public int numberOfBoomerangs(int[][] points) { int res = 0; Map
map = new HashMap<>(); for ( int[] point1 : points) { // 以其中一个点为起始点，计算到其他所有点的距离。 for ( int[] point2 : points) { int dis = (point1[ 0] - point2[ 0]) * (point1[ 0] - point2[ 0]) + (point1[ 1] - point2[ 1]) * (point1[ 1] - point2[ 1]); map.put(dis, map.getOrDefault(dis, 0) + 1); } // 假如到当前点距离为m的有n条边，那么这n条边随便选择两条都可以构成回旋镖， // 所以组合的数量是n*(n-1)，这里只需要累加即可。 for ( int val : map.values()) res += val * (val - 1); map.clear(); // 这里要清空，下一步以下一个点为起始点计算。 } return res; }C++：
public: int numberOfBoomerangs(vector
>& points) { int res = 0; unordered_map
map; for (auto &point1 : points) {// 以其中一个点为起始点，计算到其他所有点的距离。 for (auto &point2 : points) { int dis = (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]); map[dis]++; } // 假如到当前点距离为m的有n条边，那么这n条边随便选择两条都可以构成回旋镖， // 所以组合的数量是n*(n-1)，这里只需要累加即可。 for (const auto& kv : map) res += kv.second * (kv.second - 1); map.clear();// 这里要清空，下一步以下一个点为起始点计算。 } return res; }
Python：
def numberOfBoomerangs(self, points: List[List[int]]) -> int: res = 0 for point1 in points:# 以其中一个点为起始点，计算到其他所有点的距离。 cnt = Counter() for point2 in points: dis = dist(point1, point2) cnt[dis] += 1 for val in cnt.values(): res += val * (val - 1) return res笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴