每日一练 —— map习题

1. 随机链表的复制

题目链接：

138. 随机链表的复制 - 力扣（LeetCode）https://leetcode.cn/problems/copy-list-with-random-pointer/description/

 

map使用映射拷贝可以对两个无关的值建立关系

     

创建一个新的链表拷贝原链表以及next指针，然后将该链表存储在一个map中，使用每个节点本身当做key，random指针当做value，之后处理拷贝而来的新链表中的random指针，使用map中的key做映射，保证random在拷贝后链表中的相对位置与原链表的相同，最后返回拷贝而来的新链表的头结点

思路：定义一个map，我们可以先把原链表遍历一遍之后拷贝到一个新的链表中去，如果为空就给链表，如果不为空就尾插，然后将该链表存储在一个map中，将原节点和新节点之间建立出一个key - value的链接关系使用每个节点本身当做key，random指针当做value

    

然后处理random指针，copy与cur指针同时运动：遍历原链表，原链表的random指向为空，那么新链表的random指向也为空，如果原链表的random指向不为空，那么新链表就返回原链表的random指向的值

class Solution {
public:Node* copyRandomList(Node* head) {map<Node*,Node*> mapNode;Node* copyhead = nullptr;Node* copytail = nullptr;Node* cur = head;//拷贝原链表映射到map中并且创建一个新链表拷贝原链表while(cur){//初始时刻if(copytail == nullptr){copyhead = copytail = new Node(cur->val);}else{//从尾节点开始接入新节点copytail->next = new Node(cur->val);copytail = copytail->next;}//映射拷贝到map中mapNode[cur] = copytail;cur = cur->next;}//处理random指针，copy与cur指针同时运动cur = head;Node* copy = copyhead;while(cur){if(cur->random == nullptr){copy->random = nullptr;}else{//使用映射处理random节点copy->random = mapNode[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};

 

---

2. 前K个高频单词

692. 前K个高频单词 - 力扣（LeetCode）https://leetcode.cn/problems/top-k-frequent-words/description/

思路：

      

用排序找前k个单词，map已经对单词排序过了，也就是遍历map时， 字典序小的在前面，字典序大的在后面，然后我们再把数据放到vector中⽤stable_sort（因为sort底层是快排，是不稳定的，stable_sort是稳定的）来进行排序就可以实现上⾯特殊要求（按字典顺序排序 ）

class Solution {
public:struct Compare{bool operator()(const pair<string, int>& x, const pair<string, int>& y)const{return x.second > y.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for (auto& e : words){countMap[e]++;}vector<pair<string, int>> v(countMap.begin(), countMap.end());// 仿函数控制降序 stable_sort(v.begin(), v.end(), Compare());//sort(v.begin(), v.end(), Compare());// 取前k个 vector<string> strV;for (int i = 0; i < k; ++i){strV.push_back(v[i].first);}return strV;}
};

---

感谢观看~