【leetcode详解】正方形中的最多点数【中等】(C++思路精析)

思路精析:

自定义结构体解读:

一个点是否在题给正方形中,只取决于其横纵坐标的最大值,记为dis

沟通二位数组points和字符串s的桥梁,就是这个点的序号,记为idx

由此自定义结构体,储存dis 和idx

//其中bool operator部分的功能:重载小于操作符“<”, 使sort(vc.begin(), vc.end());按dis值升序排列

struct Node{int dis; int idx;bool operator<(const Node& other)const{return dis < other.dis;}
};
vector<Node>vc;

集合set的使用解释:

//笔者感觉,对于需要检验重复的问题,这是一种很经典的操作

set<int>st;
if(st.count(s[vc[i].idx]))
{if(cur_dis != vc[i].dis) re+=cur;return re;
} 
else st.insert(s[vc[i].idx]);

初始化:

int maxPointsInsideSquare(vector<vector<int>>& points, string s) {int x, y, sz = points.size();Node t_node;for(int i=0; i<sz; i++){int dis = max(abs(points[i][0]), abs(points[i][1]));t_node.dis = dis;t_node.idx = i;vc.push_back(t_node);}sort(vc.begin(), vc.end());
}

补充说明

用re记录总点数,用cur记录当前dis记录的点的个数

只有在dis相同的点全部符合要求时,才将其加到re上

re += cur

int re = 0, cur = 0, cur_dis=-1;
for(int i=0; i<sz; i++)
{if(st.count(s[vc[i].idx])){if(cur_dis != vc[i].dis) re+=cur;return re;} else st.insert(s[vc[i].idx]);if(cur_dis != vc[i].dis){re += cur;cur = 1;cur_dis = vc[i].dis;}else cur++;
}
return re+cur;

//在上述思路基础上,通过不断调试,见到了更多测试数据,由此进一步完善细节

AC代码见下:

class Solution {
private:struct Node{int dis; int idx;bool operator<(const Node& other)const{return dis < other.dis;}};vector<Node>vc;set<char>st;
public:int maxPointsInsideSquare(vector<vector<int>>& points, string s) {int x, y, sz = points.size();Node t_node;for(int i=0; i<sz; i++){int dis = max(abs(points[i][0]), abs(points[i][1]));t_node.dis = dis;t_node.idx = i;vc.push_back(t_node);}sort(vc.begin(), vc.end());int re = 0, cur = 0, cur_dis=-1;for(int i=0; i<sz; i++){if(st.count(s[vc[i].idx])){if(cur_dis != vc[i].dis) re+=cur;return re;} else st.insert(s[vc[i].idx]);if(cur_dis != vc[i].dis){re += cur;cur = 1;cur_dis = vc[i].dis;}else cur++;}return re+cur;}
};

~ 希望对你有启发 ~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/390406.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于 KubeSphere 的 Kubernetes 生产环境部署架构设计及成本分析

转载&#xff1a;基于 KubeSphere 的 Kubernetes 生产环境部署架构设计及成本分析 前言 导图 1. 简介 1.1 架构概要说明 今天分享一个实际小规模生产环境部署架构设计的案例&#xff0c;该架构设计概要说明如下&#xff1a; 本架构设计适用于中小规模(<50)的 Kubernetes …

C#对象和类型

属性、方法、字段 字段和属性的区别 在C#中&#xff0c;字段&#xff08;fields&#xff09;和属性&#xff08;properties&#xff09;都是类的成员&#xff0c;它们提供了类存储数据的方式&#xff0c;但它们在用途和功能上有着明显的区别。 字段 字段通常用来存储类…

Gstreamer配合srs服务器实现RTMP直播和WebRtc直播

前言 上一篇文章,实现了配合腾讯云直播的推流,但是需要花钱,于是就在思考能不能搞一个局域网内,免费的RTMP直播呢? 最终发现了可以使用srs服务器。如果成功了,以后也可以使用webrtc的直播推流。 以下是实现效果: 一、搭建srs服务器: 参考:ubuntu环境下搭建SRS服务器(…

MyBatis全方位指南:从注解到XML文件的数据库操作

目录 一.什么是MyBatis 入门程序初体验 二.MyBatis基本操作CRUD ▐ 增(Insert) 返回主键 ▐ 删(Delete) ▐ 改(Update) ▐ 查(Select) 起别名 结果映射 开启驼峰命名(推荐) 三.MyBatis XML配置文件 ▐ 增(Insert) ▐ 删(Delete) ▐ 改(Update) ▐ 查(Select) …

Linux:Xshell相关配置及前期准备

一、Linux的环境安装 1、裸机安装或者是双系统 2、虚拟机的安装 3、云服务器&#xff08;推荐&#xff09;——>安装简单&#xff0c;维护成本低&#xff0c;学习效果好&#xff0c;仿真性高&#xff08;可多人一起用一个云服务器&#xff09; 1.1 购买云服务器 使用云服…

基于环形拓扑的多目标粒子群优化算法(MO_Ring_PSO_SCD)求解无人机三维路径规划(MATLAB代码)

一、无人机多目标优化模型 无人机三维路径规划是无人机在执行任务过程中的非常关键的环节&#xff0c;无人机三维路径规划的主要目的是在满足任务需求和自主飞行约束的基础上&#xff0c;计算出发点和目标点之间的最佳航路。 1.1路径成本 无人机三维路径规划的首要目标是寻找…

【传知代码】Flan-T5 使用指南(论文复现)

当今&#xff0c;自然语言处理技术正在以前所未有的速度和精度发展。在这个领域中&#xff0c;Flan-T5作为一种新兴的预训练语言模型&#xff0c;正吸引着广泛的关注和应用。Flan-T5不仅仅是一个强大的文本生成工具&#xff0c;它还能通过提供高效的语义理解和多任务学习能力&a…

springboot配置多个数据源

实际业务中&#xff1b;在一个项目里面读取多个数据库的数据来进行展示&#xff0c;例如读取mysql&#xff0c;pgsql&#xff0c;oracle的不同数据库&#xff0c;springboto对同时配置多个数据源是支持的。 使用springbootmybatis的框架来进行演示&#xff0c; 在配置文件中配…

美国失业率大幅上升,增加九月份降息利率的可能性

令人失望的是&#xff0c;美国7月份经济增加了11.4万个工作岗位&#xff0c;低于预期的17.5万个和6月的17.9万个。平均小时工资持续下降&#xff0c;但失业率升至4.3%。美元继续走低&#xff0c;美国国债也在下跌&#xff0c;而黄金则获得了提振。 7月份的非农业支付数据令人失…

鸿蒙 IM 即时通讯开发实践,融云 IM HarmonyOS NEXT 版

融云完成针对“纯血鸿蒙”操作系统的 SDK 研发&#xff0c;HarmonyOS NEXT 版融云 IM SDK 已上线&#xff0c;开发者可在“鸿蒙生态伙伴 SDK 市场”查询使用。 发挥 20 年通信行业技术积累和领创品牌效应&#xff0c;融云为社交、娱乐、游戏、电商、出行、医疗等各行业提供专业…

react引入高德地图并初始化卫星地图

react引入高德地图并初始化卫星地图 1.安装依赖 yarn add react-amap amap/amap-jsapi-loader2.初始化地图 import AMapLoader from "amap/amap-jsapi-loader"; import { FC, useEffect, useRef, useState } from "react";const HomeRight () > {con…

普通人有必要学Python吗?学了之后能做什么?

目录 首先来说一下极其推荐的方向&#xff1a; 1、数据分析 2、科学计算 3、大数据框架 4、脚本开发 5、爬虫 6、Web框架 总结&#xff1a; 如果你还没有开始使用Python&#xff0c;答应我&#xff0c;把这个回答看完&#xff0c;如果你真的学习并深入使用过Python&…

我的最爱之《达明一派》

达明一派&#xff0c;是我最爱。刘以达(Tats)与黄耀明(Anthony Wong)在1980年代的香港组成的二人流行音乐组合&#xff0c;在90年代&#xff0c;网络还没兴起时&#xff0c;那是卡带流行的岁月。90年代&#xff0c;我与好友&#xff0c;同考大学&#xff0c;他留在了南充读读书…

使用labelme生成mask数据集(亲测可行)

1、下载label.exe文件 链接&#xff1a;github地址 2、安装一下anaconda&#xff0c;百度一下直接安装就行 3、打开labelme.exe文件&#xff0c;直接加载图片&#xff0c;然后编辑多边形&#xff0c;就是mask的位置 4、画好mask了&#xff0c;保存为json文件&#xff0c;记住这…

【qiankun微前端】基座主应用(vue2)+多个微应用(任意框架)

前言 前段时间对我们已有的工程进行了微前端改造,后来思考一下微前端的本质,查询了不少资料,从qiankun微前端示例中学到了不少。 微前端的核心,似乎应该是一个基座应用(含登录页,layout页,404和首页等),多个子应用(任意框架,提供内部页面内容),下面就对这个思路…

stm32入门-----软件I2C读写MPU6050

目录 前言 MPU6050 1.简介 2.相关参数 3.硬件电路 4.MPU6050框图 C编程实现I2C读写MPU6050步骤 1.MyI2C.c文件 &#xff08;1&#xff09;引脚的宏定义 &#xff08;2&#xff09;对SCL和SDA的操作以及初始化 &#xff08;3&#xff09;起始信号标志 &#xff08;4…

数据结构(面试)

目录 线索二叉树哈夫曼树并查集最小生成树最短路径拓扑排序二叉排序树平衡二叉树红黑树折半查找散列表堆排序归并排序 线索二叉树 原理&#xff1a;利用树节点的n1个左右空指针指向其遍历序列的前驱和后继&#xff08;线索&#xff09; 优点&#xff1a;简化遍历&#xff0c;不…

7.2 单变量(多->多),attention/informer

继续上文书写&#xff1a; 1 GRU Attention 收敛速度稳定的很多&#xff0c;你看这些模型是不是很容易搭&#xff0c;像积木一样&#xff1b; def create_model(input_shape, output_length,lr1e-3, warehouse"None"):input Input(shapeinput_shape)conv1 Conv…

【C++标准模版库】模拟实现vector+迭代器失效问题

模拟实现vector 一.vector成员变量二.构造函数1.无参&#xff08;默认&#xff09;构造2.有参构造3.拷贝构造1.传统写法2.现代写法 三.vector对象的容量操作1.size2.capacity3.clear4.empty5.reserve6.resize 四.vector对象的访问及遍历操作1.operator[]2.实现迭代器&#xff1…

免费【2024】springboot 大学生志愿者管理系统的设计与实现

博主介绍&#xff1a;✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术范围&#xff1a;SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化…