2024q1 Homework2 (quiz1+2)
---
contributed by < LULser0204 >
### 第一週測驗題
#### 測驗1
##### 前言
參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)，實作非遞迴 (non-recursive; iterative) 的快速排序法。作者是用了一個明確的堆疊( beg[] 和 end[] )取代了遞迴呼叫使用，減少了函式調用的開銷。
除此之外，作者在每一輪中只通過 `swap` 交換一次軸心點，避免了重複的移動開銷，減少了元素與自身交換的情況。
##### 分析此題鍊結串列的運作
###### 結構
自定義一個鍊結串列結構體:
```
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
在 `node_t` 結構中，他有一個指標 `next` 指向下一個節點，而 `left` 和 `right` 並沒有在 `quicksort`中特別著墨，猜測此為單向鍊結串列。
:::spoiler quick sort 程式碼
```
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list);
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
:::
在這個函式的迴圈中，有幾個重要的步驟:
1.選擇軸心點 (pivot) 並將其從鍊表中分離。
2.遍歷練表，根據截點值與軸心點值得比較結果，將截點添加到 `left` 或 `right` 鍊表中
3.更新 `begin` 、 `end` 陣列以反映新的子鍊表界線。
4.重設 `left` 和 `right` 為 `NULL` 並增加`i` 以處理下一層
過程如下圖:
##### 可改進之處
我認為可行的改進之處:
1.由於 `quick sort` 的效率很大程度依賴於軸心點的選擇。使用第一個作為軸心點在 `worst case` 下會導致很差的性能。
> 可以考慮使用"三數取中"策略，即從鍊表的(首部、中部和尾部)選擇三個元素，然後將這三個元素的中間值作為軸心點
2.
#### 測驗2
##### 前言
Tim Peter 他結合合併排序和插入排序的特點，提出 Timsort。在現實世界中，許多資料往往是由一些已經部分排序的序列組合而成，於是他的策略是首先識別出資料中已排序的子序列 (這些子序列稱為 run），然後透過不斷合併這些 run 來達成全資料範圍的排序。
##### 分析此題鍊結串列的運作
###### 結構
雙向鏈結串列
```
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
鏈結串列元素
```
typedef struct {
struct list_head list;
int val;
int seq;
} element_t;
```
##### 完成程式碼
程式碼
* `AAAA` 應該要填 `&head` 。因為要初始化 `tail` 指標的位址，使其指向鍊結串列的 `head` 位址。這樣 `*tail` 就可以被賦值為第一個節點，即合併後鍊節串節的頭節點。
* `BBBB` 和 `CCCC` 應該要填 `&(a->next)` 和 `&(b->next)` 從上面可以得知 `*tail` 要放入的是下一個節點，故要更新 `tail` 值使其指向下一個節點的 `next` 。這麼做是為了在下一次跌代中，將下一個節點插入鍊結串列。
* `DDDD` 和 `EEEE` 應該要填 `head->prev` 和 `tail->next` 完成雙向鍊結串列的循環。
* `FFFF` 應該填 `1` ，因為如果大於1代表鍊結串列還可以被合併
##### 運作原理
`run_size` :根據鍊結串列的頭節點計算當前運行的大小。
`merge` :合併兩個已排序的鍊結串列。
`build_prev_link` :重新連接鍊結串列的 `prev` 指針。
`find_run` :在鍊結串列中找到一個遞增或是遞減的序列，並且翻轉遞減的序列使其成為遞增序列。
`merge_at` 、 `merge_force_collapse` 、 `merge_collapse` :這些函式負責串列的合併操作。
`merge_final` :所有的 runs 都通過上面的 merge 函式合併後，負責將最後兩個 runs 合併成一個完全有序的串列，以及重建雙向鍊結。
而主函式 timsort:
1.初始化和準備:將雙向鍊結串列轉換為以 `NULL` 為結尾的單向鍊結串列。
2.尋找並合併 `runs` :通過 `find_run` 尋找 `runs`，然後利用 `merge_collapse` 或 `merge_force_collapse` 根據特定規則來合併runs。後者是在排序過程接近完成時使用。
3.最終合併:當輸入的鍊結串列完全轉化為 runs 後，使用 `merge_force_collapse` 強制合併剩餘的所有 runs ，最後通過 `merge_final` 或 `build_prev_link` 重建整個串列的雙向鍊結。
##### 改進方案
> 待補...
---
### 第二週測驗題
#### 測驗1
##### 前言
[LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/) 題意：
> 給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹。
```
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
```
##### 完成程式碼
先觀察hash table 實作中，用以處理 hash 數值碰撞的 hlist_node，注意他的 pprev 是 pointer to pointer
```
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
示意圖
* `AAAA` 應該填 `h->first` 。因為要將新節點 n 插入 hash table 的頭部， n->next 應該指向原鍊結串列的第一個節點，即目前的 h->first
* `BBBB` 應該填 `&heads[hash]` 。使用 `hlist_for_each` 遍歷特定的 hlist 。而 `&heads[hash]` 是該 hlist 的頭。
* `CCCC` 應該填 `list_entry` 。從括號內的參數剛好對應 list_entry 的 (ptr, type, member) 推測。
* `DDDD` 應該填 `&heads[hash]` 。在 node_add 函式中，其功能為將一個新的節點加入到 hash table 。 DDDD 應該指向我們想要增加新節點的鍊節串列的頭。
##### 說明特定函式的功能
* hlist_add_head :將一個新節點 n 加到指定的 hash table 頭部 h
* find :根據給定的數字 `num` 和 hash table 大小 `size` ，在 hash table 中尋找對應的 `order_node` ，返回找到的節點其索引值。
* dfs :首先通過 `preorder` 結果找到當節的根節點，然後在 `inorder` 結果中找到該節點，從而分隔出左右子樹，然後遞迴構建左右子樹。
* node_add :將中序遍歷中的一個節點和索引加入到 hash table 中 dfs 函式快速找到任何節點在中序遍歷中的位置。
* buildTree :使用前序和中序遍歷的結果來重建二元樹。首先使用 `in_heads` 紀錄中序遍歷中每個元素的 hlist 頭部。接下來，在迴圈內使用 `node_add` 進行中序遍歷，並且將其中的每個元素和對應的索引加到 hash table 。最後通過使用 dfs 函式構建二元樹，並返回構建好的二元樹根節點
##### 運作原理
1. 構建一個 hash table ，儲存 inorder 遍歷結果中每個元素，方便查詢以及之後建造二元樹
2. 使用 dfs 函式深度優先方式尋找根節點，利用 find 函式回傳索引值(根節點位置)。
3. 以根節點為中心，分為左右子樹，在遞迴乎叫 dfs 函式完成整棵二元樹。
##### 可改進之處
> 待補...
#### 測驗2
##### 前言
針對 [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/description/)
> 題目說明:有一個 LRU Cache 其有一定的容量 (capcity) ，然後使用 **put** 放入 Cache 裡面，如果放入時 Cache 已滿，則把 LRU (Least Recently Used) key 拋棄，並把新的 key 放入 Cache ;而 **get** 則是看當下 Cache 裡面是否有對應的 key ，有則返回其值，並將對應的 key **更新** ，沒有則返回 -1 。
##### 說明&完成程式碼
結構:
LRUCache :LRU 主要結構，包含容量 (capcity) 、當前數據量 (count) 、雙向鏈結的頭用於實現 LRU 功能 (dhead) 、hash table 陣列 (hhead) 用於快速查詢
LRUNode :存放在 LRUCache 中的節點結構，包含 key、value、hash table 節點、雙向鏈結串列節點 link
主要函式:
lRUCacheCreate :創建一件新的 LRU Cache 物件，初始化其 capcity、count、dhead、hhead
lRUCacheFree :釋放LRU Cache 中所占用的記憶體空間，包括所有 LRUNode 節點
lRUCacheGet: 從 Cache 中獲取一個元素的值。如果找到，將其移至雙向鏈結串列的頭，代表最近被使用。
lRUCachePut: 往 Cache 中放入一個新元素或更新現有元素的值。如果 Cache 已滿，則先移除 LRU 元素，然後在鏈結串列頭部放入新元素
EEEE :在 hlist_del 函式中，應該填入" next->pprev "。舉例:假設現在有 A->B->C 的串列，現在要刪除節點 B。
刪除前:
* A 的 next 指向 B ， B 的 pprev 指向 A 的 next
* B 的 next 指向 C ， C 的 pprev 指向 B 的 next
執行刪除動作:
* 將 B 的 pprev (即 A 的 next )更新為 B 的 next (即 C )，此時 A 直接指向 C
* 如果 B 的 next (即 C )存在，更新 C 的 pprev 為指向 A 的 next
刪除後:
* A 的 next 現在指向 C ，C 的 pprev 指向 A 的 next (從串列中移除 B )
FFFF :要填入 link ，因為這是 LRUNode 結構中連接到 list_head 的 member 名。
GGGG :要填入 &cache->link 。這裡要傳遞一個指向 list_head 的 pointer 到 list_del 函式中刪除節點。
HHHH :要填入 node ，因為 lRUCacheGet 函式是基於 hlist_node 所指向的物件。
IIII :要填入 &cache->link 指向 list_head 結構的 pointer 。
JJJJ :要填入 node ，其原因一樣是基於 hlist_node 所指向的物件。
KKKK :要填入 &c->link ，在 lRUCachePut 函式的功能就是將剛使用到的節點移到鏈結串列的頭部。
##### 運作流程
1. 由 lRUCacheGet 進行查詢的動作，通過鍵的 hash table 值定位到位置，如果找到，則將對應的節點移到頭部，並返回值;反之，找不到則返回 -1 。
2. 由 lRUCachePut 進行更新的動作，通樣先定位，檢查元素是否存在。如果存在，更新其值並移至頭部。如果不存在，檢查 Cache 是否已滿。滿了，去除掉 LRU 元素，增加新的元素在串列頭部;沒滿，直接增加新元素在串列頭部。
##### 延伸問題
> 待補...
#### 測驗3
##### 前言
在指定的記憶體空間找出第 N 個設定的位元(即 1
##### 解釋程式碼&完成程式碼
主要函式:
FIND_NTH_BIT :找到第 n 個 bit的位置。
_ffs : Find First Set 找到第一個 bit 位置。返回給定的無號整數最小有效位置的 index 。
__clear_bit :清除再給定位址中特定位。
fns :在一個常整數中找到第n個設置位的位置。通常迴圈使用 __ffs 來找到並清除最低設置位，直到找到第 n 個為止。
AAAA : 要填 0xffffffff 。根據下面判斷式中( 0x1、0x3、0xf...)的規律推導出來的
BBBB : 要填 ~mask 。 __clear_bit 函式主要功能是對於特定 bit 進行清除。要清除一個位元需要通過 AND 操作。
CCCC : 要填 % 。用於尋找第 n 個 bit 為 1 的索引。
##### 運作主要原理
find_nth_bit 是整個核心。通過遍歷數組中每個字，使用 hweight_long 快速跳過完全為 0 的字，直到找到包含目標位置 bit 。然後再使用 fns 函式定位出確切的位置。
##### 延伸問題
> 待補
Sign in with Wallet
Connect another wallet