首页 > 编程语言 >【leetcode详解】正方形中的最多点数【中等】(C++思路精析)

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

时间:2024-08-03 19:58:30浏览次数:19  
标签:cur idx re 精析 C++ int points leetcode dis

思路精析:

自定义结构体解读:

一个点是否在题给正方形中,只取决于其横纵坐标的最大值,记为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;
    }
};

~ 希望对你有启发 ~

标签:cur,idx,re,精析,C++,int,points,leetcode,dis
From: https://blog.csdn.net/H13420972436/article/details/140894099

相关文章

  • 整数二分(c++)
    1、什么是整数二分:即可以看做成找数字那个游戏在一百个数字中找到指定的数字(66)A出题B:50A50太小了B:(50+100)/2=75A75太大了B:(50+75)/2=62…所以也可以知道一个结论:有单调性,一定可以二分。可以二分的题目,不一定有单调性。2、代码思路:1、寻找到满足......
  • 【C++BFS】802. 找到最终的安全状态
    本文涉及知识点C++BFS算法LeetCode802.找到最终的安全状态有一个有n个节点的有向图,节点按0到n-1编号。图由一个索引从0开始的2D整数数组graph表示,graph[i]是与节点i相邻的节点的整数数组,这意味着从节点i到graph[i]中的每个节点都有一条边。如果一......
  • 代码随想录算法训练营Day18 | Leetcode 530 二叉搜索树的最小绝对差 Leetcode 236 二
    前言今天有一道题目没写,二叉搜索树中的众数,有点太难理解了,先放一放。Leetcode530二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)代码随想录题解:代码随想录(programmercarl.com)思路:二叉搜索树的性质是中序遍历为升序的,所以我们想找最小绝......
  • 离散化-c++
    离散化:一、使用情景值域大e.g.0~1e9个数少e.g.0~1e5二、使用方法将数组中的数映射到从0开始的自然数a[]:1、3、100、2000、50000映射到从0开始的自然数:0,1,2,3,4这个过程就是离散化三、两个问题:1.a数组中最开始可能有重复元素,需要去重vector<int>alls;//存......
  • C++ 面向对象基础-构造函数
    目录1.构造函数1.1基本使用1.2函数参数默认值1.3构造初始化列表 1.4隐式调用构造函数2.拷贝构造函数2.1概念2.2浅拷贝2.3深拷贝3.析构函数1.构造函数1.1基本使用构造函数是一种特殊的成员函数,用于创建对象时初始化,写法上有以下要求:●函数名称必......
  • 【C++】实验十五
    题目:1、求一元二次方程ax2+bx+c=0的实根。如果方程没有实根,则利用异常处理处理机制输出有关警告信息2、学校的人事部门保留了有关学生的部分数据(学号、姓名、年龄、住址)。教务部门也保留了学生的另一些数据(学号、姓名、性别,成绩),两个部门分别编写了本部门的学生数据管理程序,其......
  • LeetCode面试150——238除自身以外数组的乘积
    题目难度:中等默认优化目标:最小化平均时间复杂度。Python默认为Python3。目录1题目描述2题目解析3算法原理及代码实现3.1左右乘积列表参考文献1题目描述给你一个整数数组nums,返回数组answer,其中answer[i]等于nums中除nums[i]之外其余各元素的乘积......
  • 【C++】红黑树
     ......
  • leetcode数论(2523. 范围内最接近的两个质数)
     前言经过前期的基础训练以及部分实战练习,粗略掌握了各种题型的解题思路。现阶段开始专项练习。描述给你两个正整数 left 和 right ,请你找到两个整数 num1 和 num2 ,它们满足:left<=nums1<nums2<=right  。nums1 和 nums2 都是 质数 。nums2-nums1......
  • C++ 最小生成树 洛谷
    介绍:最小生成树是个啥?其实就像杨志一行人押送生辰纲。抛开最后生辰纲被抢的结局不谈,杨志他们需要到好几个地方,每个地方都需要花点过路费给梁山好汉们打点。比如下面就是一张城市地图:其中每两个图之间的路径长就是要给梁山好汉们打点的银子数。比如1号地点到2号地点的梁山好......