Leetcode Easy題小解（C++語言描述）

相交鏈表

給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回 null 。

圖示兩個鏈表在節點 c1 開始相交**：**

題目數據 保證 整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須 保持其原始結構 。

方法一：使用unordered_set存儲元素查詢是否重復

? 有一個招數就是使用unordered_set存儲一下我們的一個鏈表的元素，然后，去用另一個鏈表遍歷查看我們的元素是否在unordered_set種已經出現過了。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode*> sets;// init the sets to get the count;while(headA){sets.insert(headA);headA = headA->next; // go ahead;}while(headB){if(sets.count(headB)){// owns the count, and returns;return headB;}headB = headB->next;}return nullptr;}
};

? 這種方式最直觀，也是筆者的第一反應。

方法2：快慢指針判決

? 下面我們來看快慢指針的辦法進行求解。我們知道，假設A鏈表的長度是a，B鏈表的長度是b，公共部分設成c，那么顯然，我們快慢指針的判別法可以是這樣的：即嘗試兩個指針都走一次A，B鏈表，當走到我們的焦點的時候，我們發現：

A: 走了 a + (b - c)
B: 走了 b + (a - c)

? 我們高興的發現兩個指針走的部署相等，因此實際上，我們完全就讓快慢指針在交點處相等了。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;while(curA != curB){curA = (curA ? curA->next : headB); // 空了咱們去BcurB = (curB ? curB->next : headA); // 空了咱們去A}return curA;}
};

鏈表反轉

給你單鏈表的頭節點 head ，請你反轉鏈表，并返回反轉后的鏈表。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/

? 反轉鏈表比較簡單，我們實際上的難點在于，我們不能立馬修改當前遍歷節點的下一個節點，需要做緩存

class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head || !head->next) return head; // stop with null and onlyListNode* current = head;ListNode* prev = nullptr;ListNode* next_one;while(current){// cached the next onenext_one = current->next;// modify the next one's next to the cur to reversecurrent->next = prev;// restore cachesprev = current;current= next_one;}return prev;}
};

? 就可以看到，我們做的實際上就是簡單的swap操作，沒啥好說的。

判斷回文鏈表

? 給你一個單鏈表的頭節點 head ，請你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。

? 嘛！顯然，咱們沒法逆序遍歷鏈表，有一種偷懶的辦法兄弟們，那就是用一下棧這個特性。我們知道棧是一個經典的FILO結構，我們按照遍歷順序壓棧我們的單鏈表遍歷結果，之后我們只需要再遍歷一下鏈表，跟我們的棧進行對比

class Solution {
public:bool isPalindrome(ListNode* head) {stack<int> caches;ListNode* cached_head = head;while(head){caches.push(head->val);head = head->next;}     while(cached_head){if(cached_head->val != caches.top()){return false;}cached_head = cached_head->next;caches.pop();}return true;}
};

前K系列：找出前K個高頻元素

? 給你一個整數數組 nums 和一個整數 k ，請你返回其中出現頻率前 k 高的元素。你可以按 任意順序 返回答案。

? 其實回答很簡單，那就是第一步是統計我們的元素個數，我們可以使用的是unordered_map來做這個事情，其鍵值對我們采用的是：{元素，個數}鍵值對。之后咱們做的事情就是塞到大根堆進行默認的排序。需要注意的是，咱們的大根堆對pair的排序看的是第一個數大不大，所以咱們往隊列里push我們的東西的時候，是需要我們調換一下鍵值對的順序的。

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> counters; // <nums, count>for(const auto& num : nums){counters[num]++;}// next, we shell check and reordered as prioirty queuepriority_queue<pair<int, int>> pq;for(const auto& each : counters){pq.push({each.second, each.first});}vector<int> result;for(int i = 0; i < k; i++){result.emplace_back(pq.top().second);pq.pop();}return result;}
};

? 可以看到我們的priority_queue自動幫助我們處理排序的事情了。如果是小K個，那么我們只需要換greater<int>就好了

第K系列：使用Ｏ（N）復雜度尋找第K個大小的數字

可以用sort等嘛？

? 不能，因為std::sort是完全快排，實際上復雜度是O(NlogN)，我們需要改進成快速選擇的方式進行改進

class Solution {
public:int partition(vector<int>& nums, int left, int right){int pivot = nums[right];int i = left;for(int j = left; j < right; j++){if(nums[j] <= pivot){swap(nums[i], nums[j]);i++;}}swap(nums[i], nums[right]);return i; // return new pivot}int quick_selection(vector<int>& n, int left, int right, int k_smallest){if (left == right) return n[left];int pivot = partition(n, left, right);if(pivot == k_smallest){return n[pivot];}else if (pivot < k_smallest){// leftreturn quick_selection(n, pivot + 1, right, k_smallest);}else{return quick_selection(n, left, pivot - 1, k_smallest);}}int findKthLargest(vector<int>& nums, int k) {int n = nums.size();int target = n - k; // 第 k 大 → 第 n - k 小return quick_selection(nums, 0, n - 1, target);}
};

---

1. findKthLargest 函數：“化大為小，找對目標”

想象你有一堆撲克牌，現在讓你找出第 3 大的那張牌。

int findKthLargest(vector<int>& nums, int k) {int n = nums.size();// 關鍵一步：把“找第k大”轉換成“找第(n-k)小”int target = n - k; // 例如，有5張牌，找第1大（最大的），就是找第5-1=4小的（也就是索引為4的，如果從0開始數）// 找第3大，就是找第5-3=2小的（也就是索引為2的）return quick_selection(nums, 0, n - 1, target);
}

• 它的任務： 你告訴我，你想要這堆牌里第幾大的牌。
• 它的聰明之處： 它會偷偷地把你的要求“翻譯”一下。比如，如果你說要找第 3 大的牌，它會心想：“哦，這不就是說，在所有牌都排好序之后，從最小的開始數，第 (N?3) 張牌嗎？”（N 是總牌數）。
• 委托任務： 翻譯完之后，它就把這個“找第 N?k 小的牌”的任務，交給下一級的專家 quick_selection 去辦了。

---

2. partition 函數：“分堆、找個好位置”

這個函數是整個算法的“幕后功臣”，它每次的作用是：隨機挑一個“參考牌”，然后把其他牌根據這個參考牌分成兩堆。

int partition(vector<int>& nums, int left, int right)
{int pivot = nums[right]; // 選定最右邊的牌作為“參考牌”（基準值）int i = left;            // i 指針：表示“比參考牌小的牌”的區域的右邊界// j 指針從左邊開始遍歷，但不到right（因為right是參考牌）for(int j = left; j < right; j++){if(nums[j] <= pivot){ // 如果當前牌（nums[j]）比“參考牌”小或者相等swap(nums[i], nums[j]); // 就把這張牌挪到“比參考牌小的區域”里去i++;                     // “比參考牌小的區域”的邊界就往右擴大一格}}// 循環結束后，i 指向的位置，就是所有“比參考牌小的牌”后面緊跟著的位置// 也就是說，i左邊的牌都 <= pivot，i右邊的牌都 > pivot (暫時)swap(nums[i], nums[right]); // 把“參考牌”（nums[right]）放到 i 指向的位置// 這樣，i位置的牌就是新的參考牌，它左邊的都比它小，右邊的都比它大return i; // 返回這個“參考牌”最終所在的位置（索引）
}

• 它的任務： 拿到一堆牌（一個子數組），然后重新整理一下這堆牌。

• 怎么整理：

  1. 它先從這堆牌的最右邊挑一張牌，把它作為**“參考牌” (pivot)**。
  2. 它有一個**“小牌區”的邊界 i**，最開始在最左邊。
  3. 然后它從最左邊開始，一張一張地看牌 (j 遍歷)：
     • 如果它看的這張牌比“參考牌”小（或者一樣大），那么這張牌就應該放在“小牌區”里。它就會把這張牌和“小牌區”邊界 i 上的牌交換一下位置。然后，“小牌區”的邊界 i 就往右移一位。
     • 如果它看的這張牌比“參考牌”大，它就不管，繼續看下一張。
  4. 當所有牌都看完了（j 走到了 right - 1），這時候，從起始位置到 i-1 的所有牌都比“參考牌”小或相等。i 指向的牌和 i 右邊的牌都比“參考牌”大（或者還沒有處理的牌）。
  5. 最后，它會把最開始選定的那張**“參考牌”**（原來在 right 位置）放到 i 所指的位置上。

• 結果： partition 函數執行完后，數組就變成這樣：

  [小于等于參考牌的牌 | 參考牌本身 | 大于參考牌的牌]

  而且，返回的 i 就是這個**“參考牌”最終所在的位置**。這個位置非常重要，因為它告訴我們“參考牌”在整個排序好之后，會處于哪個確切的索引。

---

3. quick_selection 函數：“縮小范圍，直到找到”

這是遞歸尋找目標牌的主管。

int quick_selection(vector<int>& n, int left, int right, int k_smallest){if (left == right) return n[left]; // 如果只剩一張牌了，那這張牌就是答案，直接返回int pivot_index = partition(n, left, right); // 調用 partition，找到“參考牌”的新位置if(pivot_index == k_smallest){// 情況1：運氣真好！“參考牌”的位置正好就是我們要找的第k_smallest小牌的位置！return n[pivot_index]; // 找到了，直接返回這張牌}else if (pivot_index < k_smallest){// 情況2：“參考牌”的位置比我們想找的牌的位置靠左了// 說明我們想找的牌在“參考牌”的右邊那堆牌里return quick_selection(n, pivot_index + 1, right, k_smallest); // 遞歸去右邊那堆牌里找}else{// 情況3：“參考牌”的位置比我們想找的牌的位置靠右了// 說明我們想找的牌在“參考牌”的左邊那堆牌里return quick_selection(n, left, pivot_index - 1, k_smallest); // 遞歸去左邊那堆牌里找}
}

• 它的任務： 在指定的牌堆范圍 (left 到 right) 里，找到“翻譯”后的那個 k_smallest 索引的牌。
• 怎么找：
  1. 基地情況： 如果這堆牌里只剩下一張牌了（left == right），那這張牌肯定就是我們要找的，直接拿走。
  2. 分區： 否則，它會調用 partition 函數，把當前這堆牌重新分一下，得到一個**“參考牌”的新位置 pivot_index**。
  3. 判斷：
     • 正好找到！ 如果這個 pivot_index 恰好就是我們要找的 k_smallest 索引，那太好了！pivot_index 上的那張牌就是答案，直接返回！
     • 找錯了，往右邊找！ 如果 pivot_index 比 k_smallest 小，說明“參考牌”排得太靠左了，我們要找的牌肯定在它的右邊那堆牌里。所以，它會只在 pivot_index + 1 到 right 的范圍里，繼續用同樣的方法找 k_smallest 索引的牌。
     • 找錯了，往左邊找！ 如果 pivot_index 比 k_smallest 大，說明“參考牌”排得太靠右了，我們要找的牌肯定在它的左邊那堆牌里。所以，它會只在 left 到 pivot_index - 1 的范圍里，繼續用同樣的方法找 k_smallest 索引的牌。

---

這個算法的核心思想就是：

1. 我有一堆亂序的牌。
2. 我想找到第 N?k 小的那張牌。
3. 我隨機（這里是選最右邊）挑一張牌作為“參考牌”。
4. 我把所有比“參考牌”小的牌挪到它左邊，所有比它大的牌挪到它右邊。然后把“參考牌”放到它最終該去的位置。
5. 現在“參考牌”的位置確定了。
6. 我就看這個“參考牌”的位置是不是我想要的那個第 N?k 小的索引。
   • 如果是，那我就找到了！
   • 如果不是，我就只去“參考牌”的左邊那堆牌或者右邊那堆牌里繼續找（因為我知道我要的牌肯定在那一堆里），另一堆牌就完全不用管了。
7. 這樣，每次都能排除掉一部分不需要查找的牌，大大提高了效率。

它和快速排序最大的不同是，快速排序要排序兩邊，而快速選擇只排序包含目標元素的那一邊，所以平均情況下比完全排序要快得多。

**

1. 我有一堆亂序的牌。
2. 我想找到第 N?k 小的那張牌。
3. 我隨機（這里是選最右邊）挑一張牌作為“參考牌”。
4. 我把所有比“參考牌”小的牌挪到它左邊，所有比它大的牌挪到它右邊。然后把“參考牌”放到它最終該去的位置。
5. 現在“參考牌”的位置確定了。
6. 我就看這個“參考牌”的位置是不是我想要的那個第 N?k 小的索引。
   • 如果是，那我就找到了！
   • 如果不是，我就只去“參考牌”的左邊那堆牌或者右邊那堆牌里繼續找（因為我知道我要的牌肯定在那一堆里），另一堆牌就完全不用管了。
7. 這樣，每次都能排除掉一部分不需要查找的牌，大大提高了效率。

它和快速排序最大的不同是，快速排序要排序兩邊，而快速選擇只排序包含目標元素的那一邊，所以平均情況下比完全排序要快得多。