2022q1 Homework1 (quiz1)

contributed by < Destiny0504 >

題目連結

測驗 1

• AAA = n->next = first;
• BBB = n->pprev = &h->first;

// Leetcode problem 1 Two sum
#include <stddef.h>
#include <stdlib.h>

宣告用來建立 list 需要用到的 structure

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;

決定 hash map 的大小並初始化

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

• hash table 示意圖

宣告 hash table node 的 structure

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

container_of

此巨集能透過指向 structure 中的 member 的 pointer 回推整個 sturcture 的開頭記憶體位置

• 回傳值為指向 structure 記憶體位置的 pointer

#define container_of(ptr, type, member)               \
    ({                                                \
        void *__mptr = (void *) (ptr);                \
        ((type *) (__mptr - offsetof(type, member))); \
    })

Hash function

此函式能將傳入的 val 計算完 hash 後的值並回傳

• 選用一個夠大的數字（ 0x61C88647 ）來 hash ，這麼做可以確保 hash 過後的值並不會太小，導致我們在取前幾個 bits 所得到的值太過接近，進而失去 hash 的效果。
• 變數 bits 可以幫助我們決定要取前面多少個 bit 當作 hash 完的結果。
  • e.g. bits = 10 ，我們得到的 hash 值的範圍就會在 0 ~ 1023 之間

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

find key

確認 key 所代表的值是否在 map 之中

• 如果在 map 中函式會回傳指向 key 的 pointer ，否則回傳 NULL

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

• 透過移動 p 所指向的位置來確認 list 是否含有我們要的值。

map get

與 find key 的功能相同，差別只在於回傳的資料型別為 void pointer

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

map add

將新的值加入 map 中

• 先檢查要加入的值是否已在 map 中，如果已經加入過的話，就不做任何更動。
• 如果確認 key 不在 map 之中，則在 key 應該被加入的 list 中新增一個值為 key 的 node

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 */
    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    /* BBB */
    n->pprev = &h->first;
}

map deinit

將分配給整個 map 的記憶體釋放，相當於把整個 map 刪除。

• 遍歷整個 map 來將每個 allocated 的 node 的 memory 都釋放。

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

解決 TwoSum 問題

Two Sum 問題連結

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

Reference

• GOLDEN_RATIO_32

測驗 2

• COND1 = head->next != NULL && head->val == head->next->val
• COND2 = head != NULL && head->next != NULL && head->val == head->next->val

Singly-linked list 迭代版本

因為原本的題目就是 singly-linked list ，所以不額外實作 listnode

• 如果傳入的 list 為空或是只有一個 node 就直接回傳 head

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    struct ListNode *prev = NULL, *tmp = NULL;
    int hold = 0, cur = 0;
    if (head == NULL || head->next == NULL)
        return head;

• 將開頭所有重複的點全部移除，確保現在的 head 是需要被保留的點。這一步做完，如果整個 list 只剩下一個 node 以下，就直接回傳答案。

    while (hold != 1 && head != NULL) {
        hold = 1;
        while (head->next != NULL && head->val == head->next->val) {
            head->next = head->next->next;
            hold = 0;
        }
        if (!hold)
            head = head->next;
    }
    
    if (head == NULL || head->next == NULL)
        return head;

• 將剩餘的 duplicate node 全部移除

    prev = head;
    tmp = head->next;
    while (tmp != NULL) {
        hold = 1;
        while (tmp->next != NULL && tmp->val == tmp->next->val) {
            tmp->next = tmp->next->next;
            hold = 0;
        }
        if (hold) {
            prev->next = tmp;
            prev = prev->next;
        }
        tmp = tmp->next;
    }
    prev->next = tmp;
    return head;
}

Doubly-linked list 迭代版本

Listnode 節點

struct listnode {
    int val;
    struct listnode *next;
    struct listnode *prev;
};

List 所需要的函式

// 初始化 node
void initnode(struct listnode *head)
{
    head->next = head;
    head->prev = head;
}
// 在 doubly-linked list 尾端加入新的 node
void add_tail(struct listnode *head, struct listnode *node)
{
    head->prev->next = node;
    node->prev = head->prev;
    head->prev = node;
    node->next = head;
}
// allocate 一塊新的 memory 給新的 node 並賦予給定的值
struct listnode *createnode(int data)
{
    struct listnode *tmp = malloc(sizeof(struct listnode));
    initnode(tmp);
    tmp->val = data;
    return tmp;
}
// 刪除 doubly-linked list 中的 node
void del_node(struct listnode *node)
{
    struct listnode *next = node->next;
    struct listnode *prev = node->prev;
    prev->next = next;
    next->prev = prev;
}

從 list 中移除含有重複 val 的 node

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode *tmp = head;
    struct listnode *l_head = malloc(sizeof(struct listnode)), *cur = NULL;
    int l_size = 0, i = 0, flag = 0;
    initnode(l_head);

• 因為原本的題目是單向的 linked list ，所以我們要將原本的 linked list 中的所有的值全部加入自己實作的雙向 linked list。

    for (; tmp != NULL; tmp = tmp->next) {
        struct listnode *tmpnode = createnode(tmp->val);
        add_tail(l_head, tmpnode);
        l_size++;
    }

• 將開頭所有重複的點全部移除。這一步做完，如果整個 list 如果沒有任何 node ，就直接回傳 NULL 。

    for (cur = l_head->next; cur != l_head; cur = cur->next) {
        while (cur->next != l_head && cur->val == cur->next->val) {
            del_node(cur->next);
            l_size--;
            flag = 1;
        }
        if (flag) {
            flag = 0;
            del_node(cur);
            l_size--;
        }
    }
    if (l_head->next == l_head)
        return NULL;

• 將 head 指向第一個不重複的 node

    for (cur = l_head->next; head->val != cur->val; ){
        head = head->next;
    }

• 利用雙向的 linked list 幫助判斷原本的 node 需不需要被刪除
  • 因為雙向的 linked list 可以直接看前一個 node 的值，所以可以直接判斷現在的 node 需不需要被刪除。

    for (tmp = head, cur = l_head->next; tmp->next != NULL;) {
        if (tmp->next->val != cur->next->val) {
            tmp->next = tmp->next->next;
        }
        else {
            tmp = tmp->next;
            cur = cur->next;
        }
    }
    return head;
}

測驗 3

宣告用來建立 list 需要用到的 structure

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

typedef struct {
    int capacity, count;
    struct list_head dhead, hheads[];
} LRUCache;

typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

初始化 cache

分配一塊指定大小 (capacity）的 memory ，用來模擬 cache 的運作。obj 中的每一個 index 皆指向一個獨立的 node。每一個 node 皆為一個用來儲存 data 的 cache block。

• 因為 cache 的大小有限，所以儲存資料的 key 會先經過 hash function 在存入對應的 block 。當我們需要拿取資料的時候，也是經過同樣的方式查看對應的 block 是否已有我們要找的資料。

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

用 list.h 中實作的 list_for_each_entry_safe(entry, safe, head, member) 來一一釋放分配到的記憶體，達成清空 cache 的效果。

void lRUCacheFree(LRUCache *obj)
{
    LRUNode *lru, *n;
    list_for_each_entry_safe (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj);
}

從 cache 中拿出指定的 object

計算出 key % obj->capacity 後，到對應的 block 檢查我們需要的資料是否在 cache 中。如果有則回傳 block 中的值，

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

將指定的 object 放入 cache

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry (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 = list_last_entry(&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;
}

測驗 4

加上可以讀取測試資料的 main funtion 之後的正確答案

定義會用到的 structure 以及 include header file

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

struct seq_node {
    int num;
    struct list_head link;
};

在同樣的 hash 值的 list 中找尋是否含有要指定的值

用 num % size 求出的 hash 值，再透過函式傳入的 head，可以拿到整個可能包含 num 的 list ，接著從 list 中一一檢查是否有要查找的值（ num )。

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

解決 longest consecutive sequece 的 function

• 第一個 for 迴圈
  • 這個 for 迴圈是為了初始化整個 hash table
• 第二個 for 迴圈
  • 這個迴圈能夠將傳入此函式的 nums 所含有的數字一一加入 hash table
• 第三個 for 迴圈
  • 先指定一個值 num 再去整個 hash table 尋找是否有跟 num 相連的數字，最後得出 longest consecutive sequece 的長度。

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(--left, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(++right, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

讀取 test data

int main()
{
    int ans = 0, *nums = NULL, counter = 0;
    // 100 為可以自行調整的參數，此處的 100 代表 100 bytes
    nums = malloc(sizeof(int) * 100);
    while (scanf("%d", &nums[counter]) != EOF) {
        counter++;
    }
    ans = longestConsecutive(nums, sizeof(int) * counter);
    printf("%d\n", ans);
    free(nums);
}

Reference

• 測驗三 obj 的 malloc 問題
  • structure pointer 在宣告結束的時候就擁有 4 bytes 的空間來儲存記憶體位置了，所以 sizeof(obj) 不會是一個不確定的數字。
  • 參考 ：Scopes of identifier