# 2022q1 Homework1 (quiz1) contributed by < Korin777 > ## Q1 ### 延伸題目一 #### 函式功能: 1. map_init 用來建立 hash table map_t 的各個 hlist_head , ht 的數量為2的冪 graphviz digraph structs { rankdir=LR node[shape=record] e1 [label=" <first> ht[0].first| <second> ht[1].first | <third> ht[2].first | <forth> ht[3].first"]; node[shape=none]; null_1[label = NULL] e1:first->null_1 e1:second->null_1 e1:third->null_1 e1:forth->null_1 }  2. find_key 查詢 key 存在與否 , 透過 hash function 及 key 得到特定 ht[i] 並遍歷 ht[i] 找尋是否存在 key , 有的話回傳此 hash_key 指標 , 沒有則回傳 NULL 3. map_get 查詢 key 的 data , 透過 find_key 是否回傳 hash_key 指標來決定回傳對應的 data 指標或 NULL 5. map_add 增加 ht[i] 的節點 , 節點會增加在 ht[i].first , 先透過 find_key 查詢 key 是否存在 , 不存在再增加節點 graphviz digraph structs { rankdir=LR node[shape=record]; e1 [label="<p> ht[i].first "]; node[shape=record]; e2 [label=" <h>hlist_node | {<p> pprev | <n>next }"]; node[shape=record]; e3 [label=" <h>hlist_node | {<p> pprev | <n>next }"]; node[shape=none]; NULL [label="NULL"]; e1:p->e2:h; e2:p->e1; e2:n->e3:h; e3:p->e2:n; e3:n->NULL; subgraph cluster_0 { style=filled; color="green"; label="new node"; e2; } }  6. map_deinit 釋放 hash table 所配置過的記憶體 , 每個 ht[i] 的各個節點依照由頭到尾的順序釋放 hash_key->data 及 hash_key , 最後再釋放整個 map_t ## Q2 ### 延伸題目一 * new_head 為移除重複節點後的 head * prev_node 用來修正上個非重複節點的下個節點 c struct ListNode *deleteDuplicates(struct ListNode *head) { if (!head) return NULL; struct ListNode *new_head = NULL, *prev_node = NULL; while(head) { while (head->next && head->val == head->next->val) // skip duplicate node head = head->next; if(prev_node) { // fix previous non-duplicate node's next if(prev_node->next != head) prev_node->next = head; else prev_node = head; } if(!new_head && head->next && head->val != head->next->val) { // Init new head new_head = head; prev_node = new_head; } head = head->next; } if(prev_node) { // fix previous non-duplicate node's next if(prev_node->next != head) prev_node->next = head; } return new_head; }  ### 延伸題目二 * 將 ListNode 結構改為作業的 circular doubly-linked list 結構 c struct list_head { struct list_head *prev; struct list_head *next; }; typedef struct { int value; struct list_head list; } element_t;  #### 迭代 * tmp 為整數指標 , 用來表示當前的重複數字 * tmp 為 NULL 或 tmp 和當前 entry 的數字不同 , 就看下個 entry 的數字是否與當前 entry 數字相同 , 來判斷是否該移除當前 節點及釋放對應的記憶體 * tmp 和當前 entry 的數字相同 , 直接移除當前節點及釋放對應的記憶體 * 若 tmp 最後不為 NULL 要釋放 tmp 記憶體 c void deleteDuplicates(struct list_head *head) { if (!head) return; int *tmp = NULL; element_t *ele, *tmpele; list_for_each_entry_safe (ele, tmpele, head, list) { if (!tmp || tmp != ele->value) { if (ele->list.next && ele->list.next != head) { element_t *elen = list_entry(ele->list.next, element_t, list); if (elen->value == ele->value) { if (!tmp) tmp = malloc(sizeof(int)); tmp = ele->value; list_del(&ele->list); free(ele->value), free(ele); } } } else { list_del(&ele->list); free(ele->value), free(ele); } } if (tmp) free(tmp); return; }  #### 遞迴 * realhead 傳進 circular doubly-linked list 的 head（不作為 entry 存放 value 的節點）, 用來判斷 list 是否以遍歷完 * 如果 head 與它之後的節點 value 重複則移除這段節點 , 並對下個非重複節點呼叫 deleteDuplicates c void deleteDuplicates(struct list_head *head, struct list_head *realhead) { if (!realhead || list_empty(realhead) || list_is_singular(realhead)) return; element_t *ele, *elen; if(head != realhead && head->next != realhead) { ele = list_entry(head, element_t, list); elen = list_entry(head->next, element_t, list); if (ele->value == elen->value) { /* Remove all duplicate numbers */ while (ele->value == elen->value) { head = head->next; list_del(&ele->list); free(ele->value), free(ele); if(head->next == realhead) { // finish list traversal list_del(&elen->list); free(elen->value), free(elen); return; } ele = list_entry(head, element_t, list); elen = list_entry(head->next, element_t, list); } list_del(&ele->list); free(ele->value), free(ele); return deleteDuplicates(head->next, realhead); } } else // finish list traversal return; return deleteDuplicates(head->next, realhead); }  ## Q3 #### 資料結構 * LRUCache 結構如下 , capacity=5 為 hheads 數量及總共能存的 LRUNode 數量 , count=5 為目前 LRUNode 數量 , 能透過 dhead 或 hheads[i] 來取得 LRUNode graphviz digraph structs { rankdir=LR node[shape=record] h1 [label=" <d>dhead |<h0> hheads[0]| <h1> hheads[1] | <h2> hheads[2] | <h3> hheads[3] | <h4> hheads[4]"]; node[shape=record]; e1 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next } | <d>dlink1 | {<p1> prev | <n2>next }"]; node[shape=record]; e2 [label="{key | value } |<h>hlink2 | {<p> prev | <n>next } | <d>dlink2 | {<p1> prev | <n2>next }"]; node[shape=record]; e3 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next } | <d>dlink3 | {<p1> prev | <n2>next }"]; node[shape=record]; e4 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next } | <d>dlink4 | {<p1> prev | <n2>next }"]; node[shape=record]; e5 [label="{key | value } |<h>hlink2 | {<p> prev | <n>next } | <d>dlink5 | {<p1> prev | <n2>next }"]; h1:h0->e1:h e1:n->e2:h h1:h1->e3:h h1:h2->e4:h e4:n->e5:h h1:d->e1:d e1:n2->e2:d e2:n2->e3:d e3:n2->e4:d e4:n2->e5:d }  * 透過 hheads[i] , 只能拿到屬於這個區塊的 LRUNode graphviz digraph structs { rankdir=LR node[shape=record]; e1 [label="<h> hheads[i] | {<p> prev | <n>next }"]; node[shape=record]; e2 [label="<h>hlink1 | {<p> prev | <n>next }"]; node[shape=record]; e3 [label="<h>hlink2 | {<p> prev | <n>next }"]; node[shape=record]; e1:n->e2:h; e2:p->e1:h; e2:n->e3:h; e3:p->e2:h; e3:n->hheads; e1:p->hlink2 subgraph cluster_0 { style=filled; color="green"; label="LRUNode"; e2; } subgraph cluster_1 { style=filled; color="yellow"; label="LRUCache"; e1; } subgraph cluster_3 { style=filled; color="green"; label="LRUNode"; e3; } }  * 透過 dhead 可以遍歷所有的 LRUNode , LRUNode 越後面表示越久沒用到 graphviz digraph structs { rankdir=LR node[shape=record]; e1 [label="<d> dhead | {<p> prev | <n>next }"]; node[shape=record]; e2 [label="<h>dlink1 | {<p> prev | <n>next }"]; node[shape=record]; e3 [label="<h>dlink2 | {<p> prev | <n>next }"]; node[shape=record]; e1:p->dlink2 e1:n->e2:h; e2:p->e1:d; e2:n->e3:h; e3:p->e2:h; e3:n->dhead subgraph cluster_0 { style=filled; color="green"; label="LRUNode"; e2; } subgraph cluster_1 { style=filled; color="yellow"; label="LRUCache"; e1; } subgraph cluster_3 { style=filled; color="green"; label="LRUNode"; e3; } }  #### 函式功能 1. lRUCacheCreate 用來建立 LRUCache 及其中的 hheads[] 2. lRUCacheFree 用來釋放 LRUCache 及其所擁有的 LRUNode 3. lRUCacheGet 透過 key 來取得 LRUCache 對應的 LRUNode->value , 如果不存在則回傳 -1 4. lRUCachePut * 新增或修改 LRUNode * 如果 key 存在會修改 LRUNode->value , 並將此 LRUNode->dlink 移到 LRUCache->dhead 最前面 , 表示最近用到 * 如果 key 不存在則會看 LRUCache->count 是否已達到 LRUCache->capacity , 是的話就移除 LRUCache->dlink 最後一個 LRUNode(最久沒用到) , 並新增新的 key-value 到該 LRUNode 並加到 LRUCache->dlink 及對應的 LRUCache->hheads[] , 反之則會配置一個新的 LRUNode 空間 ## Q4 ### 延伸問題一 #### 資料結構 題目結構如下 , nums = [100,4,200,1,3,2] 、 n_size=6 , heads 數量即為 n_size 數 , 每個 num 對 n_size 取餘數放到對應的 heads[num < 0 ? -num % size : num % size] graphviz digraph structs { rankdir=LR node[shape=record] h1 [label="<h0> heads[0]| <h1> heads[1] | <h2> heads[2] | <h3> heads[3] | <h4> heads[4] | <h5> heads[5]"]; e1 [label="<num>num=100 |<l>link | {<p> prev | <n>next }"]; e2 [label="<num>num=4 |<l>link | {<p> prev | <n>next }"]; e3 [label="<num>num=200 |<l>link | {<p> prev | <n>next }"]; e4 [label="<num>num=1 |<l>link | {<p> prev | <n>next }"]; e5 [label="<num>num=3 |<l>link | {<p> prev | <n>next }"]; e6 [label="<num>num=2 |<l>link | {<p> prev | <n>next }"]; h1:h0->e3:l e3:n->e1:l h1:h1->e4:l h1:h2->e6:l h1:h3->e5:l h1:h4->e2:l }  heads[i] 後面連結屬與此區塊的 seq_node graphviz digraph structs { rankdir=LR node[shape=record]; e1 [label="<h> heads | {<p> prev | <n>next }"]; node[shape=record]; e2 [label="num=200 | <h>link1 | {<p> prev | <n>next }"]; node[shape=record]; e3 [label="num=100 | <h>link2 | {<p> prev | <n>next }"]; node[shape=record]; e1:n->e2:h; e2:p->e1:h; e2:n->e3:h; e3:p->e2:h; e3:n->heads; e1:p->link2 subgraph cluster_0 { style=filled; color="green"; label="seq_node"; e2; } subgraph cluster_1 { style=filled; color="yellow"; label="list_head"; e1; } subgraph cluster_3 { style=filled; color="green"; label="seq_node"; e3; } }  #### 函式功能 1. find 用來尋找 num 是否存在對應 heads[i] 中 , 有就回傳此 seq_node , 沒有則回傳 NULL 2. longestConsecutive * 用來找出最長連續整數長度 * 首先配置長度 n_size 的 heads 並將 nums 的數字依序以 seq_node 的型態插入對應的 heads[i] * 遍歷 nums 中的數字 num , 如果 num 存在於對應 heads[i] 中 , 則繼續尋找與 num 相連的所有數字 * left 及 right 初始為 num ,left 表示比 num 小的相鄰數字 , right 則表示比 num 大的相鄰數字 * 持續將 left 減1並查詢其是否存在與對應 heads[i] , 存在的話將 heads[i] 中的 left 移除 , 反之則表示已經沒有比 num 小的相鄰數字 , 再來持續將 right 加1並查詢 right 是否存在與對應 heads[i] , 存在的話將 heads[i] 中的 right 移除 , 反之則表示已經沒有比 num 大的相鄰數字 * 更新最長相鄰數字的長度 #### 改進與實作 在 longestConsecutive 新增釋放記憶體的 code 避免 memory leak c 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); free(node); int left = num, right = num; while ((node = find(--left, n_size, heads))) { len++; list_del(&node->link); free(node); } while ((node = find(++right, n_size, heads))) { len++; list_del(&node->link); free(node); } length = len > length ? len : length; } } struct seq_node *seq, *tmp; for (int i = 0; i < n_size; i++) list_for_each_entry_safe(seq,tmp,&heads[i],link) list_del(&seq->link), free(seq); free(heads); return length; }  ### 延伸問題二 參考 Q1 的 hash table 實作 , 結構改為如下 c 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; struct hash_key { int key; void *data; struct hlist_node node; };  沿用 Q1 程式碼 , 並參考 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) __hlist_del 函式實作 map_del 用來移除 hash table 節點 hlist_node c void map_del(struct hlist_node *n) { struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; *pprev = next; if(next) next->pprev = pprev; }  修改 longestConsecutive , 以 map_t 來尋找最長連續整數長度 c int longestConsecutive(int *nums, int n_size) { map_t *map = map_init(10); int length = 0; for (int i = 0; i < n_size; i++) { int *p = map_get(map,nums[i]); if(!p) { p = malloc(sizeof(int)); *p = nums[i]; map_add(map,nums[i],p); } } for (int i = 0; i < n_size; i++) { int len = 0; int *num; struct hash_key *hk = find_key(map, i); while (hk) { len++; num = hk->data; int left = *num, right = *num; map_del(&hk->node); free(hk->data); free(hk); while ((hk = find_key(map,--left))) { len++; map_del(&hk->node); free(hk->data); free(hk); } while ((hk = find_key(map,++right))) { len++; map_del(&hk->node); free(hk->data); free(hk); } length = len > length ? len : length; } } map_deinit(map); return length; }  [題目連結](https://hackmd.io/@sysprog/linux2022-quiz1)