Try   HackMD

2022q1 Homework1 (quiz1)

contributed by <arthurchang09>

Q1

解題

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;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    BBB;
}
  1. AAA 是 n->next = first 。 由下方的 first->pprev = &n->next 以及 h->first = n 可判斷是要將新的節點插入開頭，因此 AAA 的 next 指向原本第一個節點。
  2. BBB 是 n->pprev = &h->first 。由 1. 可知次將新節點插入開頭，由於 hlist 是雙向的，要將節點之 pprev 指回前一個節點，在此便是指回開頭。又 pprev 是指標的指標，因此是指向 h->first 之位址，

解釋上述程式碼運作原理

  • map_init()
    初始化整個 hash table之 map_t 及各個 hlist_head ，並將每個 hlist_head 初始化為 null 。






G



m

map

ht[0].first

ht[1].first

ht[2].first

...



null

null



m:e->null





m:e->null





m:e->null

  • find_key()
    查詢某個數值是否在 hash table 中並回傳位址。透過指定的 hash function 找到 map 中對應的 hlist_head ，接著走訪整個 linked list ，使用 container_of 巨集，找到整個 hash_key 的位址並取出值比較，若相符則回傳此位址。若無則回傳 null 。

  • map_get()
    呼叫 find_key 的 function 。透過 find_key 找到欲找的結點並回傳其值之指標，或者回傳 null 。

  • map_add()
    新增 hash_key 節點。先呼叫 find_key() 查詢節點是否存在。若否，則在其對應的 hlist_head 的開頭新增節點。

  • map_deinit()
    透過逐一走訪 map 中所有的 hlist_head 釋放整個 hash table，使用 container_of 找到對應 hash_key 的位址後釋放記憶體空間。最後釋放 map 的空間。

Q2

針對 LeetCode 82. 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 (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

此題之目標是要刪除值重複的節點， COND1 答案必然包含檢查當前節點的值是否和下一個節點的值相等，即 head->value == head->next->value 。然而，下一個節點可能為 NULL ，代表 linked list 已經走到結尾，直接 head->next->value 可能導致錯誤，因此要先判斷 head->next 是否為 NULL 。因此 COND1 為 head->next && head->value == head->next-value 。

while 迴圈的目的是要跳過所有值重複的節點，因此其條件和 COND1 相同，為 head->next && head->value == head->next-value 。

嘗試避免遞迴，寫出同樣作用的程式碼

struct ListNode {
  int val;
  struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head) {
  if (!head)
    return NULL;
  struct ListNode *node = NULL, *prev = NULL;
  int same_val = 0;
  for (node = head; node;) {
    if (node->next && node->val == node->next->val) {
      if (!prev) {
        head = node->next;
        same_val = 1;
        prev = NULL;
      } else {
        prev->next = node->next;
        same_val = 1;
        prev = node;
      }
    } else if (same_val) {
      same_val = 0;
      if (!prev) {
        head = node->next;
        prev = NULL;
      } else {
        prev->next = node->next;
        prev = node;
      }
    } else {
      prev = node;
    }

    node = node->next;
  }
  return head;
}

Q3

針對 LeetCode 146. LRU Cache，以下是 Least Recently Used (LRU) 可能的合法 C 程式實作:

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

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;
}
    
void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}   

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

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

MMM1 可看出來是包含四個參數，其目的是走訪整個 linked list ，並釋放每個 node 的記憶體空間，因此需要 list_entry 這個巨集。又因為要醜訪並刪除、釋放記憶體空間，需要額外之指標，因此 MMM1 為 list_for_each_entry_safe 。

MMM2 和 MMM3 皆是走放整個 linked list 且無刪除動作，另外要透過 hlink 找到所在節點的 LRUNode 位址，需要使用 list_entry ，因此 MMM2 、 MMM3 皆為 list_for_each_entry 。

Q4

針對 LeetCode 128. Longest Consecutive Sequence，以下是可能的合法 C 程式實作:

































































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

struct seq_node {
    int num;
    struct list_head link;
};                                                                                                                                                            
            
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)
{
    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;
}

在第三個 for 迴圈中， left 和 right 分別以 num 為中心，向左或向右搜尋 hash table 中搜尋連續的數字並移除掉該節點，並更新最長長度，直到找不到連續的數值之節點，再移到下一個陣列中元素進行搜尋。注意到在 46 行中已經先刪除了一個節點 num ，且接下來兩個 while 迴圈會逐步刪除數字是連續之節點，即 num - 1 、 num - 2 … 和 num + 1 、 num + 2 … ，因此 left 和 right 要先進行加或減。 LLL 為 --left ， RRR 為 ++right 。

Last changed by 
 
arthur chang arthur
0
228
Published on HackMD