---
# System prepended metadata

title: Leetcode Notes
tags: [Public]

---

<h1>
    Topic
</h1>

[TOC]

<h2>
    Best Practice Qeustions
</h2>

https://www.techinterviewhandbook.org/best-practice-questions/

# Array
[<h3>Leetcode : Array 1. Two Sum</h3>](<https://leetcode.com/problems/two-sum/description/>)
```cpp=
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // int length = nums.size();
        // vector<int> ans;
        // // C語言寫法, sizeof() -> 是用來查看 variable size
        // // size_t size = sizeof(nums) / sizeof(nums[0]);
        // for(int i=0; i<length; i++){
        //     for(int j=length-1; j>i; j--){
        //         if(nums[i] + nums[j] == target){
        //             ans.push_back(i);
        //             ans.push_back(j);
        //         }
        //     }
        // }
        // return ans;

        unordered_map<int, int> mm;
        for(int i=0; i<nums.size(); i++){
            int complement = target - nums[i]; // 9-2=7, complement=7; 9-7=2, complement=2
            if(mm.find(complement) != mm.end()){
                return {i , mm[complement]};
            }
            mm[nums[i]] = i; // mm[2]=0, mm[7]=1
        }
        return {};
    }
};
```
>在 C++ 中，end() 是一個成員函數，通常用於標識容器中的末尾位置。
對於 std::unordered_map，end() 傳回一個迭代器，指向哈希表的末尾位置。
它不指向任何有效的元素，通常被用來判斷迭代器是否已經達到容器的末端。
`if(mm.find(complement) != mm.end())`

[<h3>Leetcode : Array 15. 3Sum</h3>](<https://leetcode.com/problems/3sum/description/>)

* 首先可以先將 nums , 這樣可以比較輕鬆的去找到重複的元素
* 再來可以使用 **`雙指標（two pointers）`** 的方式來做
    * 我們現在要找出 `nums[left] + nums[right] == target`, 這時第一個當 `target`
        > `sum = nums[left] + nums[right]`
    * 如果我們發現  `sum < target`：代表 **左邊太小** `→ left++`
    * 如果我們發現  `sum > target`：代表 **右邊太大** `→ right--`
    * 若陣列 **沒排序**，根本無法判斷該往左還往右，就無法使用雙指標的方式
* 接下來每個元素都會當一次 `target`
    * 在一開始我們要先檢查說這次的 `target` 是否跟上次一樣, 如果是就 `continue`
* 然後要先算出 `target` 是多少, 再將 `左指標` 跟 `右指標` 定義好
    * while 的結束條件就是 `左指標 > 右指標`
        * 一開始一樣先算出 `sum` 是多少, 如果等於 target 就找到一個答案了
        * **這邊要注意的是他們都一樣要去檢查 `left` 和 `right` 移動到下一個時是否重複**
        * 然後如果 `sum < target` 時, 就代表 left 要往右走一格, 反之...
            * 另外你可能會想說為甚麼 `sum` `> 或 <` `target` 時不需要檢查是否相同, 這是因為他並沒有被加進正確答案中, 所以到下一次時他一樣是錯的, 所以無所謂
* 最後回傳 `answer` 就好了


```cpp=
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> answer;
        for(int i=0; i<nums.size(); i++) {
            if(i > 0 && (nums[i] == nums[i - 1])) continue;
            int target = -nums[i]; // i + j + k = 0 ----> i + j = -k
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right) {
                int sum = nums[left] + nums[right]; 
                if(target == sum) {
                    answer.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    while(left < right && (nums[left] == nums[left - 1])) left++;
                    while(left < right && (nums[right] == nums[right + 1])) right--;
                } else if(sum < target) {
                    left++;
                } else if(sum > target) {
                    right--;
                }
            }
        }
        return answer;
    }
};
```
>答案要求三數和為零, 
nums[i] + nums[j] + nums[k] = 0 會等於 nums[j] + nums[k] = -nums[i]
所以 int target = -nums[i], 所以 sum + target = 0

[<h3>Leetcode : Array 20. Valid Parentheses</h3>](<https://leetcode.com/problems/valid-parentheses/>)

```cpp
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> umap = {
            {'[', ']'},
            {'{', '}'},
            {'(', ')'},
        };

        stack<char> charStack;

        for(char c : s) {
            if(umap.count(c)) {
                charStack.push(c);
            } else {
                if(charStack.empty() || (umap[charStack.top()] != c)) {
                    return false;
                }
                charStack.pop();
            }
        }
        return charStack.empty();
    }
};
```

* 一開始先使用 `unordered_map` 先定義好所有的左右括號
* 再來開始處理, 這邊用 stack 來做, 因為要處理 "`{[}]`" 的問題, 需要用到先進後出的特性
    * `charStack.empty()` 用來檢查說左括號在不在, 如果只有對應右括號就錯
    * `umap[charStack.top()] != c` 這邊如果最上面不是對應左括號, 就會是套嵌像是 "`{(}`"
    * 那都沒有這兩種情況代表合法, 就會把它 `pop` 掉, 到最後 `stack` 是空的就是都合法

[<h3>Leetcode : Array 53. Maximum Subarray</h3>](<https://leetcode.com/problems/maximum-subarray/>)

```cpp
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int curSum = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            curSum = max(nums[i], curSum + nums[i]);
            maxSum = max(maxSum, curSum);
        }
        return maxSum;
    }
};
```

* 這邊要用兩個變數來記錄
    * 1. 目前子陣列的累計和 (`curSum`)
    * 2. 目前遇過最大的子陣列累計和 (`maxSum`)
* 目前子陣列的累計和
    * `curSum = max(nums[i], curSum + nums[i])`
        * 這邊如果遇到的 `num > 目前子陣列累計和`, 代表前面的會拖類後面的就不要了
        就會直接將遇到的 `num` 當成開始的
    * `maxSum = max(maxSum, curSum)`
        * 這邊就要跟目前遇到的子陣列來去比較, 要去記錄每次遇到的最大子陣列
* 最後 `maxSum` 就會是答案

[<h3>Leetcode : Array 121. Best Time to Buy and Sell Stock</h3>](<https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/>)
```cpp=
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int maxProfit = 0;
        int minPrice = prices[0];
        for(auto& price : prices) {
            int profit = price - minPrice;
            if(price < minPrice) minPrice = price;
            maxProfit = max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
};
```

* `minPrice` 記錄「過去看過的最低價」（可能是買入日）
* `price - minPrice` 是假設「今天賣出」可以賺多少錢
* `maxProfit` 記錄整個過程中最好的結果
    | Day | Price | minPrice (到目前為止最低價) | price - minPrice (當天賣出的利潤) | maxProfit |
    | --- | ----- | ------------------- | -------------------------- | --------- |
    | 0   | 7     | 7                   | 0                          | 0         |
    | 1   | 1     | 1                   | 0                          | 0         |
    | 2   | 5     | 1                   | 4                          | 4         |
    | 3   | 3     | 1                   | 2                          | 4         |
    | 4   | 6     | 1                   | 5                          | 5 ✅       |
    | 5   | 4     | 1                   | 3                          | 5         |


[<h3>Leetcode : Array 217. Contains Duplicate</h3>](<https://leetcode.com/problems/contains-duplicate/description/>)
```cpp=
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, int> mm;
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size(); i++){
            if(mm.find(nums[i]) != mm.end()) return true;
            mm[nums[i]] = i;
        }
        return false;
    }
};
```
>mm.end() 的檢查是必要的, 否則會跑不過
>
最簡單的寫法, 但並非最佳解
```cpp=
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i=1; i<nums.size(); i++){
            if(nums[i-1] == nums[i]) return true;
        }
        return false;
    }
};
```
**C語言的部分**
這部分使用氣泡排序法(Bubble Sort), 但因為O(n^2), 導致 Time Limit Exceeded
```cpp=
bool containsDuplicate(int* nums, int numsSize) {
    if(numsSize <= 1) return false;
    // 氣泡排序法 Bubble Sort
    for(int i=0; i<numsSize-1; i++){
        for(int j=0; j<numsSize-1-i; j++){
            if(nums[j] > nums[j+1]){
                int buffer =  nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = buffer;
            } 
        }
    }
    // for(int i=0; i<numsSize; i++){
    //     printf("nums[%d]:%d\n", i, nums[i]);
    // }

    for(int i=0; i<numsSize-1; i++){
        if(nums[i] == nums[i+1]) return 1;
    }
    return 0;
}
```
下面使用C內建函數 (qsort)
```cpp=
int compar(const void *a, const void *b){
    return(*(int*)a - *(int*)b);
}

bool containsDuplicate(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compar);
    for(int i=0; i<numsSize-1; i++){
        if(nums[i] == nums[i+1]) return true;
    }
    return false;
}
```
>qsort → https://www.runoob.com/cprogramming/c-function-qsort.html
>`void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))`
>- **base** - 指向要排序的陣列的第一個元素的指針。
>- **nitems** - 由 base 指向的陣列中元素的個數。
>- **size** - 數組中每個元素的大小，以位元組為單位。
>- **compar** - 用來比較兩個元素的函數。

[<h3>Leetcode :  Array 238. Product of Array Except Self</h3>](<https://leetcode.com/problems/product-of-array-except-self/description/>)

[解題原理可以看這](https://ithelp.ithome.com.tw/articles/10247080?sc=hot)

這需要 `從左到右` 和 `從右到左` 把乘積記下來後`再一起相乘`就會是答案

```cpp
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> left(nums.size(), 1);
        vector<int> right(nums.size(), 1);
        vector<int> answer(nums.size(), 1);
        for(int i=1; i<nums.size(); i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        for(int i=nums.size()-2; i>=0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        for(int i=0; i<nums.size(); i++) {
            answer[i] = left[i] * right[i];
        }
        return answer;
    }
};
```

比較好是像下面這樣

```cpp
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        vector<int> answer(nums.size(), 1);
        for(int i=1; i<size; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        int R = 1;

        for(int i=size-1; i>=0; i--) {
            answer[i] *= R;
            R *= nums[i];
        }
        return answer;
    }
};
```

`right` 就第二次回來時再算就好

| 步驟       | 做什麼                     |
| -------- | ----------------------- |
| 第一次走訪    | `answer[i] = 左邊乘積`      |
| 第二次走訪    | `answer[i] *= 右邊乘積 (R)` |
| `R` 每輪更新 | `R *= nums[i]`          |

:::info
不直接排除 `nums[i]`，而是把`「它左邊所有數字的乘積」 ×「右邊所有數字的乘積」`，剛好就是 除了 `nums[i]` 的所有數字相乘！
:::

[<h3>Leetcode :  Array 242. Valid Anagram</h3>](<https://leetcode.com/problems/valid-anagram/>)

* Anagram (字母異位詞)
    * 兩者**長度相同**
    * 兩者包含的**字母種類**及**數量完全一樣**，但順序可以不一樣
* `Input: s = "anagram", t = "nagaram"`
    * `anagram` 的字母與數量：
        * `a: 3`, `n: 1`, `g: 1`, `r: 1`, `m: 1`
    * `nagaram` 的字母與數量：
        * `n: 1`, `a: 3`, `g: 1`, `r: 1`, `m: 1`
    * **數量完全相同，順序不同，因此是字母異位詞。**


```cpp
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.empty() || t.empty()) return false;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};
```

這邊實作方式是直接用 sort 排序過後直接比較兩字串時否相同
這是最簡單的作法

另一種更高效的做法是**計數比較**, 他是 **計算兩字串中各字元數量，若全部相等即為異位詞。**

# Binary

[<h3>Leetcode :  Binary 338. Counting Bits</h3>](<https://leetcode.com/problems/counting-bits/>)

```cpp=
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n+1, 0);
        for(int i=1; i<=n; i++) {
            ans[i] = ans[i>>1] + (i&1);
        }
        return ans;
    }
};
```

假如 n = 61 = 32 + 29

32 = 10000 
29 = 2^4 + 2^3 + 2^2 + 2^0 = 16 + 8 + 4 + 1

| 5   | 4   | 3   |  2  |  1  | 0   |
| --- | --- | --- |:---:|:---:| --- |
| 1   | 1   | 1   |  1  |  0  | 1   |

`0` 的部分是奇數才會有, 所以把它拿出來後只要看 `5~1` 的部分, 所以 `ans[i>>1]`
而 `ans[i>>1]` 前面基本上已經有算過了, 所以可以直接用

```cpp
ans[i] = ans[i>>1] + (i&1)
```

for 從 1 開始, 因為 0 一定是 0

|  0  |      1(奇數+1) `ans[1]`       |      2(偶數+0) `ans[2]`       | 3 `ans[3]`                    |          4 `ans[4]`           | 5 `ans[5]` |  6  | 7   |
|:---:|:-----------------------------:|:-----------------------------:| ----------------------------- |:-----------------------------:|:----------:|:---:| --- |
|  0  | `ans[1]`=`ans[1/2=0]`+`1`=`1` | `ans[2]`=`ans[2/2=1]`+`0`=`1` | `ans[3]`=`ans[3/2=1]`+`1`=`2` | `ans[4]`=`ans[4/2=2]`+`1`=`2` |            |     |     |

這樣最後算下來就是 **`O(n)`**

# String
[<h3>Leetcode :  String 3. Longest Substring Without Repeating Characters</h3>](<https://leetcode.com/problems/longest-substring-without-repeating-characters/description/>)
>這題我目前暴力解
```cpp=
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) return 0;
        int j=0, num=0;
        string ss;
        for (int i=0; i<s.size(); i++){
            size_t pos = ss.find(s[i]); // size_t 無符號整數類型，通常用來表示大小、索引、位置等非負整數值。
            if (pos != string::npos){ // 當您使用 std::string::find 或其他字符串搜索函數時，
                ss.erase(0,1);        // 如果未找到匹配的子字符串或字符，這些函數通常會返回 std::string::npos，
                j=1;                  // 以指示未找到。
            } // erase -> 刪除指定範圍內的字符
            ss.push_back(s[i]);
            cout << ss << endl;
            j++;
            if (j >= num) num = j;
            if (ss[0] == s[i+1]){
                ss.clear(); // .clear() 是用於清空 C++ 字符串
                j=0;
            }else if (s[i] == s[i+1]){
                ss.clear();
                j=0;
            }else if (s[i+1] == s[i+2] && j == num){
                ss.clear();
                j=1;
            }
        }
        return num;
    }
};
```
**最優解**
```cpp=
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.size();
        int sq[128] = {0}; // 把 0-127 都初始化為 0
        int mx = 0; // 紀錄最大大小
        for (int l=0, r=0; r<len; r++){
            l = max(sq[s[r]], l);
            //  C++ 具有一定的隱式類型轉換能力，可以將 char 和 int 進行比較，
            // 並根據字符的 ASCII 值來進行比較。
            mx = max(mx, r - l + 1);
            sq[s[r]] = r + 1; // 記錄這個 char 最後一次出現的位置
        }
        return mx;
    }
};
```
>`int sq[128] = {0};`：
一個整數數組 sq，用於存儲每個字符在字符串中的最後一次出現的位置（索引）。
這個數組的大小為128，因為通常使用的 ASCII 字符集有128個字符。

# Martrix
[<h3>Leetcode :  Matrix 73. Set Matrix Zeroes</h3>](<https://leetcode.com/problems/set-matrix-zeroes/description/>)
```cpp=
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<int> result;
        int row = matrix.size();
        int column = matrix[0].size();
        for(int i=0; i<row; i++){
            int count = 0;
            for(int j=0; j<column; j++){
                if(matrix[i][j] == 0){
                    result.push_back(j);
                    count = 1;
                }
            }
            if(count >= 1){
                for(int k=0; k<column; k++){
                    matrix[i][k] = 0;
                }
            }
        }
        for(int i=0; i<row; i++){
            for(int s=0; s<result.size(); s++){
                if(matrix[i][result[s]] != 0) matrix[i][result[s]] = 0;
            }
        }
    }
};

/* row and column
1,2,3
4,5,6
7,8,9

row -> 1,2,3

column -> 1,
          4,
          7,
*/
```
>這題就比較簡單, 想一下其實就可以解出來, 
目前看大家都是 O(N^2), 所以不知道這樣算不算暴力解
我是先處裡 row, 再去處理 column

[<h3>Leetcode : Martix 54. Spiral Matrix</h3>](<https://leetcode.com/problems/spiral-matrix/>)
```cpp=
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        int m = matrix.size(); // column
        int n = matrix[0].size(); // row
        int left = 0, right = n - 1, top = 0, bottom = m - 1;

        while (result.size() < m * n) {
            // 往右
            for (int i = left; i <= right; i++) {
                result.push_back(matrix[top][i]);
            }
            ++top;

            // 往下
            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }
            --right;

            // 往左
            if(result.size() >= m * n) break;
            for (int i = right; i >= left; i--) {
                result.push_back(matrix[bottom][i]);
            }
            --bottom;

            // 往上
            for (int i = bottom; i >= top; i--) {
                result.push_back(matrix[i][left]);
            }
            ++left;
        }

        return result;
    }
};
```
**解析**
>一步一步去走, 使用上下左右來定義邊界,
往右走上面就要往下, 往下走右邊就要往左, 往左走下面就要往上, 往上走左邊就要往右
慢慢的縮小邊界
![image](https://hackmd.io/_uploads/HysQ1Tc6p.png)
![image](https://hackmd.io/_uploads/Sy5NyTc6a.png)
![image](https://hackmd.io/_uploads/H1LBJ656a.png)
![image](https://hackmd.io/_uploads/r1yI169T6.png)
![image](https://hackmd.io/_uploads/SyE8k69T6.png)
**left = 1, right = 2, top = 2, bottom = 1**
result 數量最多只有 m*n, 所以如果在 m*n 的話就會繼續
這邊要注意往左之前要加上 if(result.size() >= m * n) break;
因為通常 top 已經 > bottom, 而 left 沒有 > right, 所以他可能會再進去往左
.
或者可以在**往左**加入 `if (top <= bottom)` 就進去 for, 
但這樣的話也在**往上**加入 `if (left <= right)` 就進去 for

# Linked List
[<h3>Leetcode : Linked List 206. Reverse Linked List</h3>](<https://leetcode.com/problems/reverse-linked-list/>)
```cpp=
/**
 * 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) {
        ListNode* ListAns = nullptr;
        ListNode* tail = nullptr;
        stack<int> ans;
        while(head != nullptr){
            ans.push(head->val);
            head = head->next;
        }
        while(!ans.empty()){
            int val = ans.top();
            ans.pop();
            if(ListAns == nullptr){
                ListAns = new ListNode(val);
                tail = ListAns;
            }else {
                tail->next = new ListNode(val);
                tail = tail->next;
            }
        }
        return ListAns;
    }
};
```
**比較好的解法**
```cpp=
/**
 * 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) {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while(head != nullptr){
            head = head->next;
            cur->next = prev;
            prev = cur;
            cur = head;
        }
        return prev;
    }
};
```
>這邊要去翻轉這個 Linked List,
需要有三個 ListNode, 1→head, 2→current, 3→prev
head→ 紀錄下一個點, cur→ 目前的點, prev→ 反轉要回傳的
>1. head = head->next; 將 head 指向 head 的下一個點
>2. cur->next = prev; 將 cur 往前指向 prev
>3. cur = head; 將 cur 指向 head 已經指向下一個點的 head
>![image](https://hackmd.io/_uploads/r1mXea9aa.png)
![image](https://hackmd.io/_uploads/ByaXepcTT.png)
![image](https://hackmd.io/_uploads/Sk9Nepc66.png)
![image](https://hackmd.io/_uploads/HyHSx6qaT.png)
![image](https://hackmd.io/_uploads/SyqSxTcTT.png)
![image](https://hackmd.io/_uploads/HJxUxaqTa.png)
到這邊 head 跟 cur 都已經是 NULL, 並且 while(head != nullptr), 所以停止 loop,
並回傳 prev, 因為 prev 從 5 往 1 指過去, 這樣就完成翻轉了。
主要是用到 head, current, prev

**C語言解法**
```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *temp = NULL;
    struct ListNode *previous = NULL;
    while(head != NULL){
        temp = head;
        head = head->next;
        temp->next = previous;
        previous = temp;
    }
    return previous;
}
```

[<h3>Leetcode : Linked List 141. Linked List Cycle</h3>](<https://leetcode.com/problems/linked-list-cycle/>)
```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode* first = head->next;
        ListNode* second = head;
        while(first != second){
            if(first == NULL || first->next == NULL) return false;
            first = first->next->next;
            second = second->next;
        }
        return true;
    }
};
```
**解題想法**
>題目那個 pos 根本不用理他, 他只是讓你方便理解用的,
首先宣告兩個 ListNode, 一個為起始點, 一個為起始點的下一個,
如果有環, 不管怎麼 →next 都不會到 NULL, 所以要想辦法讓前面的繞一圈追到後面的,
所以 first 會前進兩個, second 會前進一個, 這樣如果有環, 
就會追到 first == second , while 就會結束, 因為 first 跑最快, 
所以判斷如果 first == NULL 或者 first→next == NULL 就等於沒環 return false
最後出 while 就代表 first == second 所以回傳 true

[<h3>Leetcode : Linked List 21. Merge Two Sorted Lists</h3>](<https://leetcode.com/problems/merge-two-sorted-lists/>)
```cpp=
/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1 && !list2) {
            return nullptr;
        }
        if(!list1) {
            return list2;
        }
        if(!list2) {
            return list1;
        }
        if(list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};
```
**合併流程**
>當我們將兩個有序的鍊錶合併時，我們首先比較它們的頭部節點，然後將較小的節點移至合併後的鍊錶。
我們遞迴執行此過程，直到其中一個鍊錶變為空為止。
以下是一個示意圖，展示了如何合併兩個排序的鍊錶：
![image](https://hackmd.io/_uploads/S1dQZ69aT.png)
![image](https://hackmd.io/_uploads/S1dEZT9pa.png)
![image](https://hackmd.io/_uploads/SyfHWp9pT.png)
![image](https://hackmd.io/_uploads/r1YHZT96p.png)
![image](https://hackmd.io/_uploads/HyJUW65Ta.png)
![image](https://hackmd.io/_uploads/SkHIZp5TT.png)
這樣，我們已經成功合併了兩個排序的鍊錶，並且合併後的鍊錶仍然保持升序排序。
這就是這段程式碼中 **`mergeTwoLists`** 函數的運作方式。

[<h3>Leetcode : Linked List 143. Reorder List</h3>](<https://leetcode.com/problems/reorder-list/>)
```cpp=
/**
 * 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:
    void reorderList(ListNode* head) {
        //  1.find the middle Node
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        //  2.reverse the second half of the list
        ListNode *current = slow->next;
        ListNode *prev = nullptr; // previous
        slow->next = NULL;
        while(current != nullptr){ // prev  5->4->nullptr
            ListNode *next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        //  3.merge two lists
        ListNode *list1, *list2;
        while(head != nullptr && prev != nullptr){
            list1 = head->next;
            list2 = prev->next;
            head->next = prev;
            prev->next = list1;
            head = list1;
            prev = list2;
        }
    }
};
```
**作法分三個步驟**
>1. **find the middle point**
    - 使用兩個指針 **`fast`** 和 **`slow`** 同時遍歷鏈表，其中 **`fast`** 一次移動兩個節點，**`slow`** 一次移動一個節點，當 **`fast`** 到達鏈表尾部時，**`slow`** 就會指向鏈表的中間節點。
>2. **reverse the second list**
    - 將 **`slow`** 指向的中間節點後的部分反轉。
    使用指針 **`current`** 依次指向中間節點的下一個節點，然後進行反轉操作，
    即將 **`current->next`** 指向 **`prev`**，**`prev`** 移動到 **`current`**，
    **`current`** 移動到 **`current->next`**。
    這樣完成後，**`prev`** 就成為了反轉後的第一個節點。
>3. **merge two lists**
    - 將鏈表的前半部分和反轉後的後半部分進行交叉合併。
    具體步驟是使用兩個指針 **`list1`** 和 **`list2`** 分別指向兩部分的頭節點，
    然後進行交叉合併，即將 **`head->next`** 指向 **`prev`**，**`prev->next`** 指向 **`list1`**，
    **`head`** 和 **`prev`** 各自往後移動。

# Interval
[<h3>Leetcode : Interval 57. Insert Interval</h3>](<https://leetcode.com/problems/insert-interval/>)
```cpp=
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end());
        ans.push_back(intervals[0]);
        for(int i=1; i<intervals.size(); i++){
            int &end = ans.back()[1];
            if(end >= intervals[i][0]){
                end = max(intervals[i][1], end);
            }else ans.push_back(intervals[i]);
        }
        return ans;
    }
};
```
**解析**
![image](https://hackmd.io/_uploads/HkVcGac6p.png)

```cpp=
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& in, vector<int>& newIn) {
        vector<vector<int>> ans;
        in.push_back(newIn);
        sort(in.begin(), in.end());
        ans.push_back(in[0]);

        for (int i = 1; i < in.size(); i++) {
            int *end = &ans.back()[1]; // 將 end 宣告為指標
            if (*end >= in[i][0]) {
                *end = max(in[i][1], *end);
            } else {
                ans.push_back(in[i]);
            }
        }
        return ans;
    }
};
```
**解析**
![image](https://hackmd.io/_uploads/HJY3Gpcpa.png)
![image](https://hackmd.io/_uploads/Byr6z6qTT.png)

# Graph
# Tree
# Heap
# Unclassified

[<h3>50. Pow(x, n)</h3>](<https://leetcode.com/problems/powx-n/description/>)

```cpp=
typedef long long long2;

class Solution {
public:
    double myPow(double x, int n) {
        if(x == 0) {
            return 0.0;
        }
        if(n == 0) {
            return 1.0;
        }
        long2 N = n;
        if(n < 0) {
            x = 1/x;
            N = -N;
        }
        double ans = 1.0;
        double current_value = x;
        while(N > 0) {
            if(N % 2 == 1) {
                ans *= current_value;
            }
            current_value *= current_value;
            N/=2;
        }
        return ans;
    }
};
```

這題要使用 **快速幂** 來解, [可以參考此影片](https://www.youtube.com/watch?v=GbDtCFhq20A)

![image](https://hackmd.io/_uploads/H1IYrCMUyl.png)

|  2^10   |      ans      | current_value |
| --- |:-------------:| ------------- |
| 10  |       1       | 2^2           |
| 5   |    1 x 2^2    | 2^4           |
| 2   |    1 x 2^2    | 2^8           |
| 1   | 1 x 2^2 x 2^8 | 2^16          |
|     |     2^10      |               |

`10 = 00001010`

|   循環次數   |  n   |
|:------------:|:----:|
|      1       | 1010 |
|      2       | 101  |
|      3       |  10  |
|      4       |  1   |
| ~~5 (退出循環)~~ |  0   |

上面就等於 `N/2`

:::info
另外可以知道

**`N/2` ==` N>>1`**

**`N%2` == `N&1`**
:::

遞迴做法：

```cpp
class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0) return 1.0;
        long long N = n;
        if(N < 0) {
            N = -N;
            x = 1/x;
        }
        double ans = 1.0;
        if(N & 1) {
            ans *= x;
        }
        ans *= myPow(x*x, N>>1);
        return ans;
    }
};
```

一樣使用 `快速冪` 每進到下一次遞迴都是 `x * x`, 只有在基數時更新 ans, 可以參考上面 binary table

以 `2^10` 為範例會進4次, 「10, 5, 2, 1」, 0 結束

`ans *= myPow(x*x, N>>1)`

最後就是「10(`1`), 5(`2^2`), 2(`1`), 1(`2^8`)」, `1*2^2*1*2^8`