LeetCode——3143. 正方形中的最多点数
通过万岁!!!
- 题目:给你一个n*2的数组,然后第i行表示第i个点的坐标,然后还给你了一个字符串s,s[i]则表示第i个点的名称。然后让你找一个中心是(0,0)的正方形,正方形中尽可能包含多的点,但是里面的点的名称不能重复。即所有的点不存在s[i]=s[j]的情况。
- 思路:下面的点我们先都以第一象限来考虑,然后写代码的时候加个绝对值就好了。首先是构建一个map,然后key是名称,value是点的list。如果list的长度大于1,就对list进行排序,排序的规则就是坐标轴(x或者y)最大的那个点在后面,即切比雪夫距离,也就是max(|x|,|y|)。然后我们找正方形边长的一半(这里叫他minWidth)就好了,因为这个list的长度大于1,我们要让正方形尽可能的大,list是排序过的,所以不包含第二点(暂记为(a,b))就好了,也就是minWidth=max(a,b)-1,但是minWidth还要与之前的minWidth取最小值,所以最终公式为minWidth=max(minWidth,max(a,b)-1)。拿到宽度以后我们再遍历map,然后记录有多少个点再minWidth的范围之内就好了。
- 进阶思路:我的代码时间复杂度有点高,因为涉及到了排序。然后我看了下网上大佬们的思路,其实不用排序的,我们只需要遍历字符串,找到s[i]的这些点中,第二小的切比雪夫距离。
- 技巧:排序
java代码
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {Map<Character, List<int[]>> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {List<int[]> list = map.getOrDefault(s.charAt(i), new ArrayList<>());list.add(points[i]);map.put(s.charAt(i), list);}// 对list进行排序int minWidth = Integer.MAX_VALUE;for (Map.Entry<Character, List<int[]>> entry : map.entrySet()) {List<int[]> value = entry.getValue();if (value.size() >= 2) {// 坐标最大的那个放在后面value.sort(Comparator.comparingInt(o -> Math.max(Math.abs(o[0]), Math.abs(o[1]))));// 获取第二个点int[] point = value.get(1);// 不能包含第二个点minWidth = Math.min(minWidth, Math.max(Math.abs(point[0]), Math.abs(point[1])) - 1);}}int ret = 0;for (Map.Entry<Character, List<int[]>> entry : map.entrySet()) {List<int[]> value = entry.getValue();int[] point = value.getFirst();if (Math.abs(point[0]) <= minWidth && Math.abs(point[1]) <= minWidth) {ret++;}}return ret;}
}
java代码——进阶
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {Map<Character, Integer> map = new HashMap<>();// 正方形的宽度的一半int minWidth = Integer.MAX_VALUE;for (int i = 0; i < s.length(); i++) {int temp = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));// s[i]的宽度Integer siWidth = map.getOrDefault(s.charAt(i), Integer.MAX_VALUE);if (temp < siWidth) {// 因为已经有比siWidth小的点了,siWidth可能是第二小的点minWidth = Math.min(minWidth, siWidth);// 当前这个点的坐标会更小,我们要保留这个点map.put(s.charAt(i), temp);} else if (temp < minWidth) {// temp这个可能是不是s[i]中更小的,但是他比minWidth小minWidth = temp;}}int ret = 0;for (Map.Entry<Character, Integer> entry : map.entrySet()) {if (entry.getValue() < minWidth) {ret++;}}return ret;}
}
- 总结:题目还是有点难度的,主要是这里的切比雪夫距离。
相关文章:
LeetCode——3143. 正方形中的最多点数
通过万岁!!! 题目:给你一个n*2的数组,然后第i行表示第i个点的坐标,然后还给你了一个字符串s,s[i]则表示第i个点的名称。然后让你找一个中心是(0,0)的正方形,…...
const重新赋值的问题
问: const haveNextPage false; // 默认没有下一页fetch(historyFullUrl).then(data > {haveNextPage data.data.has_more;这段代码有什么问题吗? 回答: 在你的代码中,有一个潜在的问题涉及到 haveNextPage 的赋值。你定义了 haveNextPage 作为一个常量&am…...

python开发上位机 - PyCharm环境搭建、安装PyQt5及工具
目录 简介: 一、安装PyCharm 1、下载 PyCharm 2、PyCharm安装 1)配置安装目录 2)安装选项 3、问题及解决方法 二、安装PyQt5 1、打开 Pycharm,新建 Project 2、安装 pyqt5 3、安装很慢怎么办? 4、安装 pyq…...
day02-安装虚拟机
1. 安装配置 前面一直下一步就OK 2. 虚拟机操作系统配置 语言 中文 软件安装: 最小安装,标准,调试工具,开发工具,系统工具,man手册 网络和主机名配置 主机名,自己起名字 网络配置 常规 &g…...
Qt:线程
一个Qt窗口生成后,为什么拖动窗口,窗口可以随着鼠标移动或放大缩小 因为对窗口操作后,都有对应的事件产生,Qt在其框架中对这些事件进行了默认处理 一个Qt程序默认只有一个线程,称为主线程(也叫ui线程&#…...

VisionPro二次开发学习笔记11-使用 Caliper和Fixture定位Blob工具检测方块
该示例演示了如何使用卡尺工具和夹具工具来固定 Blob 工具。示例代码将检测图像上部区域中小方块的存在。当点击“运行”按钮时,将读取一张新图像。卡尺工具将被运行,卡尺工具的输出 Y 信息将传递给夹具工具。夹具工具使用来自卡尺工具的 Y 信息和新图像…...

高翔【自动驾驶与机器人中的SLAM技术】学习笔记(五)卡尔曼滤波器一:认知卡尔曼滤波器;协方差矩阵与方差;
卡尔曼滤波器 为了研究卡尔曼,我阅读了大量博文。不敢说完全吃透,但是在做一件什么事,可以通过下面这文章来理解,我读了不下五遍。并整理标准重点,添加自己的一些见解。 自动驾驶传感器融合算法 - 自动驾驶汽车中的激…...

【Go】通过反射解析对象tag信息,实现简易ORM
反射是运行时,需要在运行时解析类型信息,编译期无法优化这些操作,因此比编译时已知类型信息的直接调用效率要低。 package mainimport ("fmt""reflect""strings" )type Person struct {Name string json:&quo…...

gemini2相机和宇树雷达L1的使用注意点
gemini2相机: 官方资料:Gemini2深度相机 (yahboom.com) 目前深度这一块智能提供某一点的深度数据,没有提供某一点的世界坐标,虽然网上有文章说是可以计算 已知深度图,获得某个像素点的三维坐标_深度图如何知道特征点的3d坐标-CS…...
FPGA开发——verilog随机涵数$random的使用方法
一、概述 我们进行FPGA开发的过程中在做仿真的时候,难免会需要一些数据作为输入。有的时候需要输入大量的数据对于设计结果进行一个验证,如果逐个去进行输入,就需要花费大量的时间。这种情况下我们通常会想到使用随机数。随机数在我们的日常…...
Android14 WPA2和WPA3 类型的WiFi网络连接
Android14 WPA2和WPA3 类型的WiFi网络连接 文章目录 Android14 WPA2和WPA3 类型的WiFi网络连接一、前言二、源码分析1、Android原生Settings 连接WPA 和WPA3 网络的配置代码 三、其他1、WPA/WPA2和WPA3连接小结2、WPA配置无法连接WPA3的网络的情况Android11 Wifi 加密类型详解 …...

24/8/5算法笔记 逻辑回归sigmoid
今日是代码对sigmoid函数的实现和运用 #linear_model线性回归 #名字虽然叫逻辑回归,作用于分类 #分类:类别 #回归:预测 from sklearn.linear_model import LogisticRegression 实现函数 import numpy as np import matplotlib.pyplot as pl…...

适用于验证码的OCR,识别快速,使用简单!
环境 windows 11python 3.9 前言 Muggle OCR 是一个高效本地 OCR 模块,旨在通过简单的几步设置提供强大的文本识别功能,无论是在处理印刷文本还是解析验证码,都能让用户在工作中畅通无阻。Muggle OCR 易于安装和使用,支持双模型&a…...
超简单适合练手的双指针题:判断子序列
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列&#…...

打破老美垄断,潘展乐商业价值起飞
文|琥珀食酒社 作者 | 积溪 奥运会上的潘展乐 真是牛逼坏了 拿下男子100米自由游金牌 打破欧美长达近百年垄断 搞定男子4x100米混合泳金牌 终结了美国在这项目上 10年不败的神话 比赛前 美国选手对他爱答不理 招呼都不打 比赛后美国选手想套热乎 潘展乐…...
java面试题:简化URL
1 问题场景 编写一种方法,将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的“真实”长度。 注意:字符串长度在 [0, 500000] 范围内。 2 答案 2.1 解决方案一 直接使用String方法解决 public s…...

用 echarts 开发地图、点击展示自定义信息框
1、下载所需地市的json 链接:DataV.GeoAtlas地理小工具系列 在右侧输入需要的名称,然后下载json文件到本地 2、在html 中准备容器,并设置宽高 <div id"mapContent"> <div ref"mapChart" style"width:10…...
Android 应用兼容性变更调试
引言 本文将介绍如何调试和解决这些兼容性问题,并记录调试过程中实际操作的步骤和方法。在Android应用开发中,随着Android系统版本的不断更新,应用的兼容性问题变得越来越复杂。 推荐:《Android系统开发中高级定制专栏导读》08-03 16:04:53.518 6555 6555 D Compatibili…...

76 多态
多态(polymorphism)是指基类的同一个方法在不同派生类对象中具有不同的表现和行为。 派生类继承了基类的行为和属性之后,还会增加某些特定的行为和属性,同时还可能会对继承来的某些行为进行一定的改变,这都是多态的表现…...

数据采集工具之Canal
本文主要介绍canal采集mysql数据的tcp、datahub(kafka)模式如何实现 1、下载canal https://aliyun-datahub.oss-cn-hangzhou.aliyuncs.com/tools/canal.deployer-1.1.5-SNAPSHOT.tar.gz canal的原理类似于mysql的主从复制,canal模拟的是从节点拉取主节点的binlog数…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...