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

力扣刷题之3143.正方形中的最多点数

题干描述

给你一个二维数组 points 和一个字符串 s ,其中 points[i] 表示第 i 个点的坐标,s[i] 表示第 i 个点的 标签 。

如果一个正方形的中心在 (0, 0) ,所有边都平行于坐标轴,且正方形内  存在标签相同的两个点,那么我们称这个正方形是 合法 的。

请你返回 合法 正方形中可以包含的 最多 点数。

注意:

  • 如果一个点位于正方形的边上或者在边以内,则认为该点位于正方形内。
  • 正方形的边长可以为零。

示例 1:

输入:points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = "abdca"

输出:2

解释:

边长为 4 的正方形包含两个点 points[0] 和 points[1] 。

示例 2:

输入:points = [[1,1],[-2,-2],[-2,2]], s = "abb"

输出:1

解释:

边长为 2 的正方形包含 1 个点 points[0] 。

示例 3:

输入:points = [[1,1],[-1,-1],[2,-2]], s = "ccd"

输出:0

解释:

任何正方形都无法只包含 points[0] 和 points[1] 中的一个点,所以合法正方形中都不包含任何点。

题干分析

        已知题目要求我们找到一个合法的正方形,中心在(0,0),边平行于坐标轴,并且正方形内不能有两个点的标签相同。我么需要返回这样一个合法正方形内可以包含的最多点。

示例分析

  • 示例1:在标签a和b的最小距离都小于所有标签的次小距离的情况下,可以容纳最多的点数是2。
  • 示例2:因为只有标签a的最小距离小于次小距离,所以结果是1.
  • 示例3:所有点都无法单独构成合法的正方形,所以结果是0。

解题思路

1.定义一个合法的正方形:
  • 正方形的中心为(0,0)。
  • 正方形的边长可以从0开始逐渐增加。
  • 在正方形的边界或内部不能有两个标签相同的点。
2.距离计算:

       计算每个点(x,y)到原点的最大绝对坐标距离,即d = max(abs(x),abs(y))。这样,边长为2*d的正方形可以刚好覆盖这个点。选择最大的绝对值是因为正方形的边需要平行于坐标轴,确保正方形能够完全包含点(x,y)。

3.最小距离更新:

我们维护一个min1数组和一个min2变量:

  • min1数组:用于记录每个标签对应的最小距离。min1[j]表示标签为j的点中,到原点的最小距离。这个最小距离表示对于每个标签j,能使其位于正方形内的最小正方形边长。
  • min2变量:用于记录所有标签中的次小最小距离。这意味着所有标签的最小距离中,第二小的值。这个值的意义在于如果某个标签的最小距离小于min2,我们就能够确保在正方形中只包含这一标签,而不包含其他可能导致标签冲突的点。换句话说,标签j的最小距离min1[j]小于min2以为着子在该标签的正方形内部不会有其他标签的点,也即不会有标签重复的情况。
4.判断合法性:
  • 如果一个标签的最小距离min1[j]小于min2,则可以认为这个标签可以包含在合法正方形中。
  • 这是因为min2是次小的最小距离,任何小于min2的标签距离都不会导致重复的标签出现。
 5.最大化点数:
  • 计算并返回所有满足条件的标签的数量,这个数量即是哈法正方形内可以包含的最多点数。

 代码示例

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>//计算最大合法正方形的点数
int maxPointsInsideSquare(int** points, int pointsSize, int* pointsColSze, char* s) {int min1[26];//初始化每个标签的最小距离为最大值for (int i = 0; i < 26; i++){min1[i] = INT_MAX;}int min2 = INT_MAX;//第二小的最小距离初始化为最大值int n = pointsSize;//点的数量//遍历所有点for (int i = 0; i < n; ++i){int x = points[i][0], y = points[i][1];int j = s[i] - 'a';//标签对应的索引int d = (abs(x) > abs(y)) ? abs(x) : abs(y); // 计算该点到原点的距离//更新每个标签的最小和次小距离if (d < min1[j]){min2 = (min2 < min1[j]) ? min2 : min1[j];min1[j] = d;}else if (d < min2) {min2 = d;}}int res = 0;//用于记录最大合法点数//统计合法点数for (int i = 0; i < 26; i++){if (min1[i] < min2) {//如果标签的最小距离小于次小距离,则认为其可以包含在合法正方形中++res;//增加合法点数计数}}return res;//返回合法点数
}
int main() {// 测试用例1int points1[][2] = { {2, 2}, {-1, -2}, {-4, 4}, {-3, 1}, {3, -3} };int* ptr1[5];for (int i = 0; i < 5; i++) {ptr1[i] = points1[i];}int pointsColSize1[5] = { 2, 2, 2, 2, 2 }; // 每个点的列数char s1[] = "abdca"; // 标签字符串printf("Output: %d\n", maxPointsInsideSquare(ptr1, 5, pointsColSize1, s1)); // 期望输出: 2// 测试用例2int points2[][2] = { {1, 1}, {-2, -2}, {-2, 2} };int* ptr2[3];for (int i = 0; i < 3; i++) {ptr2[i] = points2[i];}int pointsColSize2[3] = { 2, 2, 2 }; // 每个点的列数char s2[] = "abb"; // 标签字符串printf("Output: %d\n", maxPointsInsideSquare(ptr2, 3, pointsColSize2, s2)); // 期望输出: 1// 测试用例3int points3[][2] = { {1, 1}, {-1, -1}, {2, -2} };int* ptr3[3];for (int i = 0; i < 3; i++) {ptr3[i] = points3[i];}int pointsColSize3[3] = { 2, 2, 2 }; // 每个点的列数char s3[] = "ccd"; // 标签字符串printf("Output: %d\n", maxPointsInsideSquare(ptr3, 3, pointsColSize3, s3)); // 期望输出: 0return 0;
}

相关文章:

力扣刷题之3143.正方形中的最多点数

题干描述 给你一个二维数组 points 和一个字符串 s &#xff0c;其中 points[i] 表示第 i 个点的坐标&#xff0c;s[i] 表示第 i 个点的 标签 。 如果一个正方形的中心在 (0, 0) &#xff0c;所有边都平行于坐标轴&#xff0c;且正方形内 不 存在标签相同的两个点&#xff0c…...

【更新2022】省级经济高质量发展指标体系测度 含代码 2000-2022

重磅更新&#xff01;【章汕】制作“省级经济高质量发展指标体系测度 含代码”&#xff0c;市面上有这个版本的数据&#xff0c;但其内容非常不全面&#xff0c;个别指标有误&#xff0c;没有stata和代码&#xff0c;即使有代码小白也很容易报错&#xff1b;没有权重、宽面板等…...

缓冲流练习

练习1&#xff1a;拷贝文件 四种方式拷贝文件&#xff0c;并统计各自用时。 字节流的基本流&#xff1a;一次读写一个字节 字节流的基本流&#xff1a;一次读写一个字节数组 字节缓冲流&#xff1a;一次读写一个字节 字节缓冲流&#xff1a;一次读写一个字节数组 这里我只使用了…...

自己履行很多的话语,依旧按照这个方式进行生活

《明朝那些事儿》最后一段讲述了徐霞客的故事&#xff0c;作者当年明月通过徐霞客的生平表达了一种人生哲学。在书的结尾&#xff0c;当年明月写道&#xff1a;"成功只有一个——按照自己的方式&#xff0c;去度过人生"&#xff0c;这句话被用作《明朝那些事儿》的结…...

交通预测数据文件梳理:METR-LA

文章目录 前言一、adj_METR-LA.pkl文件读取子文件1读取子文件2读取子文件3 二、METR-LA.h5文件 前言 最近做的实验比较多&#xff0c;对于交通预测数据的各种文件和文件中的数据格式理解愈加混乱&#xff0c;因此打算重新做一遍梳理来加深实验数据集的理解&#xff0c;本文章作…...

按钮类控件

目录 1.Push Button 代码示例: 带有图标的按钮 代码示例: 带有快捷键的按钮 代码示例: 按钮的重复触发 2.Radio Buttion 代码示例: 选择性别 代码示例: click, press, release, toggled 的区别 代码示例: 单选框分组 3.3 Check Box 代码示例: 获取复选按钮的取值 1.Pu…...

opencascade AIS_ViewController源码学习 视图控制、包含鼠标事件等

opencascade AIS_ViewController 前言 用于在GUI和渲染线程之间处理视图器事件的辅助结构。 该类实现了以下功能&#xff1a; 缓存存储用户输入状态&#xff08;鼠标、触摸和键盘&#xff09;。 将鼠标/多点触控输入映射到视图相机操作&#xff08;平移、旋转、缩放&#xff0…...

拉削基础知识——拉床的类型及特点

拉床是所有机械加工工具中最简单的一种&#xff0c;由拉削工具、夹具、驱动装置和支撑架组成。拉削加工可获得较高的尺寸精度和较小的表面粗糙度&#xff0c;生产率较高&#xff0c;适用于大批量生产。拉床按其结构主要分为卧式和立式。应用领域和功能可分为液压拉床、自动拉床…...

docker-compose笔记

docker 目前docker官网已经无法登录&#xff0c;但是还可以从清华镜像站&#xff08;https://mirrors.tuna.tsinghua.edu.cn/docker-ce/&#xff09;下载。 使用方法可以参考早期文章《docker笔记》 docker-compose 可以从Github下载不同版本的二进制文件&#xff0c;例如do…...

C# 自定义控件无法加载

问题 在做winform开发时自己定义了一个控件&#xff0c;控件在工具箱中显示了&#xff0c;但是拖动到窗体设计器时会提示未能加载工具箱项xxx&#xff0c;将从工具箱中将其删除&#xff0c;如下图所示: 点击确定后&#xff0c;控件会从工具箱中移除。 解决方法 将 生成>…...

avl树自实现(带图),探讨平衡因子与旋转

引子&#xff1a; 在此之前&#xff0c;我们学过了搜索二叉树&#xff0c;这种树&#xff0c;在如果数据有序或接近有序的情况下&#xff0c;二叉搜索树将退化为单支树&#xff0c;查找元素相当于在顺序表中搜索元素&#xff0c;效率低下&#xff0c;而且普通搜索二叉树无法有…...

Elasticsearch 的DSL查询,聚合查询与多维度数据统计

文章目录 搜索聚合高阶概念 搜索 即从一个索引下按照特定的字段或关键词搜索出符合用户预期的一个或者一堆cocument&#xff0c;然后根据文档的相关度得分&#xff0c;在返回的结果集里并根据得分对这些文档进行一定的排序。 聚合 根据业务需求&#xff0c;对文档中的某个或…...

【如何高效处理前端常见问题:策略与实践】

在快速发展的Web开发领域&#xff0c;前端作为用户与应用程序直接交互的界面&#xff0c;其重要性不言而喻。然而&#xff0c;随着技术的不断演进和项目的复杂化&#xff0c;前端开发者在日常工作中难免会遇到各种挑战和问题。本文旨在深入探讨前端开发中常见的问题类型&#x…...

聊聊前端 JavaScript 的扩展运算符 “...“ 的使用场景

前言 在 JavaScript 中&#xff0c;... 被称为 “扩展运算符” 或 “剩余参数运算符”。 扩展运算符是在 ES6&#xff08;ECMAScript 2015&#xff09;中被引入的&#xff0c;目的是为了提高语言的表达能力和代码的可读性。 根据上下文不同&#xff0c;它主要用在数组、对象…...

华为续签了,但我准备离职了

离职华为 今天在牛客网看到一篇帖子&#xff0c;名为《华为续签了&#xff0c;但我准备离职了》。 讲得挺真诚&#xff0c;可能也是一类毕业进华为的同学的心声。 贴主提到&#xff0c;当年自己还是应届毕业的时候&#xff0c;手握多个 offer&#xff0c;最终选的华为&#xff…...

RocketMQ 的认证与授权机制

Apache RocketMQ 是一个高性能、高吞吐量、分布式的消息中间件&#xff0c;广泛应用于异步通信、应用解耦、流量削峰等场景。在企业级应用中&#xff0c;消息安全尤为重要&#xff0c;本文将深入探讨 RocketMQ 的认证与授权机制&#xff0c;帮助开发者和系统管理员更好地理解和…...

【设计模式】六大原则-上

首先什么是设计模式&#xff1f; 相信刚上大学的你和我一样&#xff0c;在学习这门课的时候根本不了解这些设计原则和模式有什么用处&#xff0c;反而不如隔壁的C更有意思&#xff0c;至少还能弹出一个小黑框&#xff0c;给我个hello world。 如何你和我一样也是这么想&#xf…...

CRC16循环冗余校验

代码&#xff1a; #include<stdio.h> #include <stdint.h>#define uchar unsigned char #define uint unsigned int static const uint8_t auchCRCHi[] { 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x0…...

Mysql80主从复制搭建;遇到问题 Slave_IO_Running: Connecting和Slave_SQL_Running以及解决过程

总结主要步骤 1.配置一个提供复制的账号&#xff1b; 创建用户 CREATE USER replication% IDENTIFIED BY your_password; GRANT REPLICATION SLAVE ON *.* TO replication%; FLUSH PRIVILEGES;2.修改配置 选择模式 主库配置&#xff1b; windows的得话是my.ini文件 默认这个目…...

Yarn网络代理配置指南:在受限网络环境中优化依赖管理

Yarn是一个现代的包管理器&#xff0c;用于JavaScript项目&#xff0c;它提供了快速、可靠和安全的依赖管理方式。然而&#xff0c;在某些受限的网络环境中&#xff0c;例如公司内网或某些国家地区&#xff0c;直接连接到公共npm仓库可能不可行或效率低下。这时&#xff0c;配置…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

大数据驱动企业决策智能化的路径与实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、引言&#xff1a;数据驱动的企业竞争力重构 在这个瞬息万变的商业时代&#xff0c;“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...