LeetCode.1037-有效的回旋镖(Valid Boomerang)

這是小川的第387次更新，第416篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第248題（順位題号是1037）。回旋镖是一組各不相同且不在一條直線上的三個點。給出三個點的清單，判斷這些點是否是回旋镖。

例如：

輸入：[[1,1]，[2,3]，[3,2]]

輸出：true

輸入：[[1,1]，[2,2]，[3,3]]

輸出：false

注意：

• points.length == 3
• points[i].length == 2
• 0 <= points[i][j] <= 100

02 第一種解法

要判斷三個點是否能構成回旋镖，一是三個點各不相同，二是不能在一條直線上，即二維數組中三對坐标兩兩值不相等，且任意兩對坐标的斜率不能相等。直接将題目的意思翻譯過來即可，但是在計算兩點的斜率時，如果分母為0或者分子為0，即這兩個點可能與

x

軸、

y

軸平行，需要傳回

false

。另外算斜率要用

double

類型，不能用

int

類型。

public boolean isBoomerang(int[][] points) {
    int x1 = points[0][0], x2 = points[1][0], x3 = points[2][0];
    int y1 = points[0][1], y2 = points[1][1], y3 = points[2][1];
    // 坐标兩兩不等
    if ((x1 == x2 && y1 == y2) || (x2==x3 && y2==y3) || (x1==x3 && y1==y3)) {
        return false;
    }
    // 不能和x軸、y軸平行
    if ((x1 == x2 && x2 == x3) || (y1 == y2 && y2 == y3)) {
        return false;
    }
    // 計算斜率
    double slope = (y2-y1)/((double)x2-x1);
    double slope2 = (y3-y2)/((double)x3-x2);
    return slope != slope2;      
}
           

03 第二種解法

還可以從另外的角度來看，依舊是數學角度，根據題目給的回旋镖定義，要是三個點能夠組成一個回旋镖，那麼三個點合成的區域一定是一個三角形。那麼我們可以計算出三條邊的長度，用三角形的定義來判斷三條邊能否組成一個三角形。

public boolean isBoomerang2(int[][] points) {
    int x1 = points[0][0], x2 = points[1][0], x3 = points[2][0];
    int y1 = points[0][1], y2 = points[1][1], y3 = points[2][1];
    // 計算三邊的長度
    double a = Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    double b = Math.sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
    double c = Math.sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
    boolean flag = a+b>c && a+c>b && b+c>a;
    boolean flag2 = a-b<c && a-c<b && b-c<a;
    return  flag && flag2;
}
           

04 小結

算法專題目前已連續日更超過七個月，算法題文章254+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！