未分類

Number of Boomerangs

Go, HashTable, LeetCode

Number of Boomerangs

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).

For Example:

1
2
3
4
5
6
7
8
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]]
提示 解題應用
HashTable HashMap

Default:

1
2
3
func numberOfBoomerangs(points [][]int) int {
}

解答思路:

一平台上有數個坐標，找出以一點為中心到另外兩點的距離相等的數組共有幾組，其中另外兩點的距離是多少無所謂，只需關心與中心點的距離即可，盲點在於從座標上來看若有一中心點到另外兩點的距離相等，這是為一組情形，但在資料的結果上為[center,pointA,pointB],[center,pointerB,pointerA]將其當作兩種結果，而本題要求的就是為後者的情況，所以對中心點之外的座標要做排列組合，不過因為我們關心的為”距離”而非哪一點，此外儲存距離也比儲存兩點之間的關係容易多，所以就用hashmap儲存中心點到其餘所有點的距離及該距離有多少個，再來只要針對距離的個數有多少個做排序組合後(道理與座標是相同)，全部總合起來就是我們要的答案。

程式碼解說:

一開始先初始化一hashmap，其中key儲存距離長度，而value則是中心到點有多少條同樣距離長度的線，再來就分別用一巢狀迴圈從同一陣列取出中心點與另一點座標，如果中心點與另一座標相同就再拿下一個座標，
接著就開始計算中心點到該點之間的距離，x間距的平方加上y間距的平方，不過我們不需要開根號，畢竟主要只是要找出相同距離及其數量，而在找出一中心點與其餘座標的所有距離後，對所有距離做排列組合，不同座標間的組合公式為n*(n-1)，並將數量加至結果，最後在中心座標換下一個之前，將hashmap給重置以重新再次儲存中心點與座標點間的距離

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var x int
var y int
var distance int
var result int
hashMap := make(map[int]int)
for i, center := range points {
	for j, point := range points {
		if i == j {
			continue
		}
		x = center[0] - point[0]
		y = center[1] - point[1]
		distance = x*x + y*y
		hashMap[distance]++
	}
	for _, value := range hashMap {
		result += value * (value - 1)
	}
	hashMap = make(map[int]int)
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func numberOfBoomerangs(points [][]int) int {
	var x int
	var y int
	var distance int
	var result int
	hashMap := make(map[int]int)
	for i, center := range points {
		for j, point := range points {
			if i == j {
				continue
			}
			x = center[0] - point[0]
			y = center[1] - point[1]
			distance = x*x + y*y
			hashMap[distance]++
		}
		for _, value := range hashMap {
			result += value * (value - 1)
		}
		hashMap = make(map[int]int)
	}
	return result
}

總結:

一平台上有數個坐標，找出以一點為中心到另外兩點的距離相等的數組共有幾組，對中心點之外的座標做排列組合，以hashmap儲存中心點到其餘所有點的距離及該距離有多少個，再來只要針對距離的個數有多少個做排序組合後(道理與座標是相同)，全部總合起來就是我們要的答案。

分享到