# 2022q1 Homework1 (quiz1)
contributed by < `happyjack91630` >
>[作業需求](https://hackmd.io/@sysprog/linux2022-quiz1)
## 第二題 - [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

針對 LeetCode 82. Remove Duplicates from Sorted List II，以下是可能的合法 C 程式實作:
::: success
COND1 = head->next && head->val == head->next.val
COND2 = head->next && head->val == head->next.val
:::
Recursive version

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

這題目的是要將single link-list裡，存在著重複`val`的node都刪掉。
:::info

if (!head)
    return NULL;

上述這段是要確保`head`不為`NULL`。
:::
:::info

if (COND1) {
    /* Remove all duplicate numbers */
    while (COND2)
        head = head->next;
    return deleteDuplicates(head->next);
}

這段程式碼的**註解**就已經說很明白了，就是要來刪除重覆數值的節點。所以`COND1`一定要比較`head->val和head->next.val`是否相同(但是要確保還有`head->next`不是`NULL`，所以也要比較`head->next != NULL`)，如果相同，就進入`if`。但是因為是Sorted list，所以有可能`head->val`也有可能跟`head->next->next.val`相同，所以就利用`while`迴圈來找到最後與`head->val`相同值的節點。因為`head`也是重覆值，所以拿`head->next`做遞迴，去比較下個`head`的情況。
:::

:::info

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

`head->val`與`head->next.val`不相同，所以保留`head，head->next = deleteDuplicates(head->next)`。
:::
Iterative version
>參考 kevinshieh0225

struct ListNode* deleteDuplicates(struct ListNode* head){

    if (!head){
        return NULL;
    }
    struct ListNode **cur = &head;
    struct ListNode *iter = (*cur)->next;
    
    while(iter){
        if(iter && (*cur)->val == iter->val){
            while(iter && (*cur)->val == iter->val){
                iter = iter->next;
            }
            *cur = iter;
            if(!iter){
                break;
            }
        } else{
            cur = &(*cur)->next;
        }
        iter = iter->next;
    }
    return head;
}

## 第三題 - [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/)
針對 LeetCode 146. LRU Cache，以下是可能的合法 C 程式實作:
::: success
MM1 = list_for_each_entry_safe
MM2 = list_for_each_entry
MM3 = list_for_each_entry
MM4 = list_last_entry
:::

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

:::info
`MMM1`是在`lRUCacheFree`，顧名思義是要將 cache 裡的東西全部釋放掉。所以必須走訪所有節點，且執行資源釋放，所以MM1 = `list_for_each_entry_safe`
:::
:::info
`MMM2`是在`lRUCacheGet`，顧名思義是要將cache裡找key值。所以必須遍歷所有的東西，如果有找到對應的key，也要將key在link_list裡的位置移到最前面(head)。所以MM2 = `list_for_each_entry`
:::
:::info
`lRUCachePut`，顧名思義是要將`key`,`value`放入。
在`MM3`的for迴圈要表示的是，我原本的list的就已經有要找的值了，所以我只需要將對應key的list往前擺就好了。MM3 = `list_for_each_entry`
在`MM4`的上面的if是要表達，這個list已經額滿了，我們要將最不常用(list最底層的key)踢掉，所以我認為MM4 = `list_last_entry`
:::