欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 游戏 > 【leetcode详解】正方形中的最多点数【中等】(C++思路精析)

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

2024/10/24 21:32:27 来源:https://blog.csdn.net/H13420972436/article/details/140894099  浏览:    关键词:【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;}
};

~ 希望对你有启发 ~

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com