1. 首页

LeetCode 149. 直线上最多的点数

题目描述

难度:Hard

相关话题:哈希表数学

给定一个二维平面,平面上有n 个点,求最多有多少个点在同一条直线上。

示例 1:

输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
|    o
|   o
| o
+------------->
0 1 2 3  4

示例2:

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
|  o
| o      o
|    o
| o       o
+------------------->
0 1 2 3 4 5 6

思路:

原理:两点确定一条直线。

  1. 确定第一个点。
  2. 确定第二个点,如果第二个点和第一个点相同,则继续选择下一个第二个点。

    注意:

    • 相同的时候,count++也要执行。
  3. 根据前面亮点的dx=p2.x-p1.xdy=p2.y-p1.y,确定后续的其他点。

    注意:

    • 当存在dx===0或者dy===0,直接判断p3.x-p1.x或者p3.y-p1.y是否为0
/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * Definition for a point.
 * function Point(x, y) {
 *     this.x = x;
 *     this.y = y;
 * }
 */
/**
 * @param {Point[]} points
 * @return {number}
 */
var maxPoints = function(points) {
  let maxLen=0
  for(let i=0;i<points.length;i++){
    // 确定第一个点
    let first=points[i]
    let count=1
    // if(maxLen===0)maxLen=1
    for(let j=0;j<points.length;j++){
      if(i===j)continue
      count++
      // 确定第二个点,如果第二个点和第一个点相同,则继续选择下一个第二个点
      let sec=points[j]
      let dx=sec.x-first.x,dy=sec.y-first.y
      if(dx===0 && dy===0)continue
      for(let k=j+1;k<points.length;k++){
        // 通过前面2个点的间隔,筛选后面的点
        if(k===i)continue
        let o=points[k]
        let deltX=o.x-first.x,
            deltY=o.y-first.y
        if(dx===0 && deltX===0)count++
        else if(dy===0 && deltY===0)count++
        else if(deltX/deltY===dx/dy)count++
      }
      maxLen=Math.max(maxLen,count)
      count=1
    }
    maxLen=Math.max(maxLen,count)
  }
  return maxLen
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 149. 直线上最多的点数

链接:https://www.javascriptc.com/4514.html

« 如何安全地使用 React context
IDEA超好用插件»
Flutter 中文教程资源

相关推荐

QR code