2022q1 Homework1 (quiz1)

contributed by < Korin777 >

Q1

延伸題目一

函式功能:

1. map_init
   用來建立 hash table map_t 的各個 hlist_head , ht 的數量為2的冪

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
4. map_add
   增加 ht[i] 的節點 , 節點會增加在 ht[i].first , 先透過 find_key 查詢 key 是否存在 , 不存在再增加節點

6. map_deinit
   釋放 hash table 所配置過的記憶體 , 每個 ht[i] 的各個節點依照由頭到尾的順序釋放 hash_key->data 及 hash_key , 最後再釋放整個 map_t

Q2

延伸題目一

• new_head 為移除重複節點後的 head
• prev_node 用來修正上個非重複節點的下個節點

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 結構

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 記憶體

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

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

• 透過 hheads[i] , 只能拿到屬於這個區塊的 LRUNode

• 透過 dhead 可以遍歷所有的 LRUNode , LRUNode 越後面表示越久沒用到

函式功能

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]

heads[i] 後面連結屬與此區塊的 seq_node

函式功能

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

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 實作 , 結構改為如下

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 __hlist_del 函式實作 map_del 用來移除 hash table 節點 hlist_node

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 來尋找最長連續整數長度

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;
}

題目連結