前言

這篇用來記錄刷leetcode 的各類主題，以及不同情境下要用的對應解題策略是哪些，也連接到之前所做的筆記跟部落格

Roadmap

這邊是參考 NeetCode 官網的roadmap 按照不同主題進行刷題的

Big-O

https://www.bigocheatsheet.com/

Two Pointers

Two pointer 如果出現在陣列題目中，代表兩個索引(index)，如果出現在 Linked List題目中，代表兩個不同的指標。但核心目的都是一樣的，透過移動pointer位置來減少溶於計算提高效率。

常見的Two pointer類型：

  • 反向指針: 一個指向頭部一個指向尾部，逐漸向中間靠攏，檢查回文, 兩數之和通常很常用這種類型
  • 快慢指針: 一個指針較快，另一個指針較慢，可以用於檢測Linked List 中是否有環。

某些情況下會搭配 Sliding Windows 來去動態調整子陣列的大小，Ex.右指針擴展Windows，左指針收斂windows。以下整理常見的 Two Pointer 使用時機：

  1. $O(N^2)$ 降低成 $O(N)$,題目要求降低複雜度
  2. 輸入資料是有序的
  3. 題目要求將不同索引作比較
  4. 題目要求要在不同索引間交換
  5. 題目要求將陣列分區

注意，如果要用反向指針逐步收斂問題範圍，會有條件，那就是資料必須是已排序的
但如果題目是要搭配 Sliding Windows 或者linked list 則資料不一定要排序

Sliding Window

Sliding Window 算是 Two Pointer 的其中一種變化，可以透過兩個指標 left 以及 right 來去建立窗口(Window)， 通常題目會要求返回特定條件的最大或最小子範圍，利用 [Left, Right] 夾出來的 Window 來在運算過程中滑動(收縮和擴展)來找出最佳的範圍。

三個關鍵步驟

  1. Expand out window
  2. Meet the condition and process the window
  3. Shrink the window

通常會由 right 指針去往外擴展，一旦滿足條件時，則可透過增加 left 來收斂 window，其解題邏輯如下：

1
2
3
4
5
6
7
void slidingWindow(){
  // Iterate through the input
    // Expand out window
    // If meet the condition to stop expansion
        // process the window
        // contract the window
}

在 sliding window 題目中一定會出現三種變數:

  1. Window 邊界: left, right
  2. 紀錄條件的變數，看是否到達expansion 停止條件
  3. 紀錄回傳值的變數

解題流程

  1. 定義停止擴展window的條件：先明確在什麼情況下需要停止擴展窗口
  2. 擴展window直到滿足條件：在擴展window之前，先處理當前 right 指標所指向的元素
  3. 當滿足停止擴展的條件時，處理當前window：在滿足條件時，針對當前window進行需要的處理
  4. 收縮當前window：在收縮window之前，先處理當前 left 指標所指向的元素
  5. 處理邊界情況：確保對特殊情況（例如空輸入、極端值等）進行適當處理

題目

參考：
https://shannonhung.github.io/posts/lecture-two-pointer-and-sliding-window
https://medium.com/@timpark0807/leetcode-is-easy-sliding-window-c44c11cc33e1

Hash Table

基本用法

1
2
3
4
5
6
7
8
9
10
#include <unordered_map>
#include <string>
using namespace std;

unordered_map<stin, int> dp ={{"Kevin", 1},{"Shannon", 2},{"Roger", 3}}; // Initialization
dp["Alan"] = 4; // Insertion, overwriting existing value
dp.insert(pair("Alan", 4)); // If key exists, return failure
dp.erase(dp.begin()); // Erase element
dp.erase("Alan"); //Erase element
dp.erase(dp.find("Shannon"),dp.end()); // Erase a range of elements

迭代存取 unordered_map 元素

1
2
3
4
5
6
7
for(const auto &n : dp){
  cout << "name:" << n.first << ", id:" << n.second << endl;
}

for(auto it=dp.begin(); it!=dp.end(); ++it){
  cout << "name:" << (*it).first << ",id:" << (*it).second << endl;
}

查找特定值

1
2
3
if(dp.find("KEY")!=dp.end()){
  return false;
}

清空 unordered_map 容器

1
dp.clear();

參考：https://shengyu7697.github.io/std-unordered_map/

使用時機1: 用於快速存取元素

一旦建立好 Hash Table 就可以用 $O(1)$ 的時間複雜度來存取元素

使用時機2: 比對無序資料

在 Python 中實踐 Hash Table的方式就是 Dictionary，而在C++中則是透過 unordered_map，他們的特點就是都是 Key-Value Pair，這代表他們就是一個無序元素映射的集合。因此在比較無序資料時也會用到 Hash Table，像是可以用來記錄特定單字在某個文章出現的頻率那也可以使用 Hash Table

使用時機3: Deep Copy

如果今天對於 Linked List 的結構有Deep Copy 的需求 (Ex. 錄製出一個一模一樣的Linked List結構)，則會需要儲存舊節點的鏈結關係以及新節點的鏈結關係。這時就可以用 Hash Table 來去做映射。

1
unordered_map <Node*, Node*> randomMap;

unordered_map vs unordered_set

1
2
unordered_map <int, int> umap;
unordered_set <int> uset;

從宣告上就可以看出差異， unordered_map 會是 Key-Value Pair 然而 unordered_set 會只有 Key 或 value，總之他並不是 pair，也並不能儲存映射關係。 兩者的共同點就是都是無序的 ，並且實踐都是基於 Hash Table，因此 unordered_set中的元素都會是唯一的

以下是 unordered_map 和 unordered_set 在解 LeetCode 題目時的使用時機整理：

功能/特性 unordered_map unordered_set
結構定義 雜湊表存儲鍵值對（Key-Value Pair） 雜湊表存儲唯一的鍵（Key）
典型使用情境 當需要同時儲存一個值（Value）與其對應的鍵（Key）時，例如計數、鍵值對查詢 當只需要快速查詢某元素是否存在，或需要儲存唯一元素集合時，例如去重、檢查存在性
插入/刪除/查詢操作時間複雜度 平均 $ O(1) $，最差 $ O(n) $ 平均 $O(1)$，最差 $O(n)$
重點功能 - 可用於統計出現次數（如頻率計數）。
- 快速通過鍵查詢值		 - 快速判斷元素是否存在。
- 快速存儲唯一元素（無需額外邏輯進行去重）
典型應用場景 1. 頻率計數：統計字元、數字或其他資料的出現次數，例如異位詞檢查、子陣列和問題
2. 映射查詢：需要通過鍵快速找到值
3. 分組：按某些條件將資料分組並存儲對應的值		 1. 集合操作：判斷某元素是否存在，例如兩數和問題
2. 去除重複：快速生成唯一元素集合，例如找出數組中的唯一值
常見 LeetCode 題目範例 - Two Sum (#1)：用於記錄目標數字的補數和其索引
- Group Anagrams (#49)：統計異位詞分組		 - Contains Duplicate (#217)：檢查數組中是否存在重複值
- Intersection of Two Arrays (#349)：找出兩數組交集
注意事項 - 若只需要檢查元素存在性，使用 unordered_set 更高效，避免存儲多餘的值 - 若需要儲存並操作鍵對應的值，應使用 unordered_map，unordered_set 無法完成此需求

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <unordered_set>
#include <vector>
using namespace std;

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> st;
    for (int num : nums) {
        if (st.find(num) != st.end()) {
            return true;
        }
        st.insert(num);
    }
    return false;
}

Stack

Stack 筆記整理： 介紹如何實作Stack，以及一些Stack STL 的基本操作

使用時機1: LIFO 問題

像是 括號匹配問題(Parentheses) {()} 這種檢查括號是否閉合的問題就是後進先出(LIFO)的問題，可以由左至右將左括號依序 Push 進入 Stack，碰到右括號就 Pop 出來看是否匹配。或是像用相對路徑存取檔案的這種題目，像是 /var/www/html 這種 檔案路徑的情境題 也很適合用 Stack 去做，先 push 進先前的目錄，而如果要從子目錄移動到上一層，則也需要先將子目錄 Pop 出來，這也會是 LIFO 的情境。

Queue

Queue 筆記整理: 介紹怎麼實作Queue，並且介紹Queue STL 的基本操作

使用時機1: FIFO 問題

如果題目情境很講求順序，例如系統接收請求的順序這種 FIFO的問題，就很適合用到Queue，但我目前並未做到這類的 Queue題目，只有類似資料結構實作題目

Linked List

Linked List 筆記整理 當時主要是用C來進行實作，但是C與C++在Linked List實踐邏輯中其實一樣，語法稍有差異而已，但不太影響解題

建立節點

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct ListNode {
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {};
    ListNode(int a): val(a), next(nullptr) {};
    ListNode(int a, ListNode *node): val(a), next(node) {};
} Node;

int main(){
   Node node1(4);
   Node node2(3, &node1);
   Node node3(2, &node2);
   Node node4(1, &node3);
  // Print the list:  1->2->3->4->NULL
}

使用時機1. Two Pointer

當需要遍歷Linked List，並且需要快速找到特定節點或結構時，快慢指針可以在一次遍歷中完成查找，適合處理效率要求較高的問題，例如尋找中間節點或判斷是否有循環。或者今天需要比較或操作多個指針時，雙指針可以用來實現倒數第 N 個節點的定位，或在兩條list間進行同步操作

使用時機2. Dummy Head

通常如果要新增或刪除節點，抑或是頻繁的操作頭節點，dummy head 就會試一種簡化操作的基礎技巧，也可以用來避免特殊判斷

使用時機3. 反轉與結構轉換

處理single Linked List反轉、旋轉等結構轉換相關的問題，或是將其他資料結構轉換成linked list

使用時機4. 排序與合併

處理Linked List的合併、重排和排序問題

使用時機5. 特殊指標處理

處理Linked List中帶有隨機指針或其他特殊結構的問題

使用時機6. 刪除重複節點

刪除Linked List中多餘或重複的節點

Tree

Tree 筆記整理-基本
Tree 筆記整理-進階

Tree 的建構

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;

class TreeNode{
    public:
        int val;
        TreeNode *left, *right;
        TreeNode(): val(0), left(nullptr), right(nullptr){};
        TreeNode(int x): val(x), left(nullptr), right(nullptr){};
        TreeNode(int x, TreeNode *lnode, TreeNode *rnode): val(x), left(lnode), right(rnode){};
    
    friend class BT;
};
class BT{
    public:
        TreeNode *root;
        
        BT():root(0) {};
        BT(TreeNode* node): root(node){};
        
        //member functions;
        // void dfs(TreeNode *root);
};
int main() {
    
    TreeNode *nodeA = new TreeNode(1);
    TreeNode *nodeB = new TreeNode(2);
    TreeNode *nodeC = new TreeNode(3);
    TreeNode *nodeD = new TreeNode(4);
    TreeNode *nodeE = new TreeNode(5);
    TreeNode *nodeF = new TreeNode(6);
    
    nodeA -> left = nodeB;
    nodeA -> right = nodeC;
    nodeB -> left = nodeD;
    nodeC -> left = nodeE;
    nodeC -> right = nodeF;
    
    BT T(nodeA);  
    return 0;
}

BFS

又稱 Level-Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BT::bfs(TreeNode *head){
  queue<TreeNode*> q;
  q.push(head);

  while(!q.empty()){
    TreeNode *current = q.front();
    q.pop();
    
    cout << current->val << " ";
    if(current->left!=nullptr) q.push(current->left);
    if(current->right!=nullptr) q.push(current->right);

  }
}

DFS

前序(Preorder)

中序(Inorder)

後序(Postorder)

Graph

Graph 筆記整理-1
Graph 筆記整理-2

Graph 主要由節點(vertex, node)跟邊(edge)構成，基本上有分成有向跟無向圖，還有一些特性像是是否是連接(connected) 以及是否有環(circle) 存在。 圖的題目類型通常會是給定一個2D陣列要你去求數量或是面積還有路徑，或者有些會給 Adjacency Matrix (List) 來告訴你節點的連接關係。目前學到的走訪方式有: DFS, BFS (後續好像還有 Topological Sort)

DFS BFS
適用範圍 有向圖、無向圖 有向圖、無向圖
用途 找路徑(不一定最短) 找最短路徑

無向圖

(1) 找出陣列中的 Connected Components
可使用 DFS, BFS 在走訪過程中透過 counter 來記錄數量，這種題目也會有其他變形題目

(2) 找出最短路徑

  • LeetCode#286. Walls and Gates 這題需要透過 BFS 走訪網格，並且直接將距離更新到網格中，這題的bfs 會優先將搜尋起點(閘門)推入Queue中去解

Recursion

Recursion 和 Backtracking 筆記整理

使用情境1: 排列組合

使用情境2: 子集

使用情境3: 迴文

Binary Search

題目可能會給陣列或字串，然後要做的事就是要先定義出左右兩側邊界以及中間值，

框架會像是下面這樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int left = <MIN_VALUE>;
int right = <MAX_VALUE>;

// left ~ mid ~ right
while(left <= right){
  int mid = left + (right-left) /2;
  
  if(<VALID>){
    // 將範圍收窄成陣列左半邊
    // left ~ mid-1
    right = mid -1;
  }
  else{
    //將範圍收窄成陣列右半邊
    // mid +1 ~ right
    left = mid +1;
  }
}

常見題目

  • LeetCode#875. Koko Eating Bananas: 這題主要是透過先定義出最大跟最小吃香蕉的速度，然後透過 Binary Search 來去挑選吃相較的速度值，再去透過其他函數驗證這個值是否能夠在時間內吃完香蕉。接著會去收窄範圍，最終得出的吃香蕉速度就會是最小的。

Heap

Dynamic Programming

DP 筆記整理 整理了Dynamic Programming 的解題邏輯，跟問題背景會是怎樣的， DP會是最佳化解答的好工具!

判斷：1. 大量重複子問題, 2. 解決所有子問題，可以得到整體問題的最最佳化答案 這時候就可以先找出題目的遞迴關係式(暴力解)，接著再透過 Memoization進行最佳化，或者如果透過Iteration 的方式直接提出最佳解。

使用情境1: 選與不選的問題

對於每個元素，都可以選或不選，藉由多種選或不選的組合，可以找出正確結果，但包含了大量的重複計算

其中還包括許多變形，像是股票交易的題目

使用情境2: 迴文系列問題

這類題目通常在遞迴函數之外還需要額外定義的 **用於檢查回文的函數 checkPalindrome**，通常會將最佳化的 dp 陣列用於這個函數，來避免大量重複計算，如果直接用 reverse() 會是較高的複雜度，通常會透過 Two Pointer 的方式來去實踐回文檢查

Example

1
2
3
4
5
6
7
8
 while(left < right){
    if(s[left] != s[right]){
        return false;
    } 
    left++;
    right--;
}
return true;

常見演算法