歡迎關(guān)注本人博客：云端筑夢(mèng)師
題目:
Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).
題意為假定平面上n個(gè)點(diǎn)兩兩都不同，boomerang解釋為具有這樣性質(zhì)的由點(diǎn)組成的元組(i,j,k)：i到j(luò)的距離等于i到k的距離，順序不同元組就不同俺夕。請(qǐng)找出n個(gè)點(diǎn)中所有的boomerang瞎嬉，返回總數(shù)，n最多為500救巷，且坐標(biāo)范圍在[-10000,10000]之間。點(diǎn)擊這里看原題
例如:
Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
算法:
from collections import defaultdict
class Solution:
def numberOfBoomerangs(self, points):
num=0
for x1,y1 in points:
distance=defaultdict(int)
for x2,y2 in points:
dx=x1-x2
dy=y1-y2
d=dx**2+dy**2
distance[d]+=1
num+=sum(n*(n-1) for n in distance.values())
return num
算法思路是這樣的，每次取一個(gè)點(diǎn)挽懦，算出這個(gè)點(diǎn)與剩下的所有點(diǎn)距離，并用一個(gè)哈希表存起來剃浇，例如巾兆，若有三個(gè)點(diǎn)到這個(gè)點(diǎn)的距離相同，則此距離的鍵值為3虎囚，根據(jù)排列組合的知識(shí)角塑，這三個(gè)點(diǎn)可與取的點(diǎn)組成3*2個(gè)boomerang，以此類推淘讥，直到將points遍歷完圃伶，對(duì)所有的boomerang求和即可。
