C++——map相关的oj题

前言：菜鸟写博客给自己看，我是菜鸟。

1：随机链表的复制

1.1题目要求：

1.2解题思路：

可以分两步来实现代码：

①先将示例1链表中的val值以及next的指向关系深拷贝到另一个新的链表当中

②再处理新链表中，random的指向关系。

思考：

第①步是很容易实现的，那么如何处理新链表中random的指向关系呢？这时候可以试着用map去解决。

map<key,T>：

map<key,T>的底层是红黑树，其内部的数据是使用pair<key,T>存储键值对数据(这里的key,T是数据类型)，键值对是一一对应/映射的关系。举一个简单的例子:

"苹果" <-> "apple"

"橘子" <-> "orange"

其中，key是不可修改的，而T是可修改的。

分析：

在第①步创建新节点的同时，将新节点与旧节点通过map<Node*,Node*> 建立键值对的关系，这样就得到了新旧节点间的映射关系。

更进一步的，再仔细想想如何处理新链表中random的指向关系呢？

是 新节点->random = 旧节点->random 吗？显然不是，题目要求构造一个全新的链表，这样的指向关系，会使得新旧链表的random指向同一个节点。

因此不是 新节点->random = 旧节点->random ，而是 新节点->random = 旧节点->random所映射的节点，可以通过map函数中的operator[]来实现。

总结：

在第①步创建链表的同时，将新旧节点通过map<Node*,Node*>建立映射关系。

在第②步中，可以通过映射关系，例如 旧13节点的random 指向 7节点，那么 新13节点 可以通过 旧13节点的random 先找到 旧7节点，再根据 map<Node*,Node*> 建立的映射关系，找到 新7节点 ，从而建立正确的指向关系

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) {map<Node*,Node*> copymap;Node* copyhead = nullptr;Node* copytail = nullptr;Node* cur = head;while(cur){if(copyhead == nullptr){copyhead = copytail = new Node(cur->val);}else{copytail->next = new Node(cur->val);copytail = copytail->next;}copymap[cur] = copytail;cur = cur->next;}Node* copy = copyhead;cur = head;while(cur){if(cur->random == nullptr){copy->random = nullptr;}else{copy->random = copymap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};

2：前K个高频单词

2.1题目要求：

前言：这是一道综合应用stl的题目，难度对于新人(博主)来说有点大，本题涉及一些对先前知识的查漏补缺。

2.2解题思路：

思路：

👉：首先应该想到的是：创建一个map<string,int> CountMap 来统计每个单词出现的个数。

👉：map类会自动将数据按照 key(前一个数据类型)来排列，即此时 CountMap 中的数据是按照 string(对应首字母的ascii码值)来排序。

👉：但是题目要求是出现次数多的在前，因此我们需要对map中的数据做处理

👉：将map中的数据拷贝到vector中，并排列得到我们想要的顺序

👉：最后再输出vector中前k个字母。

注：上述还涉及很多细节问题，在2.3中再做讨论。

2.3实现代码：

class Solution {
public:struct compare{bool operator()(const pair<string,int>& x1,const pair<string,int>& x2){return x1.second > x2.second || (x1.second == x2.second && x1.first < x2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {//统计每个字母出现的次数map<string,int> CountMap;for(auto& e : words){CountMap[e]++;}//将map中的数据拷贝到vector中进行比较vector<pair<string,int>> v(CountMap.begin(),CountMap.end());//按字符串顺序排列//默认的比较方式不满足我们的要求，因此需要自己写一个仿函数来实现stable_sort(v.begin(),v.end(),compare());//取前K个单词，并存放到 str 中作为返回值vector<string> str;for(int i = 0; i<k; i++){str.push_back(v[i].first);}return str;}
};

将代码逐一拆分解释：

        map<string,int> CountMap;for(auto& e : words){CountMap[e]++;}
该段代码用于统计每个字母出现的次数，通过map类(map<string,int>)来记录单词与出现字数之间的映射关系。

注：map<key,T> map类会按照key默认进行排序

        vector<pair<string,int>> v(CountMap.begin(),CountMap.end());//按字符串顺序排列stable_sort(v.begin(),v.end(),compare());
因为map类的默认排序不满足题给要求，因此我们需要新创建一个vector类，来保存map类中的数据。

★★★注：在map类中，iterator的返回类型是：pair<Key,T>。因此在创建 vector类时，默认参数为：pair<string,int>

问：这里为什么不用sort？而是用stale_sort,二者有什么区别？

答：编译不通过是一回事，更重要的是，排序的稳定性！

复习：排序分为稳定排序和不稳定排序，两者的区别在于：原本的数据如果已经满足排序要求，当前排序算法会不会改变原先的排列顺序，改变->不稳定排序；不改变->稳定排序

稳定排序：冒泡排序、插入排序、归并排序

不稳定排序：希尔排序、快速排序、堆排序等

其次：stable_sort 默认排序不满足我们的要求，因此需要自己写一个仿函数来实现我们所需的排序,如下：
    struct compare{bool operator()(const pair<string,int>& x1,const pair<string,int>& x2){return x1.second > x2.second;}};
compare() 涉及匿名对象调用的问题，可以通过两种方式来让stable_sort来调用我们的函数，一种是实例化compare对象，通过实例化的对象来调用，例如
        compare com；stable_sort(v.begin(),v.end(),com); 
此时不需要加括号，还有一种就是图中代码所写的匿名对象来调用。

注1：大多数时候，我们是不用写第三个参数的，只不过有些时候因为默认参数不满足我们的要求，因此这种时候需要通过仿函数来满足自己的要求。

注2：operator()，这个在优先队列一节中也曾使用过。