当前位置: 首页 > news >正文

149. 直线上最多的点数

149. 直线上最多的点数

class MaxPoints:"""149. 直线上最多的点数https://leetcode.cn/problems/max-points-on-a-line/description/?envType=study-plan-v2&envId=top-interview-150"""def solution(self, points: List[List[int]]) -> int:"""时间复杂度 O(n^2 * log n)空间复杂度 O(log n):param points: :return: """n = len(points)if n <= 2:return nans = 0for i in range(n):if ans >= n - i or ans > n // 2:breakhm = dict()for j in range(i + 1, n):x = points[i][0] - points[j][0]y = points[i][1] - points[j][1]if x == 0:y = 1elif y == 0:x = 1else:if y < 0:x = -xy = -ygcd_xy = self.gcd(abs(x), abs(y))x /= gcd_xyy /= gcd_xy# 将x缩放20001倍,可以理解为原本相邻x1,x2的距离由 1 放大至 20001,这样 无论y取任何[0, 2×10^4]中的值,# 都可以映射到这个间隔内,保证了任意两组数(x1,y1)和 (x2,y2),只要有一个值(x1 != x2 或 y1 != y2)不同,# 那映射后的val1 和 val2 也不同val = y + x * 20001hm[val] = hm.get(val, 0) + 1max_n = 0for k, v in hm.items():max_n = max(max_n, v + 1)ans = max(ans, max_n)return ansdef gcd(self, a, b):"""求a和b的最大公约数,时间复杂度 log n:param a::param b::return:"""if b == 0:return areturn self.gcd(b, a % b)

相关文章:

149. 直线上最多的点数

149. 直线上最多的点数 class MaxPoints:"""149. 直线上最多的点数https://leetcode.cn/problems/max-points-on-a-line/description/?envTypestudy-plan-v2&envIdtop-interview-150"""def solution(self, points: List[List[int]]) ->…...

不合格机器人工程讲师再读《悉达多》-2024-

一次又一次失败的经历&#xff0c;让我对经典书籍的认同感越来越多&#xff0c;越来越觉得原来的自己是多么多么的无知和愚昧。 ----zhangrelay 唯物也好&#xff0c;唯心也罢&#xff0c;我们都要先热爱这个世界&#xff0c;然后才能在其中找到自己所热爱的事业。 ----zh…...

【STM32CubeMX串口通信详解】USART2 -- DMA发送 + DMA空闲中断 接收不定长数据

&#xff08; 本篇正在编写、更新状态中.....) 文章目录&#xff1a; 前言 前言 本篇&#xff0c;详细地用截图解释 CubeMX 对 USART2 的配置&#xff0c;HAL函数使用&#xff0c;和收发程序的编写。 收、发机制&#xff1a;DMA发送 DAM空闲中断接收。 DMA空…...

Webpack5入门到原理19:React 脚手架搭建

开发模式配置 // webpack.dev.js const path require("path"); const ESLintWebpackPlugin require("eslint-webpack-plugin"); const HtmlWebpackPlugin require("html-webpack-plugin"); const ReactRefreshWebpackPlugin require("…...

苹果眼镜(Vision Pro)的开发者指南(6)-实战应用场景开发 - 游戏、协作、空间音频、WebXR

第一部分:【构建游戏和媒体体验】 了解如何使用visionOS在游戏和媒体体验中创建真正身临其境的时刻。游戏和媒体可以利用全方位的沉浸感来讲述令人难以置信的故事,并以一种新的方式与人们联系。将向你展示可供你入门的visionOS游戏和叙事开发途径。了解如何使用RealityKit有…...

flutter底层架构初探

本文出处&#xff1a;​​​​​​​​​​​​​Flutter 中文开发者网站 架构 embedder嵌入层 提供程序入口&#xff08;其他原生应用也采用此方式&#xff09;&#xff0c;程序由此和底层操作系统协调&#xff08;surface渲染、辅助功能和输入服务&#xff0c;管理事件循环…...

初识SQL注入

目录 注入攻击 SQL注入 手工注入 Information_schema数据库 自动注入 介绍一下这款工具&#xff1a;sqlmap 半自动注入 前面给大家通过学习练习的方式将XSS攻击的几种形式和一些简单的靶场和例题的演示&#xff0c;从本篇开始我将和小伙伴们通过边复习、边练习的方式来进…...

React初探:从环境搭建到Hooks应用全解析

React初探&#xff1a;从环境搭建到Hooks应用全解析 一、React介绍 1、React是什么 React是由Facebook开发的一款用于构建用户界面的JavaScript库。它主要用于构建单页面应用中的UI组件&#xff0c;通过组件化的方式让开发者能够更轻松地构建可维护且高效的用户界面。 Reac…...

设计模式——1_6 代理(Proxy)

诗有可解不可解&#xff0c;若镜花水月勿泥其迹可也 —— 谢榛 文章目录 定义图纸一个例子&#xff1a;图片搜索器图片加载搜索器直接在Image添加组合他们 各种各样的代理远程代理&#xff1a;镜中月&#xff0c;水中花保护代理&#xff1a;对象也该有隐私引用代理&#xff1a;…...

性能优化(CPU优化技术)-NEON 介绍

「发表于知乎专栏《移动端算法优化》」 本节主要介绍基本 SIMD 及其他的指令流与数据流的处理方式&#xff0c;NEON 的基本原理、指令以及与其他平台及硬件的对比。 &#x1f3ac;个人简介&#xff1a;一个全栈工程师的升级之路&#xff01; &#x1f4cb;个人专栏&#xff1a;…...

Kafka-服务端-KafkaController

Broker能够处理来自KafkaController的LeaderAndIsrRequest、StopReplicaRequest、UpdateMetadataRequest等请求。 在Kafka集群的多个Broker中&#xff0c;有一个Broker会被选举为Controller Leader,负责管理整个集群中所有的分区和副本的状态。 例如&#xff1a;当某分区的Le…...

ffmpeg使用手册

ffmpeg使用手册 文章目录 ffmpeg使用手册ffmpeg是什么指令总结1.查看ffmpeg版本2.mkv转mp43.裁剪 .mkv 视频4.不调节帧率&#xff0c;尽可能保证原视频质量的情况下将原始视频压缩4.1 crf4.2 preset 5.调节视频帧率6.调节帧率&#xff0c;尽可能保证原视频质量的情况下将原始视…...

操作系统导论-课后作业-ch15

对应异步社区资源HW-Relocation&#xff1a; 1. 种子1运行结果&#xff1a; 种子2运行结果&#xff1a; 种子3运行结果&#xff1a; 2. 需要将界限设置为930&#xff0c;结果如下&#xff1a; 3. 有人说原书翻译有误&#xff0c;原文如下所示&#xff1a; 原文翻译如…...

宝塔面板SRS音视频TRC服务器启动失败

首先&#xff0c;查找原因 1.先看srs服务在哪 find / -type f -name srs 2>/dev/null运行结果&#xff1a; /var/lib/docker/overlay2/5347867cc0ffed43f1ae24eba609637bfa3cc7cf5f8c660976d2286fa6a88d2b/diff/usr/local/srs/objs/srs /var/lib/docker/overlay2/5347867…...

04-Seata修改通信端口

基于docker环境部署下&#xff0c;可以翻看专栏之前的文章 配置文件 /home/server/seata/resources/application.yml 默认${server.port} 1000 1、修改服务端(TC)配置 seata:server:service-port: 7090 2、修改映射端口 在启动脚本中修改映射端口 docker run -id --nam…...

活动回顾丨云原生技术实践营上海站「云原生 AI 大数据」专场(附 PPT)

AI 势不可挡&#xff0c;“智算”赋能未来。2024 年 1 月 5 日&#xff0c;云原生技术实践营「云原生 AI &大数据」专场在上海落幕。活动聚焦容器、可观测、微服务产品技术领域&#xff0c;以云原生 AI 工程化落地为主要方向&#xff0c;希望帮助企业和开发者更快、更高效地…...

【数据结构与算法】4.自主实现单链表的增删查改

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更新的动力❤️ &#x1f64f;小杨水平有限&#xff0c;欢迎各位大佬指点&…...

Linux系统常用命令行指令

Linux系统是一种常用于开源项目开发的生产环境&#xff0c;因其免费、开源、安全、稳定的特点被广泛应用于手机、平板电脑、路由器、电视和电子游戏机等嵌入式系统中&#xff0c;能够更加简便地让用户知道系统是怎样工作的。前几日我安装好了Red Hat Enterprise Linux 9.0&…...

java SSM园林绿化管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM园林绿化管理系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代 码和数据库&#xff0c;系统主要采…...

【issue-halcon例程学习】edges_color.hdev

例程功能 演示如何使用edges_color&#xff0c;展示只能从彩色图像中提取某些边缘的图像&#xff0c;说明edges_color和edges_image输出之间的差异。 代码如下 dev_update_off () read_image (Image, olympic_stadium) get_image_size (Image, Width, Height) dev_close_wind…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...