2022q1 Homework (quiz1)

--- tags: linux2022 --- # 2022q1 Homework (quiz1) contributed by <`ibat10clw`> > [quiz1](https://hackmd.io/@sysprog/linux2022-quiz1) ## Q1. 以 hash 實作 LeetCode1. Two Sum 首先從解題的函式 twoSum 開始看起 ```c int *twoSum(int *nums, int numsSize, int target, int *returnSize) { map_t *map = map_init(10); *returnSize = 0; int *ret = malloc(sizeof(int) * 2); if (!ret) goto bail; for (int i = 0; i < numsSize; i++) { int *p = map_get(map, target - nums[i]); if (p) { /* found */ ret[0] = i, ret[1] = *p; *returnSize = 2; break; } p = malloc(sizeof(int)); *p = i; map_add(map, nums[i], p); } bail: map_deinit(map); return ret; } ``` 執行流程可以表示如下: 1. 初始化 hash_map 2. 看過所有 nums 中的元素並且同時查詢 map 中是否有 key 與 ```nums[i]``` 相加會等於 target * 若有查到對應的元素則將 ```i``` 與 ```HT[nums[i]]``` 作為答案 * 沒有查到的話則將 ```target - nums[i]``` 作為 key, ```i``` 作為 value 並且加入 map 中 3. 將 map 釋放掉後回傳答案接下來看 hash 的實作 ```c struct hlist_node { struct hlist_node *next, **pprev; }; struct hlist_head { struct hlist_node *first; }; ``` * 先從 hlist 看起, 相關的結構共有兩個, 分別是 head 以及 node, 為了解決碰撞(collision)問題, 同樣一個 bucket 的資料會由 hlist_head 指出去的 list 串連起來 * 此外為了讓程式碼更精簡, 在 hlist_node 採用了 pointer to pointer 的方式, 這樣能夠在 delete 的操作上消除特例情況的判斷, 不需判斷要刪除的地方是否為 head 或 NULL 的情形, 但 ```**pprev``` 的指標 hlist_head 並不需要, 若與 hlist_node 共用一個 struct 則會浪費記憶體, 因此將其分開宣告再來是 map 的本體以及 hash 的資料定義 ```c typedef struct { int bits; struct hlist_head *ht; } map_t; struct hash_key { int key; void *data; struct hlist_node node; }; ``` * map_t 裡面的 bits 會用來決定 bucket 的數量以及用於後續的 hash function, 根據 bits 的大小會產生對應的 hlist_head , 在後續的函式解說中會更詳細說明 * hash_key 為實際資料存放的地方, 裡面有個 hlist_node 可以讓 hash_key 透過 list 的方式與 bucket 連接 ### map_init ```c map_t *map_init(int bits) { map_t *map = malloc(sizeof(map_t)); if (!map) return NULL; map->bits = bits; map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits)); if (map->ht) { for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) (map->ht)[i].first = NULL; } else { free(map); map = NULL; } return map; } ``` 一開始先將傳入的參數 bits 指定給 map 的 member, 接著透過一個 macro 的實作來決定 ht 大小 ```c #define MAP_HASH_SIZE(bits) (1 << bits) ``` 以 1 為底的 shift operator 可以視為 2^0^ * 2^bits^ = 2^bits^ 的操作接下來將所有的 hlist_head 的 first 指向 NULL, 以代表目前 hash table 的各個 bucket 都是空的 ![](https://i.imgur.com/9ZuIhVI.png) ### map_get ```c void *map_get(map_t *map, int key) { struct hash_key *kn = find_key(map, key); return kn ? kn->data : NULL; } ``` 找尋傳入的 key 是否存在 map 裡面, 如果有就回把 ```hash_key->data``` 的 address 傳回去, 否則回傳空指標 ### find_key ```c static struct hash_key *find_key(map_t *map, int key) { struct hlist_head *head = &(map->ht)[hash(key, map->bits)]; for (struct hlist_node *p = head->first; p; p = p->next) { struct hash_key *kn = container_of(p, struct hash_key, node); if (kn->key == key) return kn; } return NULL; } ``` 首先透過 hash function 找出 key 可能位於哪個 bucket 之後從該個 bucket 的 head 出發尋訪整個 list 如果有找到某個 hash_key 的 key 與傳入參數的 key 相等, 則回傳該個 hash_key, 否則回傳 NULL 例如 hash 出來的值為2, 那則順著這個 list 沿路比對 key, 若比對成功的話就將這個 hash_key 的 address 回傳(附圖上先忽略了 pprev 的link) ![](https://i.imgur.com/aPPLuQa.jpg) ### hash ```c #define GOLDEN_RATIO_32 0x61C88647 static inline unsigned int hash(unsigned int val, unsigned int bits) { /* High bits are more random, so use them. */ return (val * GOLDEN_RATIO_32) >> (32 - bits); } ``` 一個好的 hash function 須滿足三個條件 1. 容易計算 2. 每個 bucket 被分配到的機率盡量相等 3. 減少碰撞發生可以看到這個 hash function 為單純的四則運算在加上 shift, 有滿足容易計算的性質第二和第三個性質待驗證這個函數的功能也相當容易理解, 就是根據傳入的 val 和 bits 回傳該將資料放在哪一個 bucket 實作部份會將 val 乘上 GOLDEN_RATIO_32 後再把 (32 - bits) 的量透過 right shift 去掉, 以本題實作來說 bits 為 10, 32 bits 的資料再去掉 22 bits 後恰好剩下 10 bits, 因此也能保證他的值會位於 0 ~ 1023 之間 ### map_add ```c= void map_add(map_t *map, int key, void *data) { struct hash_key *kn = find_key(map, key); if (kn) return; kn = malloc(sizeof(struct hash_key)); kn->key = key, kn->data = data; struct hlist_head *h = &map->ht[hash(key, map->bits)]; struct hlist_node *n = &kn->node, *first = h->first; AAA; if (first) first->pprev = &n->next; h->first = n; BBB; } ``` 首先查詢輸入的 key 是否已存在 map 中, 若有找到根據 ```find_key``` 的寫法,確認 ``` kn != NULL```, 若已存在 map 中則直接離開函式由於沒有找到所以 ```kn``` 會是空指標, 為他分配一個 ```hash_key``` 大小的記憶體空間, 同時將資料初始化然後透過 hash function 找出應該把他放在哪一個 bucket , 將這個 bucket 的資訊存在變數 h, hash_key 的 node 存在變數 n, 該 bucket 的第一個元素存在變數 first 這時先來觀察 13~15 行中給出的資訊, 若 first 不為 NULL 則表示這個 bucket 至少存在一個資料, 我們將 kn 加入在 list 的 head 端, 因此先更新了原先 first 的 pprev, 最後在將 first 更新成 n 最後來推斷 AAA 與 BBB 分別的情形 ![](https://i.imgur.com/ACOZMKf.png) 如上圖所示, 每個 node 都有 pprev 與 next 需要處理, 顯然我們還沒對新加入的資料 kn 的 node 做處理又因為是插入在 head 那一端因此需要將 next 指向原先的第一個 node, pprev 指向 hlist_head.first * AAA * 在 15 行後我們就失去了原先 first 的資訊了, 所以根據題目選項這邊一定要先把 next 指過去 * ```n->next = first``` * BBB * 由於 AAA 以更新 next, 這邊將 pprev 也指向 hlist_head.first * ```n->pprev = &h->first``` ### map_deinit ```c void map_deinit(map_t *map) { if (!map) return; for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) { struct hlist_head *head = &map->ht[i]; for (struct hlist_node *p = head->first; p;) { struct hash_key *kn = container_of(p, struct hash_key, node); struct hlist_node *n = p; p = p->next; if (!n->pprev) /* unhashed */ goto bail; struct hlist_node *next = n->next, **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; n->next = NULL, n->pprev = NULL; bail: free(kn->data); free(kn); } } free(map); } ``` 最後是釋放掉 map 的方法, 如果 map 不存在則直接 return 外層的 for 迴圈是為了檢查所有的 bucket, 內層的 for 迴圈則是走過這個 bucket 上的 list 並且透過 ```container_of``` 沿途釋放元素, 可以看到初始化時將 head->first 存在 p, 若 p 為空則直接結束, 否則移動 p 走訪 list 當所有的 node 釋放完畢後把 map 本身也釋放掉, 函式結束 ### 答案在 map_add 有詳細解釋思路 * AAA = ```n->next = first``` * BBB = ```n->pprev = &h->first``` ## Q2. LeetCode 82. Remove Duplicates from Sorted List II 這題目的要求相當簡單, 若在 list 中有出現重複元素, 則將他們全部刪除 ```c= #include <stddef.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode *deleteDuplicates(struct ListNode *head) { if (!head) return NULL; if (COND1) { /* Remove all duplicate numbers */ while (COND2) head = head->next; return deleteDuplicates(head->next); } head->next = deleteDuplicates(head->next); return head; } ``` ### 題目分析本題的題目首先要求補齊 COND1 和 COND2 以下是我的答案 * COND1 = ```head->next && head->val == head->next->val``` * COND2 = ```head->next && head->val == head->next->val``` 先來分析遞迴的中止條件, 當 head 為空指標時才會結束遞迴呼叫, 搭配上 17 和 21 行的遞迴呼叫, 可以看到是遞迴在當前的下一個 node 再來探討兩次呼叫的區別 * 17 行中的呼叫並沒有將 return 的值存下來 * 20 行中將 return 的值存下來, 並且是串在 list 上因此可以推測 20 行中所處理的是不重複的元素, 才會將 return value 串在 list 上反之 13 行開始的 if block 是處理重複的元素, 當條件成立時不斷將指標向前推進, 最後做一個遞迴呼叫 ### 遞迴解法這是我一開始的想法 ```c head->val == head->next->val ``` 只要發現目前 node 的值與下一個 node 相等, 就開始 remove all duplicate 的處理, 但一提交馬上遇到存取了 NULL pointer的問題後來在 condition 前面先補上 ```head->next``` 並且用 && 做連接變成 ```c head->next && head->val == head->next->val ``` 當 ```head->next``` 為空時, 後面的 ```head->next->val``` 就不會被執行了, 成功避免了存取空指標的問題, 同時因為是 AND 運算, 其中一個地方不成立也不會進去 if 的 block 裡面 ### 非遞迴解法以下是我實作的程式碼, remove 的方法參考了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E5%BE%9E-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E8%97%9D%E8%A1%93%E8%AB%87%E8%B5%B7)中介紹的方式關於 remove 的部份有稍做修改, 由於 LeetCode 上的 struct 定義與 linux 裡面有所不同, head 是有帶 data 的, 同時由於 head 也可能被移除, 因此將傳入的參數改為 pointer to pointer deleteDuplicates 是參考了 [lab0-c](https://hackmd.io/8xMSCctKQpWWSRGLiuPkfQ?view#q_delete_dup) 的方法外層的 while 每個回合都儲存 current->val, 然後開始與 current->next 比對, 如果相等就開始刪除直到current->next->val 不相等時, 離開內層 while 並且根據 tag 來決定是否要在刪除 current ```c= void remove_list_node(struct ListNode **list, struct ListNode *target) { struct ListNode **indirect = list; while (*indirect != target){ indirect = &(*indirect)->next; } *indirect = target->next; } struct ListNode *deleteDuplicates(struct ListNode *head) { if (!head) return NULL; struct ListNode *current = head; char tag = 0; int pval; struct ListNode* del_node; while (current != NULL) { pval = current->val; while (current->next && current->next->val == pval) { tag = 1; del_node = current; current = current->next; remove_list_node(&head, del_node); } if(tag){ tag = 0; del_node = current; current = current->next; remove_list_node(&head, del_node); } else current = current->next; } return head; } ``` ## Q3. LeetCode 146. LRU Cache 以下為完整的測試程式 * MMM1 = ```list_for_each_entry_safe``` * MMM2 = ```list_for_each_entry``` * MMM3 = ```list_for_each_entry``` * MMM4 = ```list_last_entry``` ```c= #include <stdio.h> #include <stdlib.h> #include "list.h" typedef struct { int capacity, count; struct list_head dhead, hheads[]; } LRUCache; typedef struct { int key, value; struct list_head hlink, dlink; } LRUNode; LRUCache *lRUCacheCreate(int capacity) { LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head)); obj->count = 0; obj->capacity = capacity; INIT_LIST_HEAD(&obj->dhead); for (int i = 0; i < capacity; i++) INIT_LIST_HEAD(&obj->hheads[i]); return obj; } void lRUCacheFree(LRUCache *obj) { LRUNode *lru, *n; list_for_each_entry_safe (lru, n, &obj->dhead, dlink) { list_del(&lru->dlink); free(lru); } free(obj); } int lRUCacheGet(LRUCache *obj, int key) { LRUNode *lru; int hash = key % obj->capacity; list_for_each_entry (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); return lru->value; } } return -1; } void lRUCachePut(LRUCache *obj, int key, int value) { LRUNode *lru; int hash = key % obj->capacity; list_for_each_entry (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); lru->value = value; return; } } if (obj->count == obj->capacity) { lru = list_last_entry(&obj->dhead, LRUNode, dlink); list_del(&lru->dlink); list_del(&lru->hlink); } else { lru = malloc(sizeof(LRUNode)); obj->count++; } lru->key = key; list_add(&lru->dlink, &obj->dhead); list_add(&lru->hlink, &obj->hheads[hash]); lru->value = value; } int main() { LRUCache *lRUCache = lRUCacheCreate(2); lRUCachePut(lRUCache, 1, 1); // cache is {1=1} lRUCachePut(lRUCache, 2, 2); // cache is {1=1, 2=2} printf("%d\n", lRUCacheGet(lRUCache, 1)); // return 1 lRUCachePut(lRUCache, 3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} printf("%d\n", lRUCacheGet(lRUCache, 2)); // returns -1 (not found) lRUCachePut(lRUCache, 4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} printf("%d\n", lRUCacheGet(lRUCache, 1)); // return -1 (not found) printf("%d\n", lRUCacheGet(lRUCache, 3)); // return 3 printf("%d\n", lRUCacheGet(lRUCache, 4)); // return 4 lRUCacheFree(lRUCache); return 0; } ``` 編譯並執行下列程式可以得到以下輸出 ```shell $ ./LRU.out 1 -1 -1 3 4 ``` ### LRU cache 設計概念 * 替換機制: 當 cache 滿的時候, 將最久沒用到的資料移出去 * Put: 會分為下列情形 * cache 還有空位: 將 data 放入, 且更新 least recently used element * cache 沒有空位: 透過 least recently used element 決定要將哪個 element 置換出去, 也需要更新 least recently used element * Get: 會分為下列情形 * 有查到: 將 data 回傳, 同時更新 least recently used element * 沒查到: 以 -1 當成 invalid data, 直接回傳當作查詢失敗, 不需更新 least recently used element * 資料結構: 為了滿足快速查詢以及維持 least recently used element 的操作, 分別設計了一個簡單的 hash_map 來做查詢, 以及一個 doubly circular linked list, 以 list 的 last_entry 來辨別 least recently used element * hhead 和 hlink 用來串連有同樣 hash value 的 LRUNode * dhead 和 dlink 串連所有的 LRUNode 接下來講解程式碼的部份 ### LRUCache & LRUNode 的結構定義 ```c typedef struct { int capacity, count; struct list_head dhead, hheads[]; } LRUCache; typedef struct { int key, value; struct list_head hlink, dlink; } LRUNode; ``` * 在 LRUCache 中是不帶 node 的資料的, 裡面只存了 cache 的最大容量和目前容量兩個資訊, 以及數個 list_head 來作為 LRUNode 的 head * capacity: 最大容量 * count: 當前容量 * dhead: 指向 LRUNode, 可以用 dlink 找到所有 Node 的資料 * 為 circular doubly 的結構 * hheads: 數量取決於 capacity 的大小, 指向有同樣(與 hhead 的 index 相等) hash_value 的 LRUNode, 從 hlink 找出去只能找到有同樣 hash_value 的 node * 非 circular 的結構 * LRUNode 負責裡面有 hlink 與 dlink 維持 list 的結構, 此外 key 與 value 也是 node 負責儲存 ### lRUCacheCreate ```c LRUCache *lRUCacheCreate(int capacity) { LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head)); obj->count = 0; obj->capacity = capacity; INIT_LIST_HEAD(&obj->dhead); for (int i = 0; i < capacity; i++) INIT_LIST_HEAD(&obj->hheads[i]); return obj; } ``` * 首先會為 obj 分配記憶體空間, 除了 obj 自身的大小外, 還須算上有多少 hheads, 而 hheads 的數量由 capcacity 決定, 因此將他的 size 與 capacity 相乘 * 再來將所有的 list 初始化, 透過 INIT_LIST_HEAD 讓他們的 next 與 prev 都指向自己 ### lRUCachePut ```c= void lRUCachePut(LRUCache *obj, int key, int value) { LRUNode *lru; int hash = key % obj->capacity; list_for_each_entry (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); lru->value = value; return; } } if (obj->count == obj->capacity) { lru = list_last_entry(&obj->dhead, LRUNode, dlink); list_del(&lru->dlink); list_del(&lru->hlink); } else { lru = malloc(sizeof(LRUNode)); obj->count++; } lru->key = key; list_add(&lru->dlink, &obj->dhead); list_add(&lru->hlink, &obj->hheads[hash]); lru->value = value; } ``` * 當想要把東西放進 cache 時, 首先計算傳入的 key 會對應的 hash value * 第 5 到 9 行是沿著對應的 hhead 出發查看是否有相同的 key 已經存在 cache 中, 如果有的話就將它移動到 dhead 的 head 端, 代表剛被存取過, 由於已存在所以不需要新增資料, 因此只更新 value 便可以結束 * 第 12 到 19 行在確認 cache 是否以滿, 若滿了的話則找出 least recently used element 把它移除 cache, 根據我們的設計 least recently used element 必會存在 dhead 這條 list 的 tail 端, 若 cache 還有位置則直接分配空間, 然後將 count 遞增 * 第 20 到 23 行是將 LRUNode 分別串上 hlist 與 dlist, 位置分別會是對應 hlist 的最尾端和 dlist 的最前端, 同時將參數傳入的 key 與 value 指派給 lru #### 以下為例圖, 其中省略了部份的 prev link, 兩張圖的 Node 是相同的 ![](https://i.imgur.com/Osiw2MP.jpg) * hheads 會指向所有持有同樣 hash value 的 Node, 因此可以做到快速查詢 ![](https://i.imgur.com/Rd5NkNg.jpg) * dhead 則是指向所有的 Node, 並且透過 dhead->prev 可以快速找到 least recently used element ### lRUCacheGet ```c int lRUCacheGet(LRUCache *obj, int key) { LRUNode *lru; int hash = key % obj->capacity; list_for_each_entry (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); return lru->value; } } return -1; } ``` * 要從 cache 內拿取資料時同樣要先計算 hash value, 再從對應的 hhead 出發, 如果有 key 配對上了則將這個 Node 移動到 dhead 的 head 端, 並回傳對應的 value, 否則回傳 -1 表示 cache miss ### lRUCacheFree ```c void lRUCacheFree(LRUCache *obj) { LRUNode *lru, *n; list_for_each_entry_safe (lru, n, &obj->dhead, dlink) { list_del(&lru->dlink); free(lru); } free(obj); } ``` * 由於我們能透過 dlink 找到所有的資料, 因此沿著 dhead 沿路將記憶體是空間釋放出來即可, 最後再把 cache 給 free 就結束了 ### 解題思路 #### MMM1 ```c= void lRUCacheFree(LRUCache *obj) { LRUNode *lru, *n; MMM1 (lru, n, &obj->dhead, dlink) { list_del(&lru->dlink); free(lru); } free(obj); } ``` * 這段程式碼位於 lRUCacheFree 裡面, 可以看到第 5, 6 在 delete , 為了確保不會丟失 list 的資訊這邊應該選擇 ```list_for_each_entry_safe``` #### MMM2 ```c= int lRUCacheGet(LRUCache *obj, int key) { LRUNode *lru; int hash = key % obj->capacity; MMM2 (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); return lru->value; } } return -1; } ``` * 當我們想確認某個元素是否存在 cache 裡面時必須走過對應 hhead 延伸出去的 list 才能確定結果是 hit or miss, 因此在這裡選擇 ```list_for_each_entry``` #### MMM3 MMM4 ```c= void lRUCachePut(LRUCache *obj, int key, int value) { LRUNode *lru; int hash = key % obj->capacity; MMM3 (lru, &obj->hheads[hash], hlink) { if (lru->key == key) { list_move(&lru->dlink, &obj->dhead); lru->value = value; return; } } if (obj->count == obj->capacity) { lru = MMM4(&obj->dhead, LRUNode, dlink); list_del(&lru->dlink); list_del(&lru->hlink); } else { lru = malloc(sizeof(LRUNode)); obj->count++; } lru->key = key; list_add(&lru->dlink, &obj->dhead); list_add(&lru->hlink, &obj->hheads[hash]); lru->value = value; } ``` * MMM3 出現的形式與 MMM2 類似, 都是要走訪整個 list 因此選 ```list_for_each_entry``` * MMM4 出現於 15 行, 先看 14 行的條件為當 cache 滿的時候才成立, 根據 LRU 設計的原則這時候我們需要找出 least recently used element, 將它移出 list 而因為我們選擇將 least recently used element 維持在 list 的 tail, 因此使用 ```list_last_entry``` 可以直接找出最後元素, 並將其移除 ## Q4. LeetCode 128. Longest Consecutive Sequence ```c= #include <stdio.h> #include <stdlib.h> #include "list.h" struct seq_node { int num; struct list_head link; }; static struct seq_node *find(int num, int size, struct list_head *heads) { struct seq_node *node; int hash = num < 0 ? -num % size : num % size; list_for_each_entry (node, &heads[hash], link) { if (node->num == num) return node; } return NULL; } int longestConsecutive(int *nums, int n_size) { int hash, length = 0; struct seq_node *node; struct list_head *heads = malloc(n_size * sizeof(*heads)); for (int i = 0; i < n_size; i++) INIT_LIST_HEAD(&heads[i]); for (int i = 0; i < n_size; i++) { if (!find(nums[i], n_size, heads)) { hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size; node = malloc(sizeof(*node)); node->num = nums[i]; list_add(&node->link, &heads[hash]); } } for (int i = 0; i < n_size; i++) { int len = 0; int num; node = find(nums[i], n_size, heads); while (node) { len++; num = node->num; list_del(&node->link); int left = num, right = num; while ((node = find(++left, n_size, heads))) { len++; list_del(&node->link); } while ((node = find(--right, n_size, heads))) { len++; list_del(&node->link); } length = len > length ? len : length; } } return length; } ``` ### 解題思路從 longestConsecutive 函式看起, 一開始會先建立 n_size 個 heads 作為 hash 的 bucket * 第 30 行開始的 for 迴圈會先讀過整個 nums , 並且到對應的 bucket 查詢是否以存在, 題目中的輸入數字可能會重複, 但解答時不需紀錄這些重複數字, 因此重複的部份會忽略, 而其餘部份會根據 hash value 加入到對應的 heads * 第 39 行正式開始解題的環節, 再度用一個 for 迴圈看過整個 nums , 並且每個回合以 ```nums[i]``` 作為中心點開始向更大還有更小的數做查詢 * 第 48 行將 left, right 設定為 num, 但我們想知道更大以及更小的結果是否存在, 因此將 ```++``` ```--``` 放在前面讓這個運算可以先發生, 再開始查詢, 如果有查到的話則可以將該回合的結果 len + 1, 同時將 node 刪除後繼續往更大或更小的數字查詢 * 最後根據該回合結果看是否需要更新最後的回傳值 length, 等到整個迴圈跑完後將 length 回傳即可得到解答 ## TODO 補圖

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.