LeetCode 1232. Check If It Is a Straight Line

关注

发布于: 2020 年 05 月 10 日

LeetCode 1232. Check If It Is a Straight Line

﻿
@(LeetCode)
问题描述给定一个坐标点数组，每个坐标点表示为：coordinates[i] = [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]]
返回：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
};
﻿
完整代码可点此查看。
﻿
本文同步发表在简书，https://www.jianshu.com/p/0da2e288bf25。