算法-数学-斜率-直线上最多的点数
算法-数学-斜率-直线上最多的点数
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/max-points-on-a-line/
1.2 题目描述
给你一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。


2 暴力搜索斜率相同点
2.1 思路
遍历所有节点,比较斜率,如果斜率相同就统计,最后返回最大统计数。
2.2 代码
class Solution {public int maxPoints(int[][] points) {int result = 1;for (int i = 0; i < points.length; i++) {int[] first = points[i];for (int j = i + 1; j < points.length; j++) {int[] second = points[j];// 只要到这里,说明至少有两个点// 两个点就能构成一条直线,所以至少是2// 这里相当于是i和j确定了一条直线,继续统计经过这条直线上的点数int cnt = 2;for (int k = j + 1; k < points.length; k++) {int[] third = points[k];// 计算斜率 (y1 - y0) / (x1 - x0) 是否相等// 因为涉及除不尽的情况,所以交还两边的除数来相乘int k1 = (second[0] - first[0]) * (third[1] - second[1]);int k2 = (third[0] - second[0]) * (second[1] - first[1]);if (k1 == k2) {cnt++;}}result = Math.max(result, cnt);}}return result;}
}
2.3 时间复杂度

O(N^3)
2.4 空间复杂度
O(1)
3 Hash表法
3.1 思路
3.2 代码
class Solution {public int maxPoints(int[][] ps) {int n = ps.length;int result = 1;for (int i = 0; i < n; i++) {Map<String, Integer> map = new HashMap<>();// 经过当前点 i 的直线所经过的最多点数量int max = 0;for (int j = i + 1; j < n; j++) {int x1 = ps[i][0], y1 = ps[i][1];int x2 = ps[j][0], y2 = ps[j][1];// 斜率可能除不尽,所以换一个方式存储int a = x1 - x2, b = y1 - y2;// 公约数int k = gcd(a, b);// 将分子分母公约后存储String key = (a / k) + "_" + (b / k);// 记录斜率的点数map.put(key, map.getOrDefault(key, 1) + 1);// 更新经过当前点的直线的最大点数// 即比较所有经过当前点的直线上的点数,取最大者max = Math.max(max, map.get(key));}// 更新结果result = Math.max(result, max);}return result;}// 求公约数int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
}
3.3 时间复杂度


3.4 空间复杂度
O(N)
参考
- https://leetcode.cn/problems/max-points-on-a-line/solutions/842114/zhi-xian-shang-zui-duo-de-dian-shu-by-le-tq8f/
- https://leetcode.cn/problems/max-points-on-a-line/solutions/842391/gong-shui-san-xie-liang-chong-mei-ju-zhi-u44s/
相关文章:
算法-数学-斜率-直线上最多的点数
算法-数学-斜率-直线上最多的点数 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/max-points-on-a-line/ 1.2 题目描述 给你一个数组 points ,其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 2 暴力搜索斜率…...
项目进展(五)-修复PCB电路板,学习32位ADC芯片ADS1285
一、前言 上个月29号放假了,和朋友一起去了南京(人是真滴多),师兄晚放假几天,结果在测试时不小心把12V和GND碰触到一起了,导致12V短路,电路板几乎瘫痪了。 今天下午到学校之后就开始着手寻找问题和修复,最…...
(三) Markdown插入互联网或本地视频解决方案
前言 不论博客系统是WordPress还是Typecho,绕不开的是两种书写语言,一种称之为富文本,一种叫做Markdown。 Markdown有很多好处,也有很多坏处,比如Markdown本身不具备段落居中的功能,以及Markdown也不具有…...
HPA (Horizontal Pod Autoscaler) In K8s
城市红绿灯智能调节 没准正在建设中哈哈哈 作为一位城市观察者和设计师,我想借助Kubernetes的HPA机制思想来描述城市红绿灯自动调节的场景。 在这个故事中,我们的城市面临着日益增长的交通流量和挤塞问题。为了应对这一挑战,城市决定引入智能…...
Ubuntu安装samba服务器
为了window系统下能够像访问本地目录一样访问ubuntu系统下的目录,这里我通过安装samba服务器,将ubuntu系统的文件目录通过网络挂载的方式共享出来,以便在window下就能够对ubuntu系统的文件进行读写等访问操作,这里记录一下samba服…...
[SpringBoot] 8. aop 获取 request response
最近开发有一个需求需要在 aop 中获取request response ,搜索许久没有答案,故此记录📝~ aop 获取 package com.example.easy_im.aop;import com.example.easy_im.Context; import jakarta.servlet.http.HttpServletRequest; impo…...
同学苹果ios的ipa文件应用企业代签选择签名商看看这篇文章你再去吧
同学我们要知道随着互联网的发展,苹果应用市场的火爆,越来越多的开发者加入到苹果应用开发行业中来。同时,苹果应用市场上的应用也在不断增多,用户数量也在不断增加,苹果应用代签是指通过第三方公司为开发者的应用进行…...
【PyCharm Community Edition】:excel操作
Excel操作 相关模块openpyxlxlrdshutil 实例 相关模块 openpyxl 可以对.xlsx,.xlsm,.xltx,.xltm文件格式操作 打开文件:wb_xlsx openpyxl.load_workbook(“文件名”)新建文件:wb_xlsx openpyxl.Workbook()新建sheet表:wb_xlsx_sheet wb…...
证书显示未受信任,生成的证书过期
此时若是导入证书后,证书显示未受信任,则说明我们缺失最新的AppleWWDRCA证书 解决方案: 重新下载AppleWWDRCA并安装。即下载最新的AppleWWDRCA证书,双击安装到“登录”项的钥匙串下;然后再安装你的开发证书或者发布证书…...
VS+Qt+C++ GDAL读取tif图像数据显示
程序示例精选 VSQtC GDAL读取tif图像数据显示 如需安装运行环境或远程调试,见文章底部个人QQ名片,由专业技术人员远程协助! 前言 这篇博客针对《VSQtC GDAL读取tif图像数据显示》编写代码,代码整洁,规则,…...
CSS 选择器-认识并应用选择器
CSS选择器是用来定位HTML或XML文档中的元素的模式。以下是一些常见的CSS选择器,以及对应的样例代码: 标签选择器:选择所有指定标签的元素。 示例代码: p {font-size: 16px; }类选择器:选择所有指定类名的元素。 示…...
【教程】Autojs使用OpenCV进行SIFT/BRISK等算法进行图像匹配
转载请注明出处:小锋学长生活大爆炸[xfxuezhang.cn] 此代码可以替代内置的images.findImage函数使用,但可能会误匹配,如果是对匹配结果要求比较高的,还是得谨慎使用。 runtime.images.initOpenCvIfNeeded(); importClass(java.uti…...
[庆国庆 迎国庆 发文]云计算的概念
庆国庆 迎国庆 国庆发文100%可得专属勋章 一年仅有一次哦 不要错过啦 去发布 https://activity.csdn.net/creatActivity?id10567&spm1011.2480.3001.6900 https://mp.csdn.net/edit?activity_id10567&spm1057.2600.3001.9674 云计算(cloud computing&…...
计算机网络-计算机网络体系结构-概述,模型
目录 一、计算机网络概述 二、性能指标 速率 带宽 吞吐量 时延 往返时延RTT 利用率 三、计算机网络体系结构 分层结构 IOS模型 应用层-> 表示层-> 会话层-> 传输层-> 网络层-> 数据链路层-> 物理层-> TCP/IP模型 一、计算机网络概述 计…...
对示例程序spinner_asyncio.py进行修改使其能运行
学习《流畅的python》第18章 使用asyncio包处理并发,运行示例18-2 spinner_asyncio.py的时候,程序报错如下: D:\fluentPy\chapter17>python spinner_asyncio.py File "D:\fluentPy\chapter17\spinner_asyncio.py", line 30 …...
Linux命令(93)之head
linux命令之head 1.head介绍 linux命令head用来查看文件的前N行内容;默认head查看前10行 2.head用法 head [参数] 文件 head常用参数 参数说明-n从头显示N行,默认显示10行,可以不写-q隐藏文件名,在查看两个及以上文件名的情况…...
使用Visual Studio调试排查Windows系统程序audiodg.exe频繁弹出报错
VC常用功能开发汇总(专栏文章列表,欢迎订阅,持续更新...)https://blog.csdn.net/chenlycly/article/details/124272585C软件异常排查从入门到精通系列教程(专栏文章列表,欢迎订阅,持续更新...&a…...
WebSocket实战之六心跳重连机制
一、前言 WebSocket应用部署到生产环境,我们除了会碰到因为经过代理服务器无法连接的问题(注:该问题可以通过搭建WSS来解决,具体配置请看 WebSocket实战之四WSS配置 ),另外一个问题就是外网环境不稳定经常…...
Webpack 基础入门以及接入 CSS、Typescript、Babel
一、什么是 Webpack Webpack 是一款 JS 模块化开发的技术框架,其运作原理是将多个 JS 文件关联起来构成可运行的应用程序。 Webpack 拥有丰富的 plugins / loaders 插件生态圈,可以让 js 识别不同的语言如 .css, .scss, .sass, .json, .xml, .ts, .vue…...
postgresql-自增字段
postgresql-自增字段 标识列IdentitySerial类型Sequence序列 标识列Identity -- 测试表 create table t_user( -- 标识列自增字段user_id integer generated always as identity primary key,user_name varchar(50) not null unique );-- 自动生成序列 CREATE SEQUENCE public…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
