2022q1 Homework1 (quiz1)

contributed by < YiChainLin >

測驗題目

測驗2

Leetcode : 82. Remove Duplicates from Sorted List II，以下是可能的合法 C 程式實作:

所使用的 linked list 結構為單向連結的方式

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

完整程式

#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->next && head->val == head->next->val
COND2 = head->next && head->val == head->next->val

題目採取遞迴的方式實作
思考要點:
- 進入判斷式的條件應要有與下一個節點元素相同的時候成立
- 若是重複時則 linked list
用以下範例解釋運作的過程
原始的狀態:

head 指向第一個元素，其值為 1 ，與 head->next->val 的值做比較，所以 1 != 2 因此將下一個元素 head->next 進入遞迴

head 指向第二個元素，其值為 2 ，與 head->next->val 的值做比較，所以 2 == 2 進入判斷式中

判斷式中執行 head = head->next ， (注意:這裡的 head 是遞迴上一層的 head->next )，然後在進行下兩個元素的判斷， 2 != 4 所以重複元素的判斷已結束

head = head->next 走訪至第四個節點後返回此沒有重複的節點

head->next = deleteDuplicates(head->next); 返回值為 val = 4 的節點，使一開始的 head 連結到第四個元素，但是重複的元素只是被移除( remove )並未被刪除( delete )，持續的遞迴的操作將把所有重複的元素移除

非遞迴的做法:
將上述的遞迴型式改用非遞迴的方式，在效能上會有比較好的表現
思考方式
- 將重複前的節點先存下來，使用一個指標進行重複點的走訪
- 將暫存節點換連至未重複點

#include <stddef.h>

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

struct ListNode* deleteDuplicates(struct ListNode* head){
    if (!head)
        return NULL;
    
    struct ListNode *tmp = malloc(sizeof(struct ListNode));
    tmp->next = head;
    
    struct ListNode *prev = tmp;
    struct ListNode *cur = head;
    while (cur) 
    {
        while (cur->next && cur->val == cur->next->val)
        {
            cur = cur->next;
        }
        
        if (prev->next == cur)
            prev = prev->next;
        else
            prev->next = cur->next;
        
        cur = cur->next;
    }
    return tmp->next;
}

建立一個 tmp 的節點，使 tmp->next = head 指向 head ，建立兩個指標分別為 prev 與 cur 作為走訪節點用途

while 迴圈中的判斷條件為 cur->next && cur->val == cur->next->val 所以 head != 1 並未有重複點的情況，因此兩個指標個都向前走訪一個節點 prev = prev->next; cur = cur->next;

cur 指標遇到重複點進入 while 迴圈中持續走訪重複的節點，直到不重複

此時 prev->next 指標指向未重複點也就是 cur->next 完成重複點的移除，移除所有的重複點後， return tmp->next 也就是原本的 head

改寫成 circular doubly-linked list
學生在 lab0-c中有實作，當中有程式運行的流程

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_is_singular(head))
        return false;
    struct list_head *tmp = head->next;
    struct list_head *if_dup = NULL;

    while (tmp != head) {
        element_t *ele_dup = list_entry(tmp, element_t, list);
        element_t *ele_dup_next = list_entry(tmp->next, element_t, list);

        while (!strcmp(ele_dup->value, ele_dup_next->value)) {
            if_dup = tmp;
            list_del(tmp->next);
            q_release_element(ele_dup_next);
            ele_dup_next = list_entry(tmp->next, element_t, list);
            if (tmp->next == head)
                break;
        }

        tmp = tmp->next;
        if (if_dup) {
            element_t *ele_dup_a = list_entry(if_dup, element_t, list);
            list_del(if_dup);
            q_release_element(ele_dup_a);
            if_dup = NULL;
        }
        if (tmp->next == head)
            break;
    }
    return true;
}

測驗3

Leetcode : 146. LRU Cache，以下是可能的合法 C 程式實作:

LRU 全名為 least recently used，在 cache 容量滿了的情況，將最久沒使用的資料刪除，已能空出新的空間

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

使用到 list.h中 doubly circular-linked list 的結構

struct list_head {
    struct list_head *next
    struct list_head *prev;
};

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

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

2022q1 Homework1 (quiz1)

測驗2

測驗3

Read more

2022q1 Homework6 (ktcp)

2022q1 Homework 5 (quiz8)

2022q1 Homework3 (quiz3)

2022q1 Homework2 (quiz2)