LeetCode 1232. Check If It Is a

@(LeetCode)

问题描述

给定一个坐标点数组，每个坐标点表示为：coordinates[i] = [x, y]，其中 [x, y] 代表点的坐标。检查这些点是否在一条直线上。

栗 1：

image.png

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

栗 2：

image.png

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

注意：

• 2 <= coordinates.length <= 1000。
• coordinates[i].length == 2。
• -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4。
• coordinates 中没有重复的点。

想看英文原文的戳这里。

解题思路

这是一道灰常简单的题目，有相关数学知识即可。

如果一些点在一条直线上，那么任意两点组成线段的斜率相同。

因此，可将题目转换为：计算两点之间的斜率，与初始斜率做比较，判定条件如下。

• 若不等，则不在一条直线；
• 若所有的点都相等，则在一条直线上。

而两个点的选择，只需从头遍历点即可。

比如 [x0, y0], [x1, y1], [x2, y2] 三点之间的比较如下：

// 除法比较
(y1 - y0) / (x1 - x0) = (y2 - y1) / (x2 - x1)

若采用上面除法的方式比较斜率，则需要注意浮点数相等的比较。不过也可换一种方式，采用乘法来比较，如下所示。

// 转换为乘法
(y1 - y0) * (x2 - x1) = (y2 - y1) * (x1 - x0)

js 代码：

var checkStraightLine = function (coordinates) {
  if (coordinates && coordinates.length > 0) {
    let i = 0
    
    // 记录初始斜率
    let ratio = -1

    while (i < coordinates.length - 1) {
      const point1 = coordinates[i]
      const point2 = coordinates[i + 1]

      const xDistance = point2[0] - point1[0]
      const yDistance = (point2[1] - point1[1])
      
      if (xDistance === 0) {
          return false
      }

      // 计算当前斜率
      const curRatio = yDistance / xDistance

      // 更新初始斜率
      if (ratio === -1) {
        ratio = curRatio
      }

      // 比较斜率，注意小数的比较
      if (Math.abs(curRatio - ratio) >= 1e-6) {
        return false
      }

      i += 1
    }

    return true
  }

  return false
};

完整代码可点此查看。