# 2022q1 Homework1 (quiz1)
contributed by < `jim12312321` >
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗1 ： <br>利用 linux kernel 風格的 hash table 實作 Leecode No.1 Two Sum
首先我們先將測驗 1 中的題目程式碼，依照函式拆程若干個部份並分別解釋。
### 結構宣告
```cpp
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;
#define MAP_HASH_SIZE(bits) (1 << bits)
```
- hlsit_node
在 `hlist_node` 結構中可以看到有提供兩子結構，分別為 `next` 和 `pprev` 。其中 `next` 是 `hlist_node` 的指標，所以他應該指向下一個 `hlist_node` ；而 `pprev` 是指標的指標，所以他應該指向前一個 `hlist_node *` ，也就是前一個 `hlist_node` 的指標。
- hlist_head
而 `hlist_head` 就比較簡單了，裡面只有一個子結構 `first` 用以指向第一個節點。
- map_t
裡面的 `bits` 用來初始化 hash table 的大小
- MAP_HASH_SIZE
用來指定該初始化多大的雜湊表（以 2 的冪作為初始大小）
:::warning
power of 2 的翻譯是「2 的冪」，不是「冪次」
:notes: jserv
:::
架構示意圖
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
num[label="2^bits",shape=plaintext]
head[label ="<h>||<f>list_head.first\n||<e>",width = 1.5]
node_1[label = "<m>hlist_node_1 | {<p>pprev \n| <n>next \n}",width = 1.5];
node_2[label = "<m>hlist_node_2 \n| {<p>pprev | <n>next \n}",width = 1.5];
node_3[label = "<m>hlist_node_3 | {<p>pprev \n| <n>next \n}",width = 1.5];
etc_next[shape = plaintext,label = "..."]
num->head -> node_1 -> node_2 -> node_3 -> etc_next[
weight = 10, style = invis
]
head:h -> head:e[dir=both];
head:f -> node_1:m;
node_1:p -> head:f;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> etc_next;
}
```
### hash table 初始化
```cpp
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` 的大小，將 hash table 初始化成長度為 $2^{bits}$ 的 hash table 。
### hash key, 一些 marco 和 hash function
```cpp=
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
這段程式用來描述一個 `hash_key` 的結構，其中 `key` 用來儲存對應的 `hash key` ， `data` 用來儲存資料（在這題中就是準備用來找兩數之和的數字的索引值）， `hlist_node` 則是用以提供各式操作的結構。
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
hk[label="hash_key |{key|data|node}"]
}
```
```cpp=
#define container_of(ptr, type, member)
({
void *__mptr = (void *) (ptr);
((type *) (__mptr - offsetof(type, member)));
})
```
`container_of` 用以透過子結構提取上層結構
```cpp
#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` 利用 `val * GOLDEN_RATIO_32` 製造雜湊值，又因如老師在註解提到的高位較具隨機性，因此 shift 32 bits 後回傳成雜湊值。
:::info
無聊去查了一下 `GOLDEN_RATIO_32` 為什麼要設定成那個值，明明 1640531527 (0x61C88647 轉成 10 進位後的值) 看起來跟黃金比例沒什麼關係呀？
原來這是 $2^{32}\times(1-\frac{1}{φ})$ 的近似值 （$φ$ 就是黃金比例），而且在 linux kernel 中也是用他來實作 hash 呢。
Link: [linux code](https://elixir.bootlin.com/linux/v4.7/ident/GOLDEN_RATIO_32)
:::
> TODO: 以 $\LaTeX$ 語法重新排版數學表示式
> :notes: jserv
### 取得 hash_key 中的 data
```cpp
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
若 `map` 中存在對應的 `key` ，則將 `hash_key` 中的 `data` 回傳，否則回傳 NULL 。
### 將新的值加入 hash table
```cpp
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 所對應的 hash table 位置，並設定該位置中的第一個節點
```cpp
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
```
接著先做 `AAA` ，然後如果 `first` 不是 NULL ，則將該 `hash` 值的 `linked list` 做成雙向鏈結串列，之後將原先的 `first` 替換成 `n` ，最後做 `BBB` 。
```cpp
AAA;
if (first)
first->pprev = &n->next;
h->first = n;
BBB;
```
==因此可以知道我們還缺乏設定新節點的 `pprev` 和 `next`==
所以可知
`AAA : n->next = first`
`BBB : n->pprev = &h->first`
### 清除 hash table
```cpp
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);
}
```
將 hash table 中所有佔用的記憶體空間釋放
### 重看 Two Sum
```cpp
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 table
2. 初始化一個空間儲存要回傳的索引值
3. 依序找尋數字陣列
3-1.
若某數字和目標之差值 `target - nums[i]` 已經存在於 hash table ，則將當前數字與存於 hash table 中的索引值取出，並且離開 for-loop
3-2.
若沒有找到則將當前數字，當前數字的索引值加入 hash table
4. 釋放 hash table 所佔之記憶體除存空間並回傳找到的答案
:::warning
TODO: 延伸題目2
:::
---
## 測驗2 ： 實作 LeetCode 82.
本測驗為實做 [LeetCode 82](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 的程式碼填空
[LeetCode 82](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 中要答題者將重複的節點全部移除
### 架構宣告
```cpp
struct ListNode {
int val;
struct ListNode *next;
};
```
該架構裡面存有一個屬性( `val` 用來儲存該結點的值)和另一個架構( `next` 用來指向下一個 `ListNode` )
:::warning
什麼叫做「子架構」？用語要精準
:notes: jserv
:::
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
hk[label="{ListNode|{val|next}}"]
}
```
```cpp
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;
}
```
步驟解析：
1. 判斷陣列是否存在
1-1. 不存在則回傳 NULL
1-2. 存在則繼續 2.
2. 判斷 `COND1` 有沒有發生
2-1. 若沒有則往 4.
2-2. 若有則往 3.
3. 若 `COND2` 存在則 head 繼續往後移動，然後對 head->next 繼續進行一次 `deleteDuplicates()`
4. 對 head->next 進行一次 `deleteDuplicates()` ，然後回傳 head
<br>
可知在第2點中， `COND1` 應該要可以判斷是否要發生重複的情況（當然重複的前提就是下個節點還存在），因此可得知
$\rightarrow$ `COND1 = head->next && head->val == head->next->val`
<br>
然後由於所有重複的都必須移除，因此在 `COND2` 終須判斷是否下下一個仍然存在且為同一個值，因此可推斷
$\rightarrow$ `COND2 = head->next->next && head->next->val == head->next->next->val`
但由於題目要求要最精簡程式碼，而只要將 head = head->next 就能用 `COND1` 的解法取代掉原本我認為的 `COND2` 的解法，因此可知
$\rightarrow$ `COND2 = head->next && head->val == head->next->val`
### 嘗試不用遞迴寫出 LeetCode 82
廢話不多說，先貼程式碼
```cpp=
struct ListNode* deleteDuplicates(struct ListNode* head){
struct ListNode **indirect = &head,*dup;
while((*indirect) && (*indirect)->next){
while((*indirect)->next && (*indirect)->val != (*indirect)->next->val)
indirect = &(*indirect)->next;
dup = (*indirect);
while(dup->next && dup->val == dup->next->val)
dup = dup->next;
if(dup->next){
*indirect = dup->next;
}else if(*indirect != dup){
*indirect = NULL;
}
}
return head;
}
```
步驟解析：
1. 判斷 `*indirect` (就是 `head`) 以及 `*indrect->next` 是否存在，若有其中有一者不存在，則跳出迴圈，回傳 `head` ；否則繼續步驟 2
2. 當目前 node 中的值與下一個 node 中的值不相同時，則繼續走訪 list (當然也要判斷下一個 node 是否還存在)
:::info
離開步驟 2 時有兩種情況，但在步驟 3 中沒有先對這兩種情況判斷<br>$\rightarrow$ I. 下一個結點中的值與目前結點中的值不相同 <br>$\rightarrow$ II. 下一個結點不存在
:::
3. 令 `dup` 為當前結點，並判斷後續 list 中有多少與之重複的值(當然也還是要判斷下一個結點是否存在)
4. 判斷以下兩種狀況<br>$\rightarrow$ I. 若下一個結點存在，則表示還需繼續往後檢查且此時重複的那個節點並不是 list 中的最後一個結點，因此將 `*indirect` 指向 `dup->next`<br>$\rightarrow$ II. 若下一個結點不存在且 `*indirect != dup` (這樣的情況就代表最後一個結點與前面有相同值，需移除， e.g. [1,2,3,3]) ，則將 `*indirect` 指向 NULL
:::warning
雜記:
這算是真正第一次自己利用`a pointer of a pointer` 做出題目。
還蠻開心的，不過最後還是躲不掉要進行步驟 4. 的判斷，不知道還能不能更簡化，但是目前想不到了，先這樣。
:::
:::warning
TODO: 延伸問題2
:::
---
## 測驗3 ： 實作 LeetCode 146.
本測驗為結合 [lab0-c](https://github.com/sysprog21/lab0-c) 所提供的 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 實作 linux 風格的 [LRU Cache](https://leetcode.com/problems/lru-cache/)
### 題目簡述
這題希望建構一個實作一個 LRU Cache ，建構結構體 LRUCache 並提供以下函式
- lRUCacheCreate(int capacity)
建立一個有大小為 `capacity` 的 LRU Cache
- lRUCacheFree(LRUCache *obj)
將 LRU Cache 中所有空間釋放
- lRUCacheGet(LRUCache *obj, int key)
搜尋 LRU Cache 中是否有指定的 `key` ，若有則回傳該值，沒有則回傳 -1
- lRUCachePut(LRUCache *obj, int key, int value)
用特定的 `key` 將 `value` 插入 LRU Cache 中，若 `key` 已存在則更新 LRU Cache 中同樣 `key` 中的值，若沒有則將最少使用的 `key` 移除，再將這對 `key-value` pair 加入 LRU Cache 。
### 架構宣告
```cpp=
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
- LRUCache
- capacity: 用以紀錄 LRU Cache 中有多少 `hhead` 的儲存空間
- count: 用以記錄目前 LRU Cache 中有多少 `hlink`
- dhead: 用以紀錄 key 之間最近一次被使用次序的 linked list 的 head
- hheads: 用以紀錄不同 hash 值的 linked list 的 head
- LRUNode
- key: 用以紀錄結點中的 key
- value: 用以紀錄結點中的 value
- dlink: 加在 `dhead` 後的 linked list 結點，排序排在越前面代表越近期被使用
- hlink: 加在 `hhead` 後的 linked list 結點，會依照 key 值所分配到的 hash 值加在對應的 `hhead` 後。
e.g.
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
cache[label="{LRUCache|{capacity = 2|count|<d>dhead|<h0>hheads[0]|<h1>hheads[1]}}"]
node_1[label="{LRUNode1|{key|value|<d>dlink|<h>hlink}}"]
node_2[label="{LRUNode2|{key|value|<d>dlink|<h>hlink}}"]
cache->node_1->node_2[weight = 10, style = invis];
cache:d -> node_1:d:w[color="blue"];
cache:h0 -> node_1:h:w;
node_1:d -> node_2:d:w[color="blue"];
cache:h1 -> node_2:h:w;
}
```
### 建置新的 LRU Cache
```cpp
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;
}
```
初始化新的 LRU Cache 並為其配置記憶體空間，配置好的新結點 (`list_head`) 也要進行初始化，將其變成雙向鏈結 linked list 。
### 釋放 LRU Cache 所佔據的記憶體空間
```cpp=
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
釋放架構空間時要走訪所有結點並逐一釋放，最終再釋放 Cache 本身。
==因為要走訪 linked list 中所有結點且在這個過程中要釋放該結點，因此我們可以知道必須使用 safe 模式的 linked list 走訪==
$\rightarrow$ `MMM1 = list_for_each_entry_safe`
### 取得 Cache 中的特定值
```cpp=
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;
}
```
依照特定的 hash 值走訪 Cache 中相對應的 `hheads[hash]` 並將該結點移到 `dhead` 的第一個結點。
e.g. 找 key2
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
cache[label="{LRUCache|{capacity = 2|count|<d>dhead|<h0>hheads[0]|<h1>hheads[1]}}"]
node_1[label="{LRUNode1|{key1|value1|<d>dlink|<h>hlink}}"]
node_2[label="{LRUNode2|{key2|value2|<d>dlink|<h>hlink}}"]
cache->node_1->node_2[weight = 10, style = invis];
cache:d -> node_1:d:w[color="blue"];
cache:h0 -> node_1:h:w;
node_1:d -> node_2:d:w[color="blue"];
cache:h1 -> node_2:h:w;
}
```
將 Node2 的 `dlink` 移到 `dhead` 的最前面。
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
cache[label="{LRUCache|{capacity = 2|count|<d>dhead|<h0>hheads[0]|<h1>hheads[1]}}"]
node_1[label="{LRUNode1|{key1|value1|<d>dlink|<h>hlink}}"]
node_2[label="{LRUNode2|{key2|value2|<d>dlink|<h>hlink}}"]
cache->node_1->node_2[weight = 10, style = invis];
cache:d -> node_1:d:w[color="blue"];
cache:h0 -> node_1:h:w;
cache:h1 -> node_2:h:w;
}
```
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
cache[label="{LRUCache|{capacity = 2|count|<d>dhead|<h0>hheads[0]|<h1>hheads[1]}}"]
node_1[label="{LRUNode1|{key1|value1|<d>dlink|<h>hlink}}"]
node_2[label="{LRUNode2|{key2|value2|<d>dlink|<h>hlink}}"]
cache->node_2->node_1[weight = 10, style = invis];
cache:d -> node_2:d:w[color="blue"];
cache:h0 -> node_1:h:w;
node_2:d -> node_1:d:w[color="blue"];
cache:h1 -> node_2:h:w;
}
```
==因為要走訪 linked list 中所有結點但不需要在這個過程中釋放該結點，因此可以不用使用 safe 模式的 linked list 走訪==
$\rightarrow$ `MMM2 = list_for_each_entry`
### 將特定的值依據 key 放進 Cache
```cpp=
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;
}
```
依照特定的 key 放進 Cache 中。若該 key 已經存在，則更新 key 中的值並返回。若不存在則將最沒被使用的值移除 (`dhead` 中的最後一個結點)並將新結點放進對應的 `hheads[hash]` 中與 `dhead` 中的第一個。
e.g. put(key3,value3)
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
cache[label="{LRUCache|{capacity = 2|count|<d>dhead|<h0>hheads[0]|<h1>hheads[1]}}"]
node_1[label="{LRUNode1|{key1|value1|<d>dlink|<h>hlink}}"]
node_2[label="{LRUNode2|{key2|value2|<d>dlink|<h>hlink}}"]
node_3[label="{LRUNode3|{key3|value3|<d>dlink|<h>hlink}}"]
cache->node_1->node_2[weight = 10, style = invis];
cache:d -> node_1:d:w[color="blue"];
cache:h0 -> node_1:h:w;
node_1:d -> node_2:d:w[color="blue"];
cache:h1 -> node_2:h:w;
}
```
將最沒有被使用的 Node 移除。
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
cache[label="{LRUCache|{capacity = 2|count|<d>dhead|<h0>hheads[0]|<h1>hheads[1]}}"]
node_1[label="{LRUNode1|{key1|value1|<d>dlink|<h>hlink}}"]
node_2[label="{LRUNode2|{key2|value2|<d>dlink|<h>hlink}}"]
node_3[label="{LRUNode3|{key3|value3|<d>dlink|<h>hlink}}"]
cache->node_3->node_1[weight = 10, style = invis];
cache:d -> node_3:d:w[color="blue"];
cache:h0 -> node_3:h:w;
node_3:d -> node_1:d:w[color="blue"];
cache:h1 -> node_1:h:w;
}
```
在 `MMM3` 所在的那一段中，需要走訪對應 hash 的 linked list(hheads[hash]) 並尋找 `key` 是否已經存在。
==因此我們可以知道需要走訪 linked list 並且不需要在這個過程中移除結點，因此可以使用非 safe 的走訪版本==
$\rightarrow$ `MMM3 = list_for_each_entry`
在 `MMM4` 所在的那一段中，需要走訪對應 hash 的 linked list(hheads[hash]) 的最後一個結點並將其移除。
==因此我們可以知道需要走訪 linked list 中的最後一個結點==
$\rightarrow$ `MMM4 = list_last_entry`
:::warning
TODO: 延伸問題 1 中的改進與測試、2
:::
---
## 測驗4： 實作 LeetCode 128.
本測驗為結合 [lab0-c](https://github.com/sysprog21/lab0-c) 所提供的 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 實作 linux 風格的 [Find Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/)
### 題目簡述
在一個未被排序過的 array 中尋找最長的連續序列( e.g. [1,2,3] $\rightarrow$ 連續序列)
### 架構宣告
```cpp=
struct seq_node {
int num;
struct list_head link;
};
```
- seq_node
- num: 紀錄該結點中的數值
- link: 該結點中用以形成 linked list 的架構
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
seq_node[label="{seq_node|{num|link}}"]
}
```
### 尋找特定值
```cpp=
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;
}
```
在 linked list 中尋找特定的 `num` 若存在就回傳他所在的結點，若無則回傳 NULL。
### 找最長的連續序列
```cpp=
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(LLL, n_size, heads))) {
len++;
list_del(&node->link);
}
while ((node = find(RRR, n_size, heads))) {
len++;
list_del(&node->link);
}
length = len > length ? len : length;
}
}
return length;
}
```
步驟解析:
1. 根據 `n_size` 設立一個 `heads` 並初始化其中所有 `head`
2. 走訪 `nums` 中的所有值，並且如果該值並未在 `heads` 中的任一 `head` 找到，就將該值新增進對應的 `head`
3. 走訪 `nums` 中的所有值，並且尋找該值在 `heads` 中有沒有形成連續序列，首先先往當前的 `head` 的左側(較小側)走訪，若遇到不連續則終止。接著對右邊也進行相同的事情，最後存取當前找到最長的長度
==我們可以知道在 `LLL` 中，應該要往當前數值的左側(比當前數值還小的那側)走訪，且應該先 -1 (因為 `left = num`)==
$\rightarrow$ `LLL = --left`
==我們可以知道在 `RRR` 中，應該要往當前數值的右側(比當前數值還大的那側)走訪，且應該先 +1 (因為 `right = num`)==
$\rightarrow$ `RRR = ++right`
:::warning
TODO: 延伸問題 1 中的改進與測試、2
:::
Sign in with Wallet
Connect another wallet