Leetcode-1232-缀点成线

思路：深度优先遍历/DFS

题目描述

• 在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。

• 请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。

示例1：

输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

示例 2：

输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

思路 ： 数学直线知识

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        // 1. 将所有点向(-deltax,-deltay) 方向进行平移 : 第一个点就移到了原点
        int deltaX = coordinates[0][0];
        int deltaY = coordinates[0][1];
        int n = coordinates.length;
        for(int i = 0;i < n;i++){
            coordinates[i][0] -= deltaX;
            coordinates[i][1] -= deltaY;
        }

        // 2. 两点确定一条直线 设直线方程为 Ax + By = 0 带入(-deltax_1,-deltay_1)坐标
        int A = coordinates[1][1];
        int B = -coordinates[1][0];
        
        // 3. 判断从原点和第一个点以外的所有点是否在这条直线上
        for(int i = 2;i < n;i++){
            int x = coordinates[i][0];			// 每个点的横坐标
            int y = coordinates[i][1];			// 每个点的纵坐标
            if(A * x + B * y != 0){             // 说明不在直线上
                return false;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组中的元素数量。
• 时间复杂度：O(1)

打赏