contributed by < freshLiver
>
linux2022
/**
* @brief 建立並初始化一個有 2^bits 個欄位的雜湊表
*
* @param bits
* @return map_t*
*/
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;
}
/**
* @brief 從雜湊表中尋找並回傳一節點 kn,且 kn.key == @key
*
* 將 @key 經過雜湊函數計算後得到所屬欄位,
* 接著依序走訪該欄位並檢查目標資料 @key 是否存在於該欄位中,
* 若有找到則回傳包含該資料的節點,若不存在則回傳 NULL。
*
* @param map 目標雜湊表
* @param key 目標節點的 key
* @return struct hash_key*
*/
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;
}
/**
* @brief 從雜湊表中提取 key 與 @key 相符之節點 kn 的資料 data
*
* @param map 目標雜湊表
* @param key 數列 nums 中的某數 k
* @return void*
*/
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
/**
* @brief 建立一節點 kn 來保存 @key 以及 @data
*
* @param map 目標雜湊表
* @param key 數列 nums 中的某數 k
* @param data k 在數列 nums 中的 index
*/
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return; // 所有節點的 key 不應重複
// 分配空間以及將資料複製到該節點
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
/**
* @brief 將新增的節點插入到對應欄位的首位
*
* 首先透過雜湊函式取得目標欄位的地址 h
* 以及該欄位的首位節點 first
* 最後再為 h->next, n, first 重新建立連結
*
* - 新的節點 n 需要設定 pprev 以及 next
* - n->next 指向原本的首位節點 first
* - n->pprev 則指向欄位 h 指向首位節點的結構體地址 &h->first
*
* - 欄位 h 應指向新的首位節點 n
* - 原首位節點 first 的 pprev 改指向新節點 n 的 next 的地址 &n->next
*
*/
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
我自己的發現是 其實你仔細看 n->next = first
first->pprev = &n->next 等同於 first -> pprev = & first
n->pprev = &n
pprev 在這邊的物理意義等於指向自己位址的指標
所以下面的 if (!n->pprev) goto bail;
意思是 如果指向自己的指標為 null (即自己為空)
那麼就跳至最後面處理上述可以在 leetcode代換程式碼發現結果不變 , 但我也不能百分百肯定是不是這樣,因為覺得這樣 pprev 變得很奇怪?
by修課同學 Haoyu
如果我的認知沒錯的話,indirect pointer 應該是用來儲存某個「指標的地址」,而這邊的 **prev
就應該是用來儲存「前一個節點的 next
指標的地址」。
但這邊的 first
是一個指向下個節點的指標,即使在 n->next = first
後,也只是這兩個指標指向相同的地址(儲存的值都是下個節點的地址),若是對 first
取址的話應該會得到 first
這個區域變數的地址,所以 &first == &n->next
應該不會成立。
若在這個認知上去思考 if (!n->pprev)
成立的情境的話,應該是代表前一個節點的 next
的地址為 NULL
,或是 pprev
被手動指向 NULL
,但我想不通正常操作下什麼時候會發生這個情況。
而我在 LeetCode 測試時把那行 if (...) goto ...
移除後結果也是 Accepted。
我的理解是
**pprev
變數名稱看起來的確是應該用來儲存「前一個節點的next
指標的地址」
first
指向的是串列的首個節點*first = h->first
n->next = first
就是把 原本串列的首個節點接在 n 這個節點的後面
if (first)
表示串列的首個節點是否存在 , 存在的話
將first->pprev
指向 (指向n->next
的位址)
而上面才剛修改過n-> next
為first
所以first -> pprev
會指向 指向first
的位址
以上為根據程式碼判斷的結論
看起來是我們對於first
的想法不太一樣?
如果我對程式理解有誤 麻煩在幫我指出哪裡有錯誤
首先,我看不太懂你的敘述內容且 **
造成 Markdown 格式問題,所以我對你的內文做了些調整。
再來是我實際寫了程式測試了在進行 new->next = first
後 &first == &n->next
是否會成立:
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define print_ptr(p) \
({ \
printf("%d:Pointer %s\n", __LINE__, #p); \
printf("\tAddress = %p\n", &p); \
printf("\t Value = %p\n\n", p); \
})
#define print_ind_ptr(p) \
({ \
printf("%d:Indirect Pointer %s\n", __LINE__, #p); \
printf("\tAddress = %p\n", &p); \
printf("\t Value = %p\n", p); \
printf("\t Target = %p\n\n", *p); \
})
typedef struct NODE {
struct NODE **pprev, *next;
} hlist_node;
typedef struct HEAD {
hlist_node *first;
} hlist_head;
int main(int argc, char const *argv[])
{
hlist_head *head = &(hlist_head){
.first =
&(hlist_node){
.pprev = &head->first,
.next = NULL,
},
};
hlist_node *first = head->first;
hlist_node *new = &(hlist_node){.pprev = NULL, .next = NULL};
print_ptr(head);
print_ptr(head->first);
print_ptr(first);
print_ptr(new);
new->next = first;
print_ptr(first);
print_ptr(new->next);
if (first) {
first->pprev = &new->next;
print_ind_ptr(first->pprev);
}
head->first = new;
new->pprev = &head->first;
// end
return 0;
}
測試結果:
$ gcc indirect.c && ./a.out
41:Pointer head
Address = 0x7ffd4e7ac880
Value = 0x7ffd4e7ac888
42:Pointer head->first
Address = 0x7ffd4e7ac888
Value = 0x7ffd4e7ac8a0
43:Pointer first
Address = 0x7ffd4e7ac890
Value = 0x7ffd4e7ac8a0
44:Pointer new
Address = 0x7ffd4e7ac898
Value = 0x7ffd4e7ac8b0
47:Pointer first
Address = 0x7ffd4e7ac890
Value = 0x7ffd4e7ac8a0
48:Pointer new->next
Address = 0x7ffd4e7ac8b8
Value = 0x7ffd4e7ac8a0
51:Indirect Pointer first->pprev
Address = 0x7ffd4e7ac8a0
Value = 0x7ffd4e7ac8b8
Target = 0x7ffd4e7ac8a0
可以看到在 46 行結束後,指標 first
指向的地址(變數 first
儲存的值)與 new->next
指向的地址(變數 new->next
的值)相同,但 first
的地址(&first
)與 new->next
的地址(&new->next
)明顯不同。
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);
// n 保存目前節點的地址,p 則移至下一個節點
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
// 將當前節點 n 移出當前欄位
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
// 釋放節點 n 的資料以及節點本身佔用的資源
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
TODO : if (!n->pprev) goto bail;
用途
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; // 無法分配空間給答案
/**
* @brief 利用雜湊表紀錄已看過得數值以及它們的 index
*
* 由於目標是要找到 num 與 k 使得 num + k == target
* 因此檢查到數列 nums 中的數值 num 時
* 就檢查雜湊表中是否有 key 為 k 的數值存在
*
* Case 1. k 不存在
*
* 將 num 作為 key、index 作為 data 新增至雜湊表
* 若之後遇到另一數 k 時就會因 num 存在而找到解
*
* Case 2. k 存在
*
* 代表 k 有在數列 nums 中
* 因此 k 的節點的資料 *p(代表 k 所在的 index)取出
* 接著再將 *p 以及當前 index i 作為答案回傳
*
*/
for (int i = 0; i < numsSize; i++) {
// 若雜湊表中有 key 為 k 的節點存在,則 p 不為 NULL
int *p = map_get(map, target - nums[i]);
// k 在雜湊表中
if (p) {
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
// k 不在雜湊表中,將 num (nums[i]) 以及其 index i 加入雜湊表
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
bail:
map_deinit(map);
return ret;
}
hlist_head
以及 hlist_node
在 include/linux/types.h 中有定義 hlist_head 以及 hlist_node 兩個結構體:
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
與 Linux Kernel Linked List API 相比:
list_head
的設計相似,是為了能夠方便擴充。hlist_head
作為欄位,而每個欄位都透過 first
指向各自的鏈結串列,是透過 Chaining 的方式來處理 Collision。pprev
並不是單純指向前一個節點。(使用 indirect pointer 的設計可以參考 第二週的討論)hlist_head
數量) 在宣告時就決定了(宣告成陣列的形式)。hlist_head
以及 hlist_node
相關基本操作的函式以及巨集則是定義在 include/linux/hashtable.h 以及 include/linux/list.h 中。
DECLARE_HASHTABLE(name, bits)
hash_init(table)
hash_add_head(head, node, key)
hash_del(node)
pprev
以及 next
指向 NULL
)這個 node
,則需要使用 hlist_del_init
。hlist_unhashed(node)
node
是否已被 unhashed。hlist_move_list(new_head, old_head)
old_head
的 Chaining List 取代 new_head
的 Chaining List,並移除 old_head
的 first
。hlist_for_each
系列巨集
list_for_each
系列相似,用來走訪 Chaining List,也有 entry 以及 safe 版。hlist_for_each_entry_from
head->first
開始。hlist_for_each_entry_continue
hlist_for_each_entry_from
相似,但是從指定節點的下一個節點開始繼續走訪。TODO
GOLDEN_RATIO_PRIME
這題的目標是將一個已排序過的 Singly-linked List 中重複的節點移除,需要注意的部份是:
NULL
#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;
}
在這個程式碼中,可以發現被 if
分成了三個部份,且這三個部份的的最後皆以 return
結束,分別代表了以下三種情況:
head
為 NULL
時COND1
成立時第一個部份是為了處理原串列為 NULL
以及遞迴呼叫到串列尾端時的遞迴終止條件。
第二個部份則是為了處理 head
與 head->next
兩節點資料相同的情況,所以 COND1
應該是 head->val == head->next->val
,但這邊有個陷阱是 head->next->val
若是在 head->next == NULL
時會出問題,所以必須先檢查 head->next != NULL
,因此正確的 COND1
應為:
head->next && head->val == head->next->val
而進入第二部份的 if
之後則是透過 while
迴圈跳過所有連續重複資料的節點,所以當目前指向的節點 head
的資料與其下一個節點 head->next
的資料相同時就要跳過目前節點,因此 COND2
應該是 head->val == head->next->val
。同樣的,這邊也有個陷阱是當串列走到尾端時, head->next
會是 NULL
,因此這邊也必須先檢查 head->next != NULL
,所以正確的 COND2
應和 COND1
相同,皆為:
head->next && head->val == head->next->val
而在 while
迴圈結束後(即 head->next == NULL || head->val != head->next->val
),就需要再次透過遞迴呼叫 deleteDuplicates
來找到剩餘串列中部重複的節點,但由於 head
也是重複的節點,所以傳入 deleteDuplicates
的參數應為 head->next
才對。
而最後的第三部份則因為 COND1
確保了 head
的資料不與其他節點重複,所以只需要透過 deleteDuplicates
找出 head->next
要接到哪個節點,最後再回傳 head
即可。
struct ListNode* deleteDuplicates(struct ListNode* head){
if (!head)
return NULL;
bool found = false;
for (struct ListNode **ptr = &head; *ptr;) {
// same val
if ((*ptr)->next && (*ptr)->val == (*ptr)->next->val) {
*ptr = (*ptr)->next;
found = true;
}
else {
// don't forget to rm last repeated node
if (found)
*ptr = (*ptr)->next;
else
ptr = &(*ptr)->next;
found = false;
}
}
return head;
}
這個迭代的實作參考了你所不知道的 C 語言: linked list 和非連續記憶體中提到的有品味的移除節點的操作,使用了 ListNode
的指標的指標來避免額外判斷當前節點是否為 head
。
bool
變數以簡化程式碼struct ListNode* deleteDuplicates(struct ListNode* head){
if (!head)
return NULL;
bool prev = false, found = false;
for (struct ListNode **ptr = &head; *ptr; prev = found) {
found = (*ptr)->next && (*ptr)->val == (*ptr)->next->val;
if (found || prev)
*ptr = (*ptr)->next;
else
ptr = &(*ptr)->next;
}
return head;
}
透過分別使用 prev
以及 found
來紀錄上一個節點以及目前節點的比較結果,這能讓原本程式碼中第 16 行的 if
與第 10 行的 if
合併。
與 lab0-c 中要實作的 function q_delete_dup
相似,但可以不用刪除節點資料,且儲存的資料型態為 int
而不是 char *
。
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
LIST_HEAD(duplist);
bool prev = false;
element_t *ptr = list_entry(head->next, element_t, list), *next = ptr;
for (bool same; next->list.next != head; ptr = next) {
next = list_entry(ptr->list.next, element_t, list);
same = ptr->value == next->value;
if (same || prev)
list_move(&ptr->list, &duplist);
prev = same;
}
// don't forget last node
if (prev)
list_move(&ptr->list, &duplist);
return true;
}
typedef struct ListNode Node;
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
// build doubly-linked list
struct list_head doubly;
INIT_LIST_HEAD(&doubly);
for (Node *ptr = head; ptr; ptr = ptr->next) {
element_t *e = malloc(sizeof(element_t));
e->value = ptr->val;
e->list.next = NULL;
list_add_tail(&e->list, &doubly);
}
q_delete_dup(&doubly);
// back to singly
Node *new = NULL, **pnew = &new;
element_t *ptr;
list_for_each_entry (ptr, &doubly, list) {
Node *n = malloc(sizeof(Node));
n->val = ptr->value;
n->next = NULL;
*pnew = n;
pnew = &(*pnew)->next;
}
return new;
}
如果第 23 行的 *new
不初始化成 NULL
的話,可能在 doubly
的元素皆被移除時(例如輸入串列為 [1,1]
時)跳出以下錯誤:
Line 70: Char 15: runtime error: member access within misaligned address 0x000041b58ab3 for type 'struct ListNode', which requires 8 byte alignment [ListNode.c]
0x000041b58ab3: note: pointer points here
<memory cannot be printed>
typedef struct ListNode Node;
#define assign_and_cmp(ptr, next, p_ptr_entry, p_next_entry) \
({ \
p_ptr_entry = list_entry(ptr, element_t, list); \
p_next_entry = list_entry(next, element_t, list); \
p_ptr_entry->value == p_next_entry->value; \
})
struct list_head *q_delete_dup(struct list_head *head)
{
if (!head)
return NULL;
element_t *ptr, *next;
if (head->next && assign_and_cmp(head, head->next, ptr, next)) {
while (head->next && assign_and_cmp(head, head->next, ptr, next))
head = head->next;
return q_delete_dup(head->next);
}
head->next = q_delete_dup(head->next);
if (head->next)
head->next->prev = head;
return head;
}
把 list_head
當作 Singly-linked List 操作,並透過定義巨集讓函式能直接沿用 Singly-linked List 的遞迴函式的結構,只需要額外宣告變數來存取 element_t
的資訊,以及要額外處理 prev
連結。
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
// build doubly-linked list
struct list_head doubly;
INIT_LIST_HEAD(&doubly);
for (Node *ptr = head; ptr; ptr = ptr->next) {
element_t *e = malloc(sizeof(element_t));
e->value = ptr->val;
e->list.next = NULL;
list_add_tail(&e->list, &doubly);
}
// break circular
doubly.prev->next = NULL;
// head do not contain data, start from first node
doubly.next = q_delete_dup(doubly.next);
if (doubly.next)
doubly.next->prev = &doubly;
// make circular
struct list_head *ptr;
for (ptr = &doubly; ptr->next; ptr = ptr->next)
;
ptr->next = &doubly;
doubly.prev = ptr;
// back to singly
Node *new = NULL, **pnew = &new;
list_for_each (ptr, &doubly) {
element_t *entry = list_entry(ptr, element_t, list);
Node *n = malloc(sizeof(Node));
n->val = entry->value;
n->next = NULL;
*pnew = n;
pnew = &(*pnew)->next;
}
return new;
}
大致上與迭代版本的相同,但差在由於這邊的遞迴版是沿用單向的遞迴的函式,因此在檢查條件時也是沿用 !head
以及 head->next
,所以這邊要先把最後一個節點的 next
指向 NULL
,讓串列變成非環狀串列,並以首位節點作為開頭進行 q_delete_dup
,然後在結束時還需要讓串列變回環狀。
由於 deleteDuplicates
是有被規定的,因此不論是遞迴還是迭代版都可以用相同函式測試 deleteDuplicates
。
int main(int argc, char const *argv[])
{
Node *head, **phead = &head;
int vals[] = {1, 1};
for (int i = 0; i < (sizeof(vals) / sizeof(vals[0])); ++i) {
Node *n = malloc(sizeof(Node));
n->val = vals[i];
n->next = NULL;
*phead = n;
phead = &(*phead)->next;
}
deleteDuplicates(head);
return 0;
}
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *cache;
// 利用 GNU C Extension 建立可變大小的 LRUCache 結構體物件
// REF : https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
cache = malloc(sizeof(LRUCache) + capacity * sizeof(struct list_head));
cache->capacity = capacity;
cache->count = 0;
// 初始化 dhead 以及雜湊表
INIT_LIST_HEAD(&cache->dhead);
for (int i = 0; i < capacity; ++i)
INIT_LIST_HEAD(&cache->hheads[i]);
return cache;
}
/**
* @brief 新增一資料 (key,value) 到快取中
*
* TRICK :
* 新增的資料並非放到原 LRU 節點所在的欄位
* 實際上與雜湊表概念相同
* 是將資料放在第 HASH(key) 個欄位
* 而實際的 Cache 存取紀錄則是由 LRUCache 的 dhead 管理
* 透過使用雜湊表 hhead 搭配「額外的」環狀雙向鏈結串列 dhead
*
* - 新增資料:
* - 加入(資料不存在,Cache 未滿):
* 1. 計算 HASH(key) 並將資料加入雜湊表
* 2. 將該節點加入到 dhead 串列
*
* - 取代(資料不存在,Cache 已滿):
* 1. 將 LRU 從 hhead 中移除
* 2. 將 LRU 從 dhead 中移除
* 3. 計算 HASH(key) 並將新資料加到雜湊表
* 4. 將新資料的節點加到 dhead 串列
*
* - 更新(資料存在):
* 1. 從雜湊表中尋找該資料的節點
* 2. 將該節點提昇至 dhead 首位(移除再加入)
*
* - 取得資料:
* 1. 從雜湊表中尋找該資料的節點
* 2. 若有找到該資料則將該節點提昇至 dhead 首位
* 3. 回傳節點
*
* @param cache LRUCache 物件的地址
* @param key 欲新增資料的 key
* @param value 欲新增資料的 value
*/
void lRUCachePut(LRUCache *cache, int key, int value)
{
int hash = HASH(key, cache);
LRUNode *node, *next;
// MMM3, 只是 move 不需要使用到 safe
list_for_each_entry (node, &cache->hheads[hash], hlink) {
if (node->key == key) {
// 更新該 key 的 value
node->value = value;
// 提昇至 dhead 首位
list_move(&node->dlink, &cache->dhead);
return;
}
}
// 未滿,直接新增節點
if (cache->count < cache->capacity) {
node = malloc(sizeof(LRUNode));
++cache->count;
}
// 已滿,移除 dhead 中的 LRU
else {
// MMM4
node = list_last_entry(&cache->dhead, LRUNode, dlink);
list_del(&node->dlink);
list_del(&node->hlink);
}
// 分別將資料加入到雜湊表以及 dhead
node->key = key;
node->value = value;
list_add(&node->dlink, &cache->dhead);
list_add(&node->hlink, &cache->hheads[hash]);
}
MMM4 的部份可能是答案錯了,能夠賦值的巨集應該是 list_entry
, list_first_entry
或是 list_last_entry
,而這邊因為是要獲取 LRU 所以要找的節點應該是 dhead->prev
,所以答案應為 list_last_entry
才正確。
/**
* @brief 從 LRU Cache 取得資料
*
* 透過 HASH(key) 計算出雜湊表的欄位索引
* 接著到該欄位尋找目標的 key
* 而不是走訪 dhead 中所有節點尋找 key
*
* @param cache
* @param key
* @return int
*/
int lRUCacheGet(LRUCache *cache, int key)
{
LRUNode *node;
// MMM2
list_for_each_entry (node, &cache->hheads[HASH(key, cache)], hlink)
if (node->key == key) {
list_move(&node->dlink, &cache->dhead);
return node->value;
}
return -1;
}
/**
* @brief 清除 LRU Cache
*
* 雖然快取紀錄是由 dhead 管理
* 但 LRUNode 同時包含 dlink 以及 hlink
* 分別用來指向 dhead 及 hhead 的前後節點
* 因此實際上 dhead 中的節點與 hhead 中的節點相同
* 只須刪除一邊的節點即可
*
* @param cache
*/
void lRUCacheFree(LRUCache *cache)
{
LRUNode *node, *next;
// MMM 1
list_for_each_entry_safe (node, next, &cache->dhead, dlink) {
list_del(&node->dlink);
free(node);
}
free(cache);
}
static inline void GET_AND_SHOW(LRUCache *cache, int key)
{
int value = lRUCacheGet(cache, key);
printf("GET (%d,%d)\n", key, value);
}
int main(int argc, char const *argv[])
{
LRUCache *cache = lRUCacheCreate(2);
lRUCachePut(cache, 1, 1);
lRUCachePut(cache, 1, 1);
GET_AND_SHOW(cache, 1);
lRUCachePut(cache, 3, 3);
GET_AND_SHOW(cache, 2);
lRUCachePut(cache, 4, 4);
GET_AND_SHOW(cache, 1);
GET_AND_SHOW(cache, 3);
GET_AND_SHOW(cache, 4);
lRUCacheFree(cache);
return 0;
}
TODO
/**
* @brief 找出雜湊表中包含某個數值的節點
*
* 會先對 @num 取絕對值並計算出該數所屬的欄位
* 接著在走訪該欄位、檢查是否包含此數
*
* @param num 目標數值
* @param size 雜湊表大小(有幾個欄位)
* @param heads 雜湊表
* @return struct seq_node*
*/
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)
{
// 建立並初始化雜湊表
struct list_head *heads = malloc(n_size * sizeof(*heads));
for (int i = 0; i < n_size; i++)
INIT_LIST_HEAD(&heads[i]);
// 將每個數字放入雜湊表
struct seq_node *node;
for (int i = 0, hash; i < n_size; i++) {
// 跳過重複數字
if (!find(nums[i], n_size, heads)) {
// 使用 modulo 作為雜湊函數,將數字取絕對值計算後放入雜湊表
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]);
}
}
int global = 0;
for (int i = 0, num; i < n_size; i++) {
/**
* @brief 尋找最長的連續數列 (global 代表目前找到最長的數列長度)
*
* Step 1. 檢查當前數字是否在雜湊表中
*
* Y : 跳至 Step 2
* N : 跳至 Step 4
*
* Step 2. 開始尋找包含此數(num)的連續數列 (local 代表此連續數列長度)
*
* 2-1 : 將此數移出雜湊表並將 local + 1
*
* 2-2 : 從 num 開始向下尋找最多有幾個相鄰整數 (k>0)
*
* 2-2-1 : 尋找雜湊表中是否包含 num-k
* Y : ++local, ++k, 將 num-k 從雜湊表中移除
* N : 結束此迴圈
*
* 2-3 : 類似 2-2,但是從 num+1 往上找
*
* Step 3. 如果 local 較大的話就更新 global
*
* Step 4. 如果尚未檢查到最後一個數字的話就回到 Step 1
*
* TRICK :
* 由於雜湊表不包含重複數字且在 Step 2 找連續數字時會將找到的數字移除
* 所以即使 nums 中包含連續或重複數字也只有第一次遇到時會進入第二個迴圈
* 之後遇到該群連續數列時就只需要檢查雜湊表是否包含該數而已
* 因此運作起來會像是在計算每群連續數列的長度
*/
int local = 0;
if (node = find(nums[i], n_size, heads)) {
local++;
num = node->num;
list_del(&node->link);
// 從 num-1 向下,因 num 已取出且每次找到應將 left 遞減,故 --left
for (int left = num; (node = find(--left, n_size, heads));) {
local++;
list_del(&node->link);
}
// 從 num+1 向上,因 num 已取出且每次找到應將 right 遞增,故 ++right
for (int right = num; (node = find(++right, n_size, heads));) {
local++;
list_del(&node->link);
}
global = local > global ? local : global;
}
}
return global;
}
TODO
while(node)
可改用 if
第 56 列的 if
原本是 while(node)
,但是在第 68 列的迴圈結束條件為 node
被賦予 NULL
時,因此實際上 while
只會執行一次,可用 if
替代。
while
迴圈可改用 for
迴圈使程式碼更精簡left
與 right
只會分別在各自的 while
迴圈中使用到,因此可利用 for
迴圈進行宣告,使得程式碼更加簡短並縮短 left
以及 right
的生命週期。
len
以及 length
兩變數名稱有相近含意原先的 len
是用來表示 Step 2
中找到的連續數列的長度,而 length
則是代表目前找到的最長連續數列的長度,兩個變數名稱相近可能會造成混淆,因此將 length
以及 len
分別以 global
以及 local
進行替換。
TODO