C++ 使用map，set 重实现链表算法题

1.两个数组的交集给定两个数组nums1和nums2返回它们的 交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。psset可直接去重class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { setint s1(nums1.begin(),nums1.end()); setint s2(nums2.begin(),nums2.end()); vectorint v; auto it1 s1.begin(); auto it2 s2.begin(); while(it1!s1.end() it2!s2.end()) { if(*it1*it2) it1; else if(*it1*it2) it2; else if(*it1*it2) { v.push_back(*it1); it1; it2; } } return v; } };2.带环链表给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。eg输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。class Solution { public: ListNode *detectCycle(ListNode *head) { setListNode* s; ListNode* cur head; while(cur) { auto ret s.insert(cur); if(ret.second false) { return cur; } cur cur-next; } return nullptr; } };思路1.将链表节点的地址存入set中使用set特性若插入值已存在则插入失败2.insert返回类型为pair迭代器bool 即 插入成功返回新插入节点地址true插入失败返回已存在的节点的地址false3.若ret.second false说明该地址节点已经存在插入失败为带环链表若ret.second true说明该节点与之前节点并不重复若该情况直至结束则说明该链表不为带环链表3.随机链表复制class Solution { public: Node* copyRandomList(Node* head) { mapNode*,Node* nodeMap; Node* copyhead nullptr; Node* copytail nullptr; Node* cur head; while(cur) { if(copytail nullptr) { copyhead copytail new Node(cur-val); } else { copytail-next new Node(cur-val); copytail copytail-next; } nodeMap[cur] copytail; cur cur-next; } Node* copy copyhead; cur head; while(cur) { if(cur-random nullptr) { copy-random nullptr; } else { copy-random nodeMap[cur-random]; } cur cur-next; copy copy-next; } return copyhead; } };思路1.nodeMap[cur] copytail; 利用map的kv结构建立映射2.copy-random nodeMap[cur-random];即用cur-random当nodeMap的key查找出来的val赋给copy的random从而实现随机链表的赋值。4.前k个高频词class Solution { public: struct Compare { bool operator()(const pairstring,int x,const pairstring,int y) { return x.secondy.second || ((x.secondy.second) x.firsty.first); } }; vectorstring topKFrequent(vectorstring words, int k) { mapstring,int countmap; for(auto e:words) { countmap[e]; } vectorpairstring,int v(countmap.begin(),countmap.end()); sort(v.begin(),v.end(),Compare()); vectorstring strv; for(int i 0;ik;i) { strv.push_back(v[i].first); } return strv; } };