前往
大廳
主題

LeetCode - 447. Number of Boomerangs 解題心得

Not In My Back Yard | 2020-10-23 19:39:55 | 巴幣 0 | 人氣 223

題目連結:


題目意譯:
給定 n 個平面上的相異點。一個「迴力鏢」被定為一個多元組 (i, j, k) 滿足點 i 到點 j 的距離等於點 j 到點 k 的距離(多元組的次序有影響)

找到迴力鏢的個數。你可以假設 n 不超過 500 ,且每個點的座標值皆位於 [-10000, 10000] 的範圍(含左、右端點)之中。



範例測資:
輸入:
[[0,0],[1,0],[2,0]]
輸出:
2
解釋:
兩個迴力鏢分別為 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]。


解題思維:
窮舉所有的開頭點 i,接著對於每個 i 值再窮舉所有可能的中繼點 j。對於每對點 (i, j) 求出兩點的距離,並統計每個距離值的出現次數(可以用雜湊表(Hash Table)去統計)。

接著對於開頭點 i 下得出的所有可能距離值之數目 C ,將所求的迴力鏢數目加上 C × (C - 1) (因為點 j 到點 k 的距離也要一樣)。

窮舉完所有點 i 之後,最後的回力鏢數目即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作