缀点成线

发表于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

LeetCode每日一题，1232. Check If It Is a Straight Line

先看题目描述

srO9sS.png

大意就是给定一个数组，里面存储着二维点的坐标，让我们判断这些点连起来是否是一条直线

算法和思路

这题的思路很简单，如果三点A(x1，y1)，B(x2，y2)，C(x3，y3) 处在一条直线上，那么必然满足(y2 - y1) / (x2 - x1) = (y3 - y2) / (x3 - x2)，我们就按照此思路一个个计算即可

算法源码

除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int len = coordinates.length;
        int preX = coordinates[1][0];
        int preY = coordinates[1][1];
        int flag = coordinates[1][0] - coordinates[0][0];
        if (flag == 0) {
            for (int i = 2; i < len; i++) {
                int x = coordinates[i][0];
                int y = coordinates[i][1];
                if (x != preX) {
                    return false;
                }
            }
        } else {
            double k = (double)(coordinates[1][1] - coordinates[0][1]) / (coordinates[1][0] - coordinates[0][0]);
            for (int i = 2; i < len; i++) {
                int x = coordinates[i][0];
                int y = coordinates[i][1];
                if ((double)(y - preY) / (x - preX) != k) {
                    return false;
                }
                preX = x;
                preY = y;
            }
        }
        return true;
    }
}

上面的代码是最开始实现的代码，但不推荐该实现，因为除法存在除 0 和精度的问题，而且乘法的开销远小于除法，所以我们应将除法实现改为用乘法实现，即判断 (y2 - y1) * (x3 - x2) = (y3 - y2) * (x2 - x1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int len = coordinates.length;
        for (int i = 1; i < len - 1; i++) {
            int res1 = (coordinates[i][1] - coordinates[i - 1][1]) * (coordinates[i + 1][0] - coordinates[i][0]);
            int res2 = (coordinates[i][0] - coordinates[i - 1][0]) * (coordinates[i + 1][1] - coordinates[i][1]);
            if (res1 != res2) {
                return false;
            }
        }
        return true;
    }
}