個人主頁：Lei寶啊?

愿所有美好如期而遇

---

目錄

第一題?

第二題

第三題

---

第一題?

隨機鏈表的復制https://leetcode.cn/problems/copy-list-with-random-pointer/description/

思路?

首先遍歷舊鏈表，并創建新節點，同時用map將舊節點與新節點存起來建立聯系，這樣在遍歷新鏈表填充random的時候，就可以這樣填Node* copy = m[cur]; copy->random = m[copy->random];

代碼

class Solution {
public:Node* copyRandomList(Node* head) {Node* cur = head;Node* phead = nullptr;Node* ptail = nullptr;map<Node*,Node*> m;while(cur){Node* temp = new Node(cur->val);if(phead == nullptr){phead = ptail = temp;}else{ptail->next = temp;ptail = ptail->next;}m[cur] = temp;cur = cur->next;}cur = head;while(cur){Node* copy = m[cur];if(cur->random == nullptr)copy->random = nullptr;elsecopy->random = m[cur->random];cur = cur->next;}return phead;}
};

第二題

前K個高頻單詞https://leetcode.cn/problems/top-k-frequent-words/description/

思路?

這道題有兩個點，第一個點是按照單詞出現頻率排序，第二個點是頻率相同，按字母的字典序排序。

首先我們可以使用map<string,int>來存單詞和他的頻率，這樣這些單詞就先進行了字典序排序，接著將map里的元素拷貝到一個vector<pair<string,int>>中，然后按照頻率排序，但是這個排序必須是穩定排序，因為我們一開始在map中就已經按照字典序排好了單詞，接下來按照頻率排序時，穩定排序不會改變原來頻率相同單詞的相對順序，所以這里的排序有兩種選擇，第一種就是使用庫里的stable_sort，這個底層使用的歸并排序，是穩定排序，而sort是不穩定排序，底層使用的快排。第二種就是使用sort，改變他的排序方式，有一個參數Compare comp,就是一個仿函數的對象，我們需要自己寫一個仿函數，然后傳遞他的對象。

代碼

class Solution {
public:class Compare{public:bool operator()(const pair<string,int>& k, const pair<string,int>& v){return k.second > v.second || (k.second == v.second && k.first < v.first);}};vector<string> topKFrequent(vector<string>& words, int k) {//去重并按照字典順序排序map<string,int> m;for(auto &e : words){m[e]++;}//按照頻率排序，并在頻率相同時按照字典序排序vector<pair<string,int>> v(m.begin(),m.end());sort(v.begin(),v.end(),Compare());vector<string> ret;for(auto &e : v){ret.push_back(e.first);k--;if(k == 0) break;}return ret;}
};

第三題

兩個數組的交集https://leetcode.cn/problems/intersection-of-two-arrays/description/

思路

這里需要使輸出結果的每個元素唯一，那么我們需要對原來的容器中的元素進行去重，這里我們可以使用set，第一種方式，我們使用set去重后，使用迭代器遍歷其中一個set，然后在另一個set中找是否存在，存在就push_back進我們的vector中。第二種方式，我們使用迭代器遍歷兩個set，然后使*it1和*it2中小的++，大的繼續往后走，相等的就push_back，這種方法的好處是不僅可以取交集，還可以取差集（相等跳過，不相等留下）。

代碼

class Solution 
{
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2){set<int> st1(nums1.begin(),nums1.end());set<int> st2(nums2.begin(),nums2.end());vector<int> v;set<int>::iterator it1 = st1.begin();set<int>::iterator it2 = st2.begin();while(it1 != st1.end() && it2 != st2.end()){if(*it1 < *it2) it1++;else if(*it1 > *it2) it2++;else{v.push_back(*it1);it1++;it2++;} }return v;}
};