<noframes id="0eeke"></noframes>

Leetcode 447. Number of Boomerangs

周國輝發布于2019-08-14 17:16 / 1665人閱讀

摘要：所以給定一個點的數組，要依次選擇每個點當做第一個點，依次求出它跟其他點的距離，如果相等則給結果加一，最后返回總數。數據結構去存儲距離和這個距離出現的次數。代碼滿足條件的點的排列組合結果數

題目：

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).
Example: 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]]

解法：

這道題主要條件是計算三點中第一個點到第二個點的距離和第一個點到第三個點的距離是否相等，因為順序有關，所以要返回到底有多少排列滿足這個條件。所以給定一個點的數組，
要依次選擇每個點當做第一個點，依次求出它跟其他點的距離，如果相等則給結果加一，最后返回總數。

數據結構：

HashMap去存儲距離和這個距離出現的次數。

代碼：

public int numberOfBoomerangs(int[][] points){
    int result = 0;
    HashMap() map= new HashMap<>();
    for(int i = 0; i < points.length; i++){
        for(int j = 0; j < points.length; j++){
            if(i == j) continue;
            int distance = getDistance(points[i],points[j]);
            map.put(distance, map.getOrDefault(distance,0)+1);
        }
        for(int val : map.values()){
            result += val*(val-1); //滿足條件的點的排列組合結果數
        }
        map.clear();
    }

    return result;
}

public int getDistance(int[] point1, int[] point2){
    int x = point1[0] - point2[0];
    int y = point1[1] - point2[1];
    return x*x + y*y;
}

云服務器 GPU云服務器 Boomerangs LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66529.html

447. Number of Boomerangs

摘要：題目鏈接遍歷每個，然后找和它等距離的其他，按距離來保存，比如有一個點，和它距離都是的點有，，，那么一共的組合就有種，包括。這么算是不考重復的情況下。還有可能坐標完全相同，那么和會被當成兩個點算兩次。 447. Number of Boomerangs 題目鏈接：https://leetcode.com/problems... 遍歷每個point，然后找和它等距離的其他point，按距離...

baukh789 2019-08-14 17:28 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode[191] Number of 1 Bits

摘要：依次移位復雜度思路依次移動位數進行計算。代碼利用性質復雜度，思路代碼 LeetCode[191] Number of 1 Bits Write a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Fo...

Scliang 2019-08-14 15:00 評論0 收藏0