---
tags: linux2022
---
# 2022q1 Homework1 (quiz1)
contributed by < `YiChainLin` >
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗2
[Leetcode : 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)，以下是可能的合法 C 程式實作:
* 所使用的 `linked list` 結構為單向連結的方式
```c
struct ListNode {
int val;
struct ListNode *next;
};
```
* 完整程式
```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->next && head->val == head->next->val
COND2 = head->next && head->val == head->next->val
```
* 題目採取遞迴的方式實作
* 思考要點:
* 進入判斷式的條件應要有與下一個節點元素相同的時候成立
* 若是重複時則 `linked list`
* 用以下範例解釋運作的過程
* 原始的狀態:
1. `head` 指向第一個元素，其值為 1 ，與 `head->next->val` 的值做比較，所以 `1 != 2` 因此將下一個元素 `head->next` 進入遞迴
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
}
head->A->B->C->D->E->NULL
}
```
2. `head` 指向第二個元素，其值為 2 ，與 `head->next->val` 的值做比較，所以 `2 == 2` 進入判斷式中
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
}
head->B
A->B->C->D->E->NULL
}
```
3. 判斷式中執行 `head = head->next` ， (注意:這裡的 `head` 是遞迴上一層的 `head->next` )，然後在進行下兩個元素的判斷， `2 != 4` 所以重複元素的判斷已結束
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
}
head->C
A->B->C->D->E->NULL
}
```
4. `head = head->next` 走訪至第四個節點後返回此沒有重複的節點
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
}
head->D
A->B->C->D->E->NULL
}
```
5. `head->next = deleteDuplicates(head->next);` 返回值為 `val = 4` 的節點，使一開始的 `head` 連結到第四個元素，但是重複的元素只是被移除( `remove` )並未被刪除( `delete` )，持續的遞迴的操作將把所有重複的元素移除
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
NULL[shape=plaintext,fontcolor=black]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
}
head->A
A->D->E->NULL
B->C
}
```
* 非遞迴的做法:
將上述的遞迴型式改用非遞迴的方式，在效能上會有比較好的表現
* 思考方式
* 將重複前的節點先存下來，使用一個指標進行重複點的走訪
* 將暫存節點換連至未重複點
```c
#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;
}
```
1. 建立一個 `tmp` 的節點，使 `tmp->next = head` 指向 `head` ，建立兩個指標分別為 `prev` 與 `cur` 作為走訪節點用途
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=black]
prev[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
tmp[label=tmp]
}
prev->tmp cur->head
tmp->head->A->B->C->D->E->NULL
}
```
2. `while` 迴圈中的判斷條件為 `cur->next && cur->val == cur->next->val` 所以 `head != 1` 並未有重複點的情況，因此兩個指標個都向前走訪一個節點 `prev = prev->next;` `cur = cur->next;`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=black]
prev[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
tmp[label=tmp]
}
prev->A cur->B
tmp->head->A->B->C->D->E->NULL
}
```
3. `cur` 指標遇到重複點進入 `while` 迴圈中持續走訪重複的節點，直到不重複
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=black]
prev[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
tmp[label=tmp]
}
prev->A cur->C
tmp->head->A->B->C->D->E->NULL
}
```
4. 此時 `prev->next` 指標指向未重複點也就是 `cur->next` 完成重複點的移除，移除所有的重複點後， `return tmp->next` 也就是原本的 `head`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=black]
prev[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=1]
B[label=2]
C[label=2]
D[label=4]
E[label=7]
tmp[label=tmp]
}
prev->A cur->D B->C
tmp->head->A->D->E->NULL
}
```
* 改寫成 circular doubly-linked list
學生在 [lab0-c](https://hackmd.io/@YiChianLin/linux2022-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](https://leetcode.com/problems/lru-cache/)，以下是可能的合法 C 程式實作:
* LRU 全名為 [least recently used](https://zh.wikipedia.org/wiki/%E5%BF%AB%E5%8F%96%E6%96%87%E4%BB%B6%E7%BD%AE%E6%8F%9B%E6%A9%9F%E5%88%B6)，在 cache 容量滿了的情況，將最久沒使用的資料刪除，已能空出新的空間
```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;
}
```
* 使用到 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)中 `doubly circular-linked list` 的結構
```c
struct list_head {
struct list_head *next
struct list_head *prev;
};
```
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
```
```c
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
Sign in with Wallet
Connect another wallet