专栏首页江涛的博客leetcode - 缀点成线

leetcode - 缀点成线

题意

在一个 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

提示

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

出处

链接:https://leetcode-cn.com/problems/check-if-it-is-a-straight-line

思路

这题考的是数学,初中还是小学我忘了。线性函数可以用f(x) = kx + b来表示,k 为系数,b 为常数。通过相关的推倒,我们可以得到这样一个式子f(x1) - f(x2) = k (x1 - x2).这里如果你写成这样(f(x1) - f(x2)) / (x1 - x2) = k,其实是很危险的,因为x1 - x2有可能为 0. 但是这题我们是要比 k 一不一样啊,怎么办?我在找一个点,把除法转换成乘法,即判断d1 * x2 === d2 * x1, 嗯,其实就是在考斜率。

代码

/**
 * @param {number[][]} coordinates
 * @return {boolean}
 */
const checkStraightLine = function (coordinates) {
  const len = coordinates.length;
  if (len === 2) {
    return true;
  }
  const x1 = coordinates[1][0] - coordinates[0][0];
  const y1 = coordinates[1][1] - coordinates[0][1];
  for (let i = 0; i < len; i++) {
    const x2 = coordinates[i][0] - coordinates[0][0];
    const y2 = coordinates[i][1] - coordinates[0][1];
    if (x1 * y2 !== x2 * y1) {
      return false;
    }
  }
  return true;
};

export default checkStraightLine;

测试

import checkStraightLine from '../../code/leetcode/1232';

describe('test function checkStraightLine: ', () => {
  test('test case coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]', () => {
    const res = checkStraightLine([
      [1, 2],
      [2, 3],
      [3, 4],
      [4, 5],
      [5, 6],
      [6, 7],
    ]);
    expect(res).toBe(true);
  });
  test('test case coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]', () => {
    const res = checkStraightLine([
      [1, 1],
      [2, 2],
      [3, 4],
      [4, 5],
      [5, 6],
      [7, 7],
    ]);
    expect(res).toBe(false);
  });
  test('test case coordinates = [[1,2],[2,3],[3,5]]', () => {
    const res = checkStraightLine([
      [1, 2],
      [2, 3],
      [3, 5],
    ]);
    expect(res).toBe(false);
  });
  test('test case coordinates = [[0,0],[0,1],[0,-1]]', () => {
    const res = checkStraightLine([
      [0, 0],
      [0, 1],
      [0, -1],
    ]);
    expect(res).toBe(true);
  });
  test('test case coordinates = [[0,0],[0,5],[5,5],[5,0]]', () => {
    const res = checkStraightLine([
      [0, 0],
      [0, 5],
      [5, 5],
      [5, 0],
    ]);
    expect(res).toBe(false);
  });
});

说明

本文首发于 GitHub 仓库https://github.com/ataola/coding,线上阅读地址:https://zhengjiangtao.cn/coding/,转载请注明出处,谢谢!

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-01-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode:缀点成线

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

    Liusy
  • LeetCode 1232. 缀点成线

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

    Michael阿明
  • leetcode之缀点成线

    code4it
  • leetcode之缀点成线

    code4it
  • 力扣 (LeetCode)-14. 最长公共前缀|刷题打卡

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • 【每日leetcode】47.和为K的子数组

    给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

    一条coding
  • 高级数据结构讲解与案例分析

    然而,仅仅掌握好它们不足以应付大厂的算法面试的。为了达到对时间和空间复杂度的理想要求,本节课探究高级数据结构,它们的实现要比那些常用的数据结构要复杂得多。其中重...

    Lanson
  • 有哪些值得推荐的程序员在线编程网站?

    我知道对于一个新手来说,可能配运行环境要比上手写代码要难受的多。所以我就抽时间整了一些在线编程测试的网站,虽然推荐了这些网站,但是还是推荐大家平时写代码的时候在...

    谭庆波
  • GitHub高星!互联网公司最常见的面试算法题大集合

    LeetCode是一个美国的在线编程网站,收集了各个大厂的笔试面试题,对找工作的毕业生和开发者来说,非常有价值。不过LeetCode上面的题目很多都是考察应聘者...

    新智元
  • 9月技术文章汇总

    Leetcode名企之路
  • LeetCode 例题精讲 | 18 前缀和:空间换时间的技巧

    在设计算法时,时间复杂度始终是我们关注的重点。我们需要让算法的时间复杂度尽可能低,追求运行效率。有些时候,我们可以通过增加空间占用的方式减少算法的运行时间,这便...

    五分钟学算法
  • 算法细节系列(23):回溯

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 力扣(LeetCode)刷题,简单题(第25期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • 前缀树问题-LeetCode 409、412、414、415、419、421

    给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:...

    算法工程师之路
  • GTD践行周报第一期

    给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

    程序员小王
  • Python 求中心索引,第二种方法不可取!

    今天,我们做一道 LeetCode 题目,开启咱们 【算法刷题日记】知识星球的第一道 LeetCode 题。题目的基本类型是 数组,考察点数组的索引、求和等,基...

    double
  • 图解 LeetCode 第 421 题:数组中两个数的最大异或值

    今天分享的题目来源于 LeetCode 第 421 号问题:数组中两个数的最大异或值。在 异或 这个知识点里面属于一个中高难度的题目。

    五分钟学算法
  • Leetcode【61、82、83、142、143、1171】

    1、先计算链表长度 size,k = k % size,如果 k % size == 0,则不用移动,直接返回 head; 2、否则,需要将前 size - ...

    echobingo
  • 数字问题-LeetCode 452、453、454、455、456、459(KMP算法)

    在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。由于它是水平的,所以y坐标并不重要,因此只要知道开始和结束的x坐标...

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券