專欄：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算法文檔 。