<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;
}
};
```
**解析**
>一步一步去走, 使用上下左右來定義邊界,
往右走上面就要往下, 往下走右邊就要往左, 往左走下面就要往上, 往上走左邊就要往右
慢慢的縮小邊界
**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
>
到這邊 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;
}
}
};
```
**合併流程**
>當我們將兩個有序的鍊錶合併時，我們首先比較它們的頭部節點，然後將較小的節點移至合併後的鍊錶。
我們遞迴執行此過程，直到其中一個鍊錶變為空為止。
以下是一個示意圖，展示了如何合併兩個排序的鍊錶：
這樣，我們已經成功合併了兩個排序的鍊錶，並且合併後的鍊錶仍然保持升序排序。
這就是這段程式碼中 **`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;
}
};
```
**解析**
```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;
}
};
```
**解析**
# 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)
| 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`
Sign in with Wallet
Connect another wallet