给定一个整数数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。
示例 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
提示：
2 <= coordinates.length <= 1000coordinates[i].length == 2-104 <= coordinates[i][0], coordinates[i][1] <= 104coordinates中不含重复的点
最开始我想的很简单嘛，单纯的一个数学公式就秒了
class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
int r = (coordinates[0][1] - coordinates[1][1]) / (coordinates[0][0] - coordinates[1][0]);
for(int i=2;i<coordinates.size();i++)if((coordinates[i][1] - coordinates[i-1][1]) / (coordinates[i][0] - coordinates[i-1][0]) != r)return false;
return true;
}
};交上去发现 devide by zero（太经典了）所以得换种思路：
解决除以零（以及整数除法精度丢失）的最佳方法是将除法转换为乘法（交叉相乘）。
斜率公式为：
\frac{y_1 - y_0}{x_1 - x_0} = \frac{y_i - y_0}{x_i - x_0}
转换为乘法形式即可完全避免除法：
(y_1 - y_0) \times (x_i - x_0) = (x_1 - x_0) \times (y_i - y_0)
修改后的代码：
class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
int dx = coordinates[1][0] - coordinates[0][0];
int dy = coordinates[1][1] - coordinates[0][1];
for (int i = 2; i < coordinates.size(); i++) {
int cur_dx = coordinates[i][0] - coordinates[0][0];
int cur_dy = coordinates[i][1] - coordinates[0][1];
// 交叉相乘判断斜率是否相等
if (dy * cur_dx != dx * cur_dy) {
return false;
}
}
return true;
}
};
时间与空间复杂度： 时间复杂度为 O(N)，空间复杂度为 O(1)。
文章评论