參考資料

代碼隨想錄 https://programmercarl.com/
LeetCode https://leetcode.cn/

一 數(shù)組

1.1 二分查找

• 前提
  有序數(shù)組，元素唯一（有重復(fù)元素，使用二分查找法返回的元素下標(biāo)可能不是唯一）
• 思想
  • 定義 target 是在一個(gè)在左閉右閉的區(qū)間里，也就是[left, right]
  • while (left <= right) 要使用 <= ，因?yàn)閘eft == right是有意義的，所以使用 <=
  • if (nums[middle] > target) right 要賦值為 middle - 1，因?yàn)楫?dāng)前這個(gè)nums[middle]一定不是target，那么接下來(lái)要查找的左區(qū)間結(jié)束下標(biāo)位置就是 middle - 1
  • 若要通過二分查找確定插入位置，則最后需判斷nums[mid] > target，若是則mid為結(jié)果，若不是則mid + 1為結(jié)果
• 代碼

  // https://leetcode.cn/problems/binary-search/description/
  class Solution {public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left)/2;if (nums[mid] == target) {return mid;} if (nums[mid] < target) {left = mid + 1;}if (nums[mid] > target) {right = mid - 1;}}return -1;}
  };
  

1.2 移除元素

• 前提
  O(1)空間，不要求保留原順序
• 思想
  將要?jiǎng)h除的元素用數(shù)組最后面的元素進(jìn)行替換
• 代碼

  // https://leetcode.cn/problems/remove-element/description/
  class Solution {public:int removeElement(vector<int>& nums, int val) {int left = 0, right = nums.size() - 1;while (left <= right) {if (nums[left] == val) {nums[left] = nums[right];right --;} else {left ++;}}// [0, right]為需要保留的元素，長(zhǎng)度位right + 1return right + 1;}
  };
  

1.3 長(zhǎng)度最小的子數(shù)組

• 前提
  O(1)空間，子數(shù)組連續(xù)
• 思想
  定義區(qū)間[left, right)，當(dāng)區(qū)間和sum < target時(shí)移動(dòng)right，相反則記錄當(dāng)前區(qū)間長(zhǎng)度right - left并移動(dòng)left，直到right > 數(shù)組總長(zhǎng)度時(shí)結(jié)束循環(huán)
• 代碼

  // https://leetcode.cn/problems/minimum-size-subarray-sum/description/
  class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0, right = 0; // [left, right)int sum = 0, ans = 0;while (right <= nums.size()) {if (sum < target) {// 此時(shí)right指針已達(dá)到末尾，且子數(shù)組和小于target// 結(jié)束循環(huán)if (right ==  nums.size()) {break;}sum += nums[right];right ++;} else {int len = right - left;if (ans == 0) {ans = len;} else {ans = ans > len ? len : ans;}sum -= nums[left];left ++;}}return ans;}
  };
  

1.4 螺旋矩陣

• 思想
  關(guān)鍵在于方向的轉(zhuǎn)換，并且需要記錄行和列上還有多少是沒有遍歷過的，每次方向轉(zhuǎn)換都需要減少一個(gè)待遍歷的行或列
• 代碼

  // https://leetcode.cn/problems/spiral-matrix-ii/description/
  class Solution {
  public:vector<vector<int>> generateMatrix(int n) {// direction = 0 => 從左到右，direction = 1 => 從上到下// direction = 2 => 從右到左，direction = 3 => 從下到上int direction = 0;int row_count = n, col_count = n;int i_index = 0, j_index = 0; int num = 1;// 初始化結(jié)果vector<vector<int>> res;for (int i = 0; i < n; i ++) {vector<int> r(n);res.push_back(r);}while (num <= n * n) {// printf("direction = %d\n", direction);switch(direction) {case 0:// printf("case0, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < col_count; i ++) {res[i_index][j_index] = num;j_index ++;num ++;}i_index ++;j_index --;row_count --;break;case 1:// printf("case1, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < row_count; i ++) {res[i_index][j_index] = num;i_index ++;num ++;}i_index --;j_index --;col_count --;break;case 2:// printf("case2, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < col_count; i ++) {res[i_index][j_index] = num;j_index --;num ++;}j_index ++;i_index --;row_count --;break;case 3:// printf("case3, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < row_count; i ++) {res[i_index][j_index] = num;i_index --;num ++;}i_index ++;j_index ++;col_count --;break;}direction ++;direction = direction % 4;// for (int i = 0; i < n; i ++) {//     for (int j = 0; j < n; j ++) {//         cout << res[i][j];//     }//     cout << endl;// }}return res;}
  };
  

1.5 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

• 代碼

  // https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
  class Solution {
  public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> ret(2, -1);// 有效區(qū)間[left, right]int left = 0, right = nums.size() - 1, mid;bool tag = false;while (left <= right) {mid = left + (right - left)/2;if (nums[mid] == target) {tag = true;break;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}if (!tag) return ret;// cout << left << " " <<  mid << " " << right  << endl;// [left, mid - 1] 中尋找小于target的元素int l = left, r = mid - 1, from = left;while (l <= r) {int m = l + (r - l)/2;if (nums[m] < target) {from = m;break;} else {r = m - 1;}}// 向右找到第一個(gè)等于target的元素while (nums[from] != target) from ++;// [mid + 1, right] 中尋找大于target的元素l = mid + 1;r = right;int to = right;while (l <= r) {int m = l + (r - l)/2;if (nums[m] > target) {to = m;break;} else {l = m + 1;}}// 向左找到第一個(gè)等于target的元素while (nums[to] != target) to --;ret[0] = from;ret[1] = to;return ret;}
  };
  

二 鏈表

2.1 移除鏈表元素

• 思想
  移除鏈表中指定元素的關(guān)鍵在于找到被移除元素的上一個(gè)節(jié)點(diǎn)
• 代碼

  // https://leetcode.cn/problems/remove-element/description/
  class Solution {
  public:ListNode* removeElements(ListNode* head, int val) {// 定義虛擬頭節(jié)點(diǎn)，不需要對(duì)第一個(gè)節(jié)點(diǎn)進(jìn)行特殊判斷ListNode *dummy_head = new ListNode(-1, head);// 定義pre和cur，方便刪除元素ListNode *pre = dummy_head;ListNode *cur = dummy_head->next;while (cur != NULL) {if (cur->val == val) {pre->next = cur->next;cur = pre->next;} else {pre = pre->next;cur = cur->next;}}return dummy_head->next;}
  };
  

2.2 設(shè)計(jì)鏈表

• 思想
  • 設(shè)計(jì)虛擬頭節(jié)點(diǎn)可以簡(jiǎn)化對(duì)于第一個(gè)節(jié)點(diǎn)的操作
  • 由題可知，大部分操作都需要找到下標(biāo)的為index的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，因此設(shè)計(jì)了getPre(int index)函數(shù)
  • 設(shè)計(jì)尾節(jié)點(diǎn)可以降低addAtTail的時(shí)間復(fù)雜度，但是在鏈表變化時(shí)需要對(duì)其進(jìn)行維護(hù)
• 代碼

  // https://leetcode.cn/problems/design-linked-list/
  class MyListNode {    
  public:int val;MyListNode *next;MyListNode(int val, MyListNode *next) {this->val = val;this->next = next;}
  };class MyLinkedList {
  private:MyListNode *dummy_head;MyListNode *tail;int size;// 找到下標(biāo)為index的上一個(gè)節(jié)點(diǎn)MyListNode *getPre(int index) {MyListNode *node = dummy_head;while (index > 0) {node = node->next;index --;}return node;}
  public:MyLinkedList() {dummy_head = new MyListNode(-1, NULL);tail = NULL;size = 0;}int get(int index) {if (index >= size) {return -1;}MyListNode *node = getPre(index);return node->next->val;}void addAtHead(int val) {MyListNode *node = new MyListNode(val, NULL);node->next = dummy_head->next;dummy_head->next = node;if (tail == NULL) {tail = node;}size ++;}void addAtTail(int val) {if (tail == NULL) {addAtHead(val);   } else {tail->next = new MyListNode(val, NULL);tail = tail->next;size ++;}}void addAtIndex(int index, int val) {// 如果 index 比長(zhǎng)度更大，該節(jié)點(diǎn)將 不會(huì)插入 到鏈表中if (index > size) {return ;}// 如果 index 等于鏈表的長(zhǎng)度，那么該節(jié)點(diǎn)會(huì)被追加到鏈表的末尾if (index == size) {addAtTail(val);} else {MyListNode *node = new MyListNode(val, NULL);MyListNode *p = getPre(index);node->next = p->next;p->next = node;size ++;}}void deleteAtIndex(int index) {if (index >= size) {return ;}MyListNode *p = getPre(index);// 要?jiǎng)h除的節(jié)點(diǎn)為尾節(jié)點(diǎn)，需要修改tailif (p->next == tail) {p->next = NULL;tail = p;} else {p->next = p->next->next;                }size --;}
  };
  

2.3 反轉(zhuǎn)鏈表

• 思想
  • 為原鏈表添加虛擬頭節(jié)點(diǎn)，刪除節(jié)點(diǎn)時(shí)不需要維護(hù)頭節(jié)點(diǎn)，簡(jiǎn)化操作（新鏈表的虛擬頭節(jié)點(diǎn)同理）
  • 反轉(zhuǎn)鏈表主要分為節(jié)點(diǎn)斷開和節(jié)點(diǎn)接入，分為兩部分實(shí)現(xiàn)，可避免思路不清晰，導(dǎo)致鏈表成環(huán)（q->next = NULL可刪除）
• 代碼

  // https://leetcode.cn/problems/reverse-linked-list/
  class Solution {
  public:ListNode* reverseList(ListNode* head) {// 為原鏈表添加虛擬頭節(jié)點(diǎn)，方便節(jié)點(diǎn)的刪除ListNode *dummy_head = new ListNode(-1, head);ListNode *p = dummy_head;// 為新鏈表添加虛擬頭節(jié)點(diǎn)ListNode *new_head = new ListNode(-1);while (p->next != NULL) {// 把節(jié)點(diǎn)從原鏈表斷開ListNode *q = p->next;p->next = q->next;q->next = NULL;// 把節(jié)點(diǎn)接入到新鏈表的頭部q->next = new_head->next;new_head->next = q;}return new_head->next;}
  };
  

2.4 兩兩交換鏈表中的節(jié)點(diǎn)

• 思想
  • 多定義變量可一定程度上簡(jiǎn)化操作（變量不用🪙）
• 代碼

  // https://leetcode.cn/problems/swap-nodes-in-pairs/description/
  class Solution {
  public:ListNode* swapPairs(ListNode* head) {ListNode *dummy_head = new ListNode(-1, head);ListNode *p = dummy_head;while (p->next != NULL && p->next->next != NULL) {// a和b為要進(jìn)行交換的節(jié)點(diǎn)，c為后面的節(jié)點(diǎn)ListNode *a = p->next;ListNode *b = a->next;ListNode *c = b->next;// 將a和b從原鏈表中斷開（為了方便理解，可省略）p->next = NULL;a->next = NULL;b->next = NULL;// 重新拼接p->next = b;b->next = a;a->next = c;p = a;}   return dummy_head->next;}
  };
  

2.5 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

• 思想
  先讓fast跑n步，然后slow和fast再一起跑，fast到達(dá)末尾時(shí)，slow剛好為倒數(shù)第n+1個(gè)節(jié)點(diǎn)
• 代碼

  // https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
  class Solution {
  public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *dummy_head = new ListNode(-1, head);ListNode *fast = dummy_head;ListNode *slow = dummy_head;while (n > 0) {fast = fast->next;n --;}while (fast->next != NULL) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummy_head->next;   }
  };
  

2.6 鏈表相交

• 代碼

  // https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
  class Solution {
  public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 計(jì)算鏈表A和B的節(jié)點(diǎn)數(shù)int a_count = 0;int b_count = 0;ListNode *p = headA;while (p != NULL) {a_count ++;p = p->next;}p = headB;while (p != NULL) {b_count ++;p = p->next;}// 若兩個(gè)鏈表相差sub個(gè)節(jié)點(diǎn)，則讓長(zhǎng)的鏈表先跑sub步while (a_count > b_count) {headA  = headA->next;a_count --;}while (b_count > a_count) {headB = headB->next;b_count --;}// 兩個(gè)鏈表同時(shí)往前，此時(shí)遇到的第一個(gè)相同節(jié)點(diǎn)即為結(jié)果while (headA != headB) {headA = headA->next;headB = headB->next;}return headA;}
  };
  

2.7 環(huán)形鏈表II

• 思想
  • 通過快慢指針法確定鏈表是否存在環(huán)，并找到環(huán)中的任意一個(gè)節(jié)點(diǎn)
  • 遍歷環(huán)，直至將環(huán)中的所有節(jié)點(diǎn)添加到set集合中
  • 從head開始遍歷，當(dāng)節(jié)點(diǎn)存在與set集合中時(shí)，即為環(huán)的入口節(jié)點(diǎn)
• 代碼

  // https://leetcode.cn/problems/linked-list-cycle-ii/
  class Solution {
  public:ListNode *detectCycle(ListNode *head) {// 通過快慢指針法確定鏈表是否存在環(huán)，并找到環(huán)中的任意一個(gè)節(jié)點(diǎn)ListNode *fast = head;ListNode *slow = head;bool tag = false;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {tag = true;break;}}if (tag) {// 此時(shí)fast和slow都是環(huán)中的節(jié)點(diǎn)，遍歷環(huán)，直至將環(huán)中的所有節(jié)點(diǎn)添加到`set`集合中set<ListNode*> st;while (st.find(fast) == st.end()) {st.insert(fast);fast = fast->next;}// 從`head`開始遍歷，當(dāng)節(jié)點(diǎn)存在與`set`集合中時(shí)，即為環(huán)的入口節(jié)點(diǎn)while (st.find(head) == st.end()) {head = head->next;}return head;} else {return NULL;}}
  };
  

• 最優(yōu)解法

  // https://leetcode.cn/problems/linked-list-cycle-ii/solutions/12616/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
  class Solution {
  public:ListNode *detectCycle(ListNode *head) {ListNode *fast = head;ListNode *slow = head;bool tag = false;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {tag = true;break;}}if (!tag) return NULL;fast = head;while (fast != slow) {fast = fast->next;slow = slow->next;}return fast;}
  };
  

三 哈希表

3.1 有效的字母異位詞

• 思想
  • 兩個(gè)字符串長(zhǎng)度不同，直接返回false
  • 遍歷字符串s，使用map統(tǒng)計(jì)第一個(gè)字符串s中每各字符出現(xiàn)的次數(shù)
  • 遍歷字符串t，若字符不存在于map中，則返回false；存在則進(jìn)行減操作，當(dāng)字符次數(shù)減為0時(shí)，從map移除
  • map為空則表示兩個(gè)字符串是字母異位詞
  • （進(jìn)階）由于題目中說明字符串都由小寫字母組成，那么我們可以將所有字符映射到長(zhǎng)度為26的數(shù)組，簡(jiǎn)化操作
• 代碼（基礎(chǔ)解法）

  // https://leetcode.cn/problems/valid-anagram/description/
  class Solution {
  public:bool isAnagram(string s, string t) {if (s.length() != t.length()) {return false;}map<char, int> mp;for (int i = 0; i < s.length(); i ++) {char key = s[i];auto it = mp.find(key);if (it != mp.end()) {it->second += 1;} else {mp.insert(pair<char, int>(key, 1));}}for (int i = 0; i < t.length(); i ++) {char key = t[i];auto it = mp.find(key);if (it == mp.end()) {return false;} else {if (it->second == 0) {return false;} else if (it->second == 1) {mp.erase(it);} else {it->second -= 1;}}}return mp.empty();}
  };
  

• 最優(yōu)解法

  // https://leetcode.cn/problems/valid-anagram/description/
  class Solution {
  public:bool isAnagram(string s, string t) {if (s.length() != t.length()) {return false;}vector<int> mp(26, 0);for (char c : s) {mp[c - 'a'] ++;}for (char c : t) {mp[c - 'a'] --;}for (int c : mp) {if (c != 0) return false;}return true;}
  };
  

3.2 兩個(gè)數(shù)組的交集

• 代碼

  // https://leetcode.cn/problems/intersection-of-two-arrays/
  class Solution {
  public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;set<int> st;// 將nums1的所有元素添加到set中，會(huì)自動(dòng)去重for (int num : nums1) {st.insert(num);}// 遍歷nums2，判斷元素是否存在st中，存在則是兩個(gè)數(shù)組的交集，添加到結(jié)果數(shù)組ret中// 為防止元素重復(fù)添加，需要將其從st中移除for (int num : nums2) {if (st.find(num) != st.end()) {ret.push_back(num);st.erase(num);}}return ret;}
  };