思路精析:
自定义结构体解读:
一个点是否在题给正方形中,只取决于其横纵坐标的最大值,记为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