做mip网站必须备案吗,如何做网站容易收录,网站敏感关键词,html网页模板制作一、习题一#xff1a;随机链表的复制
1.1题目详情 1.2思路
在没有学习map和set之前#xff0c;解决这道题最大的问题就在于无法建立原链表与拷贝链表的映射关系#xff0c;只能通过在原链表每个节点后面新建一个新的链表来进行节点间的对应#xff0c;而学习了map之后随机链表的复制
1.1题目详情 1.2思路
在没有学习map和set之前解决这道题最大的问题就在于无法建立原链表与拷贝链表的映射关系只能通过在原链表每个节点后面新建一个新的链表来进行节点间的对应而学习了map之后就可以选用mapNode*,Node*来建立两个链表之间的映射关系了
在map中我们对[]进行了重载可以实现没有对应key的节点时插入节点并对该处节点的value进行操作有key节点的时候直接对key对应的value进行操作
综上我们可以选择如下实现思路
①复制一个新的链表
②创建一个map对象利用它来创建原链表与新链表之间的映射关系
③更新随机因子random
1.3代码实现
①基本版
/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val _val;next NULL;random NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {mapNode*,Node* m1;//复制链表Node* curhead;Node* copy_nnullptr;Node* c_curcopy_n;while(cur){if(copy_nnullptr){c_curnew Node(cur-val);copy_nc_cur;curcur-next;}else{c_cur-nextnew Node(cur-val);c_curc_cur-next;curcur-next;}}//遍历在map中建立一一映射关系curhead;c_curcopy_n;while(cur){m1[cur]c_cur;//确定不会在map里有c_curc_cur-next;curcur-next;}//再次遍历对随机值random进行更新curhead;c_curcopy_n;while(cur){if(cur-randomnullptr)c_cur-randomnullptr;else{c_cur-random(m1.find(cur-random))-second;}c_curc_cur-next;curcur-next;}return copy_n;}
};
②改善版映射关系的建立可以和链表的复制一同进行
/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val _val;next NULL;random NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {mapNode*,Node* m1;//复制链表其中copy_n起头节点作用c_cur起尾节点作用Node* curhead;Node* copy_nnullptr;Node* c_curnullptr;while(cur){//头尾节点指向一起if(copy_nnullptr){copy_nnew Node(cur-val);c_curcopy_n;}//尾节点往后走else{c_cur-nextnew Node(cur-val);c_curc_cur-next;}//为原链表与循环链表建立联系嵌套在循环里m1[cur]c_cur;curcur-next;}//循环设置复制链表randomcurhead;c_curcopy_n;while(cur){if(cur-randomnullptr)c_cur-randomnullptr;else//c_cur-random(m1.find(cur-random))-second;//m1[cur-random]本身就返回second的值且一定存在cur-randomc_cur-randomm1[cur-random];c_curc_cur-next;curcur-next;}return copy_n;}
};
二、习题二判断是否循环链表
2.1题目详情 2.2思路
未学习map和set之前我们使用了快慢指针的方式来解决这道题但快慢指针的应用意味着我们需要进行循环必定相遇的求证证明过程并不简单但现在有了map和set我们就可以选择直接插入节点到set中因为set的insert会返回一个可以证明插入是否有效的
pairiterator,bool
利用这个bool我们可以轻易得出答案
2.3代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *tmphead;setListNode* sl;while(tmp){if(!(sl.insert(tmp).second))return true;tmptmp-next;}return false;}
};
2.补关于异地容灾备份
我们手机上的云存储其实对应的是一个数据同时存储在手机和服务器上当在手机上删除了备份过的内容服务器与手机进行同步服务的时候会自动把删除了的内容复原回去
但是数据实在服务器上存储服务器也是电脑也有可能损坏所以为了保证数据的安全性有了数据容灾备份采用一原本多副本的方式彼此间进行同步
三、前k个高频单词
3.1题目详情 3.2思路
之前题目一的练习我们已经知道了map中重载[]的用法在这里我们可以利用重载后的[]快速得到单词与单词出现次数的映射关系
有了映射关系以后我们只需要设法通过次数对pair进行排序即可得到前k个需要的单词可以在仿函数中书写逻辑再调用系统函数sort
因为返回值是一个vectorstring类型的值所以我们需要把map中的单词拷贝到vector中此时我们距离成功只差一步那就是按照字典序排序
那么我们就这么思考怎么排吗要知道map中我们其实已经是按照key的字典序排列的可不可以不消耗更多时间呢
问题可以从sort上解决因为sort的底层是快排与堆排结合既然有快排那么排序完以后就会变得不稳定所以
①可以采用稳定排序stable_sort
②可以在仿函数中进行比较逻辑的特殊设定让出现次数相同时按照字典序排序以此来保证稳定
综上我们可以得出思路
①创建map对象for循环建立映射关系
②补充仿函数逻辑将其传入sort并用sort进行次数的比较的出前k个单词
③把前k个单词放到一个新的vector中
3.2补pair的比较大小
pair之间其实也支持比较大小比如“”符号会先看first小不小如果first小的话那这个pair就小如果first大于等于的话会看second小不小seconde小的话也会小
例如
pairint,int p1make_pair(5,7);pairint,int p2make_pair(8,6);p1p2;//p1的first比p2小所以应该返回truep2p1;//p2的first比p1大所以要看p2的second而p2的second比p1小所以也返回true
通过这个例子不难看出除非在特殊情况否则最好不要去用pair本身自带的比较逻辑因为与我们日常思维方式不符合
3.3代码实现
①使用stable_sort稳定排序
struct Compare
{bool operator()(const pairstring,int p1,const pairstring,int p2){//排降序return p1.secondp2.second;}
};class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {//创建map建立单词出现顺序和次数的联系mapstring,int m;for(const auto e:words){m[e];}//排序提取出排名前几的单词vectorpairstring,int v_p;for(const auto e:m){v_p.push_back(e);}//使用相对位置不改变的sort来确保字典序排序stable_sort(v_p.begin(),v_p.end(),Compare());vectorstring s;for(size_t i0;ik;i){s.push_back(v_p[i].first);}return s;}
};
②修改仿函数逻辑保持稳定
struct Compare
{bool operator()(const pairstring,int p1,const pairstring,int p2){//排降序return p1.secondp2.second||(p1.secondp2.secondp1.firstp2.first);}
};class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {//创建map建立单词出现顺序和次数的联系mapstring,int m;for(const auto e:words){m[e];}//排序提取出排名前几的单词vectorpairstring,int v_p(m.begin(),m.end());//使用相对位置不改变的sort来确保字典序排序sort(v_p.begin(),v_p.end(),Compare());vectorstring s;for(size_t i0;ik;i){s.push_back(v_p[i].first);}return s;}
};
