购物网站源码下载,中和seo公司,贵州省兴义市建设局网站首页,北京网站建设公司哪家实惠一、两个数组的交集
题目链接#xff1a;
349. 两个数组的交集 - 力扣#xff08;LeetCode#xff09;
题目描述#xff1a;
给两个数组#xff0c;求在数组里面共同出现的部分#xff0c;就是求两个数组的交集#xff0c;返回顺序不做要求
解题思路#xff1a;
…一、两个数组的交集
题目链接
349. 两个数组的交集 - 力扣LeetCode
题目描述
给两个数组求在数组里面共同出现的部分就是求两个数组的交集返回顺序不做要求
解题思路
求交集问题可以先对数据进行去重升序排序然后两个数组同时从第一个开始走当数值相同则说明是交集输出并两个同时走下一个若是不相同则让小的那一个单独走到下一个直到某一个走完则结束。
参考代码 vectorint intersection(vectorint nums1, vectorint nums2) {//找交集先利用set去重加排序setint s1(nums1.begin(),nums1.end());setint s2(nums2.begin(),nums2.end());//升序序列找交集相同则为交集不同则小的往后走其中一方结束则结束auto it1 s1.begin();auto it2 s2.begin();vectorint ret;while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2){ret.push_back(*it1);it1;it2;}else if(*it1 *it2){it1;}else{it2;}}return ret;} 二、前k个高频单词
题目链接
692. 前K个高频单词 - 力扣LeetCode
题目描述
题目给你一个vectorstring类型也就是单词序列需要找到在序列中出现次数从多到少前k个单词并且要求当单词出现次数相同时要按照字典序排序存入到一个vectorstring中返回
解题思路
利用map去对单词进行统计然后按字典序输出存放到一个vectorpair中然后对序列中的单词根据次数进行排序由于题目要求相同时按照字典序排序因此使用排序的时候要求不破坏前后顺序也就是要求使用具有稳定性的排序去进行排序可以使用算法中提供的排序也可以利用仿函数给定排序规则去实现
参考代码 class Compare{public:bool operator()(const pairstring,int x,const pairstring,int y)const {return x.second y.second || (x.second y.second x.first y.first);}};vectorstring topKFrequent(vectorstring words, int k) {//使用map去统计每个单词的次数mapstring,int map_count;for(auto e:words){map_count[e];}//此时输出的顺序是按照字典序输出的将其存放到一个vectorpair中利用具有稳定性的方式按照次数排序即可vectorpairstring,int v(map_count.begin(),map_count.end());sort(v.begin(),v.end(),Compare());vectorstring ret;for(int i 0;ik;i){ret.push_back(v[i].first);}return ret;} 三、复杂链表的深拷贝
题目链接
LCR 154. 复杂链表的复制 - 力扣LeetCode
题目描述
题目给了一个单向的链表比起普通单链表还多了一个随机指针random每个节点的随机指针都随机指向其他节点或者是自己也可能是空题目要求拷贝一条一模一样的链表难点在于随机指针要完成深拷贝需要原链表和拷贝链表建立某种联系使得能够知道原链表的随机指针是如何指向的 解题思路
在C语言阶段时我们采用通过将每个拷贝节点链接在原节点的方式建立链接去确定random指针的指向现在我们学习了map以后可以直接通过map去建立原链表和拷贝链表之间的链接然后去确定好random
参考代码 Node* copyRandomList(Node* head) {//直接先拷贝一条链表Node* copy_head nullptr;Node* copy_tail nullptr;Node* cur head;while(cur){if(copy_head nullptr){copy_head new Node(cur-val);copy_tail copy_head;}else{Node* newnode new Node(cur-val);copy_tail-next newnode;copy_tail newnode;}cur cur-next;}//利用map建立两个链表之间的链接,并且通过原指针的random去找到copy后的random链接mapNode*,Node* m;Node* cur1 head;Node* cur2 copy_head;while(cur1){m[cur1] cur2;//建立链接cur1cur1-next;cur2cur2-next;}cur1 head;cur2 copy_head;while(cur1){cur2-random m[cur1-random];//通过联系链接cur1cur1-next;cur2cur2-next;}return copy_head;}
