每日一练 —— map习题

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;
    }
};

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;
    }
};