# 2022q1 Homework1 (quiz1)
contributed by < [Nomad1230](https://github.com/Nomad1230) >
## 第一題 - [LeetCode 1. Two Sum](https://leetcode.com/problems/two-sum/)
### map_init
```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;
#define MAP_HASH_SIZE(bits) (1 << bits)
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;
}
```
由以上程式碼可以看出 `map_t` 為整個雜湊表的結構體，內容儲存了 `int` 型別的 `bits` 以及 `struct hlist_head *` 型別的 `ht` ， `bis` 代表雜湊表的大小為 2 ^`bits` ， `ht` 則是 `struct hlist_head *` 陣列，陣列大小為 2 ^`bits` (如下圖中紅色框起來的部分)。
其中 `ht` 的每一個元素都會指向一條非環狀 doubly linked list。
hlist 架構示意圖:
### find_key
```c
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
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(key)` 的回傳值去查詢 hash table ，並走訪 `ht` 指向的 linked list 查詢有沒有對應的 `key` 。
### 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;
n->next = first; // AAA
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first; // BBB
}
```
此函式一開始會執行一次 `find_key` 若搜尋失敗，則會將搜尋失敗的 `key` 加入 linked list 中。
此題測驗的題目就是此函式的第12行及第16行，
可以看到在執行 `AAA` 之前已經將資料都存入節點中了，可想而知12~16行的目的是將節點加入 linked list 。
由於 linked list 的結構非環狀，因此節點全部都是由開頭插入，觀察第13、14行，此兩行的目的在於把 `first` 的 `pprev` 指向新增的節點。
另外因為 `pprev` 為 indirect pointer ，可以在不用造訪前一個節點的前提下，直接修改前一個節點的指標，提升程式效率，這樣的好處會體現在刪除節點上，由於這邊的程式碼是加入節點，所以實施的步驟跟一般 linked list 一樣多。
於是第12行要做的事情就是將欲新增的節點先指向 `first` ，這樣第13、14行才可以正確的把節點串接上，第15行把 `first` 變成新增的節點，最後第16行 `BBB` 把被新增的節點的 `pprev` 指回 `hlist_head` 。
流程圖如下:
1.
2.
3.
4.
5.
### 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);
}
```
此函式用來釋放整個 hlist 的記憶體，值得注意的是第七行 `*pprev = next` ，這行程式碼的用意是將節點從 linked list 中移除，只需要短短一行就可以移除當前節點，相當地有效率，也是使用 indirect pointer 的根本原因。
### GOLDEN_RATIO_PRIME
```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` 函式中發現使用到了 `GOLDEN_RATIO_32` 變數，其值為 0x61C88647 ，上網查了一下這個值，發現將這個值應用在 hash function 中可以將資料較為平均地分配在 hash table 中。
選這個值的原因詳細參考<[ThreadLocal的hash算法（關於0x61c88647）](https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/751048/)>，簡而言之就是這個數'剛好'有這個特性。
## 第二題 - [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
#### 原始程式碼
```c=
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
if (head->next && head->val == head->next->val) { // COND1
/* Remove all duplicate numbers */
while (head->next && head->val == head->next->val) // COND2
head = head->next;
return deleteDuplicates(head->next);
}
head->next = deleteDuplicates(head->next);
return head;
}
```
這道題目的問題是第13行及第15行的條件判斷該寫甚麼條件，答案很簡單，就只是確保下個節點不為空，並比較現在節點跟下個節點的資料相不相等，若相等就一直把指標往後移，移到出現不相等的資料為止並回傳指標，然後把回傳的指標跟開頭串接上，即可將重複的資料全部移除。
#### 將程式改成迭代版本
```c
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
void deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
struct ListNode *temp = head;
while (head != NULL) {
if (head->next && head->value == head->next->value) {
temp = head;
while(temp->next && temp->value == temp->next->value) {
temp = temp->next;
}
head->next = temp->next;
}
}
}
```
要從 recurive function 改成迭代，最簡單的方式就是多設一個變數來暫存資料，只要發現相同資料，就用`temp` 去往下走訪就好，刪除的方式相同就不贅述。
#### circular doubly-linked list (遞迴版本)
```c
#include <stddef.h>
struct ListNode {
int val;
struct list_head list;
};
struct list_head *deleteDuplicates(struct list_head *head)
{
if (!head)
return NULL;
struct list_head *temp = head;
head->prev->next = NULL;
if (temp->next && list_entry(temp, ListNode, list)->val
== list_entry(temp->next, ListNode, list)->val) {
/* Remove all duplicate numbers */
while (temp->next && list_entry(temp, ListNode, list)->val
== list_entry(head->next, ListNode, list)->val)
temp = temp->next;
return deleteDuplicates(temp->next);
}
struct list_head *result;
result = deleteDuplicates(head->next);
temp->next = result;
head->prev = result->prev;
result->prev->next = head;
result->prev = temp;
return temp;
}
```
以上是我初步的想法，跟原本的 recursive 最大的不同是我多使用了兩個變數來儲存資料，因為 circular doubly-linked list 的串接還要將 `prev` 指回前一個節點，所以每次搜尋的開頭都要儲存起來，讓搜尋完畢後可以把最尾端的節點指向開頭。
但這樣寫有一個問題，就是第一次執行函式時要開始搜尋的節點是 `head->next` ，而之後每次的重複呼叫都是從 `head` 開始搜尋，以目前的程式碼來看，第一次呼叫 `list_entry(temp, ListNode, list)->value` 時程式就會出錯，因為此時 `head` 為單純的指標而沒有被包裹成 `ListNode *` 的型別。
目前我想到的解決方案是將函式的參數多一個 `count` 使其第一次進入函式時將 `temp` 指向後一個節點，但這樣感覺有點大費周章，之後想到更好的方式改良再來更新。
改良程式碼如下:
```c
struct list_head *deleteDuplicates(struct list_head *head, int count)
{
if (!head)
return NULL;
struct list_head *temp = head;
head->prev->next = NULL;
// count == 0 at first function call
if(!count)
temp = temp->next;
if (temp->next && list_entry(temp, ListNode, list)->val
== list_entry(temp->next, ListNode, list)->val) {
/* Remove all duplicate numbers */
while (temp->next && list_entry(temp, ListNode, list)->val
== list_entry(head->next, ListNode, list)->val)
temp = temp->next;
return deleteDuplicates(temp->next, count++);
}
struct list_head *result;
result = deleteDuplicates(head->next, count++);
temp->next = result;
head->prev = result->prev;
result->prev->next = head;
result->prev = temp;
return temp;
}
```
#### circular doubly-linked list (迭代版本)
```c
#include <stddef.h>
struct ListNode {
int val;
struct list_head list;
};
void deleteDuplicates(struct list_head *head)
{
if (!head)
return NULL;
struct ListNode *node, *safe;
list_for_each_entry_safe (node, safe, head, list) {
// if &safe->list == head, safe->value will dereference a null pointer
if (&safe->list != head) {
if (node->value && safe->value) {
if (node->val == safe->value)) {
list_del(&node->list);
free(node->value);
free(node);
}
}
}
}
}
```
跟在 [lab0-c](https://hackmd.io/mr0mzS6qRl2kYhll8ONsxg?view#2022q1-Homework1-lab0) 實作的方式完全相同，參照其中的 `q_delete_dup` 函式。
用 `list_for_each_entry_safe` 來走訪 linked list ，在走訪的過程中比較 `node` 及 `safe` 中的資料大小，若相等則把 `node` 刪除，注意 `if (&safe->list != head)` 這個條件判斷，因為最後一次迴圈時 `safe` 已經回到 `head` 了，如果這時候呼叫 `list_entry(safe, ListNode, list)` 會導致程式出錯。
## 第三題 - [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/)
#### 結構
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
首先觀察 cache 的結構，可以發現在 `LRUCache` 的結構中有兩個 `list_head` 型別的變數， `dhead` 負責串接所有資料，當 cache 的容量到達上限時會刪除 `dhead` 串接的最後一個節點，因為每次 cache hit 的時候都會把資料所在的節點搬到第一個，刪掉最後一個節點符合 LRU 的原則。
另一個變數 `hheads` 是類似 hash table 的性質，要從 cache 查找資料時只要搜尋 `hheads[key]` 這條 linked list 就好，以此達到較佳的效能。
這樣的結構讓 cache 在存放或刪除資料時要同時對 `dhead` 跟 `hheads` 進行操作，`dhead` 的功能是使得 LRU 的機制知道哪一個節點需要刪除， `hheads` 是使得查找資料更為快速。
#### CacheCreate
```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;
}
```
用來分配 cache 所需的記憶體
#### CacheFree
```c
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
用來釋放 cache 的記憶體，這邊 MMM1 的功能應該是走訪 linked list ，而且要有可以對當前節點進行操作的性質，故答案應為`list_for_each_entry_safe` 。
#### CacheGet
```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 中的資料，所以 MMM2 的功能應為走訪 linked list ，而且只需要讀取資料就好，不用對節點進行操作，故答案應為 `list_for_each_entry` 。
注意到這邊會把輸入的 key 經過 hash function 轉換，再經過轉換的值去查找對應的 hash table `hheads[hash]` 。
若是查找成功的話，會把此節點搬到 `dhead` 的第一個位置， `list_move` 在 `list.h` 中的定義如下:
```c
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add(list, head);
}
```
#### CachePut
```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;
}
```
此函式的功用是將 cache miss 的資料存放入 cache 中。
一開始會先在 cache 中搜尋一次資料，確保真的 cache miss 了才進行存放資料的操作，因此 MMM3 的功能應為走訪 linked list ，答案為 `list_for_each_entry` 。
cache miss 後進行存放操作，首先檢查 cache 的容量足不足夠，若足夠則 `count++` 並插入節點，不夠則需要刪除資料，也就是 MMM4 這邊進行的操作，由於每次 cache hit 都會使用 `list_move` 將節點搬到最前面，故我們需要刪除的節點會是 linked list 的最後一個節點，因此 MMM4 的答案會是 `list_last_entry` 。
注意節點的加入跟刪除都要對 `dhead` 跟 `hheads` 進行操作!!
## 第四題 - [LeetCode 128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)
#### find
```c
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 ，可以注意到其中的 hash function `int hash = num < 0 ? -num % size : num % size` ，其會判斷 `num` 是否為負數，因為 hash key 為陣列的索引，故不能出現負數，但我們的目標是尋找連續的數字排列，其中出現負數是有可能的，因此在計算 hash key 的時候會直接取其絕對值。
#### longestConsecutive
```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);
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.創建 hash table `heads[]` 及分配其記憶體。
2.將所有的資料 `num[]` 存入 hash table ，存入前會先用 `find` 函式檢查資料是否已經存在其中，因此重複的資料不會被存入。
3.利用 `for` 迴圈從 `num[0]` 開始逐一計算連續資料的長度， `len` 為每次計算的長度， `length` 為目前的最長紀錄。
這道題目的問題 LLL 及 RRR 分別在兩個 `while` 迴圈的 condition 中，而 `while` 迴圈所做的事情是尋找相鄰資料，故 LLL 應為 --left ， RRR 應為 ++right 。
假設 num == 3 ，如果要計算連續資料的長度的話先找 2 有沒有在 hash table 中，若找到就再尋找 1 以此類推，一旦搜尋失敗就會回傳 NULL 並跳出迴圈，另一邊就是先找 4 找到了就找 5 以此類推，最後就能順利計算出連續資料的長度。
另外每次搜尋成功後都會將資料從 hash table 中移除，因此不會有重複搜尋的問題。
Sign in with Wallet
Connect another wallet