1232. Check If It Is a Straight Line

yPhantom 2019年10月20日 106次浏览

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Example 1:

img

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false

Example 2:

img

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates contains no duplicate point.

Constraints:

  • 2 <= coordinates.length <= 1000
  • coordinates[i].length == 2
  • -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
  • coordinates contains no duplicate point.

Solution

题意是给定一个坐标数组,判断数组中的坐标是否在一条直线上。

这个很简单,先根据前两个点算出斜率,然后从第二个点开始遍历算斜率即可,初步解法:

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        if (coordinates.length  < 2) {
            return coordinates.length > 0;
        }
        int[] pointA = coordinates[0];
        int[] pointB = coordinates[1];
        
        float k = (float)(pointB[1] - pointA[1]) / (pointB[0] - pointA[0]);
        
        for (int i = 2; i < coordinates.length; i++) {
            int[] p = coordinates[i];
            if (Math.abs((float)(p[1] - pointA[1]) / (p[0] - pointA[0]) - k) > 0.001) {
                return false;
            }
        }
        return true;
    }
}

但是这个方法感觉不够简洁,看了一下DISCUSS,可以利用相似三角形的原理。假设3个点A,B,C在一条直线上,那么有

因此代码可以写的更简洁:

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int p = coordinates[0][0], q = coordinates[0][1], u = coordinates[1][0], v = coordinates[1][1];
        for (int[] c : coordinates) {
            if ((c[0] - p) * (c[1] - v) != (c[0] - u) * (c[1] - q)) 
                 return false;    
        }
        return true;
    }
}