# 2021 年「資訊科技產業專案設計」課程第 1 次作業

contributed by < `老藍 - Old Blue` >
>[英文影片](https://youtu.be/dESR_jP4Vpk)
>[中文影片](https://youtu.be/TxlgiarQ04k)

> [作業要求](https://hackmd.io/@sysprog/info2021-homework1)

**R**epeat: 重複提問，確認自己理解原本的要求
**E**xamples: 針對題目條件，舉出符合的案例，不限於特例
**A**pproach: 說明自己打算採用的方案
**C**ode: 撰寫程式
**T**est: 若不能實際測試，說明驗證程式的方案
**O**ptimization: 優化你的演算法

* LeetCode 題號
* Easy
* [1. Two Sum](https://leetcode.com/problems/two-sum/)
* [27. Remove Element](https://leetcode.com/problems/remove-element/)
* [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
* [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)
* Medium
* [116. Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)
* [138. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)

---
# 改進目標

## interviewer
* 站在 interviewer 的角度思考，進而可以學習題目的多變性，不會只站在背誦者的角度。
* 中文影片雙方幾乎都是背誦者，並沒有辦法了解人。
* 注重在 "inter" ，讓自己學習面試不是背誦，而是表現自己。

---
# 英文題目

## [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = new ListNode(0);
        ListNode* next = head -> next;
        while(head){
            head -> next = pre;
            pre = head;
            head = next;
            next = head -> next;
        }
        return pre;
    }
};

1. 這樣做會出現 UndefinedBehavior 因為在最後一次 next 先做了 head → next，此時 head 已經指向 NULL ，那 head → next 會是什麼？顯然很奇怪。
2. 所以我們可以改進一下，仔細看 `next = head -> next;` 我們其實多宣告了一次，第一次初始化，第二次是指標操作。但其實每次 while 操作都會需要 `next = head -> next;` ，直到 head 已經指向 NULL。
3. 然後可以發現 `next = head -> next;` 其實不一定要先指向 `head -> next;` 可以先確定 head 在哪裡再操作 next。

所以應該變成這樣

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        while(head){
            ListNode* next = head -> next;
            head -> next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
};

Recursion

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !(head -> next)) {
            return head;
        }
        ListNode* node = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return node;
    }
};

延伸閱讀：
* [你所不知道的C語言：遞迴呼叫篇 - HackMD](https://hackmd.io/@sysprog/c-recursion#%E9%81%9E%E8%BF%B4%E7%A8%8B%E5%BC%8F%E6%B2%92%E6%9C%89%E4%BD%A0%E6%83%B3%E5%83%8F%E4%B8%AD%E7%9A%84%E6%85%A2)

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)

1. 這樣做會出現 UndefinedBehavior 因為在最後一次 next 先做了 head → next，此時 head 已經指向 NULL ，那 head → next 會是什麼？顯然很奇怪。
2. 所以我們可以改進一下，仔細看 `next = head -> next;` 我們其實多宣告了一次，第一次初始化，第二次是指標操作。但其實每次 while 操作都會需要 `next = head -> next;` ，直到 head 已經指向 NULL。
3. 然後可以發現 `next = head -> next;` 其實不一定要先指向 `head -> next;` 可以先確定 head 在哪裡再操作 next。

所以應該變成這樣

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        while(head){
            ListNode* next = head -> next;
            head -> next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
};

Recursion

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !(head -> next)) {
            return head;
        }
        ListNode* node = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return node;
    }
};

利用傳入的 parameter `l1`, `l2` 互相比較大小。

多宣告一個 `ListNode dummy;` ，**這個 dummy 之後會被拋棄，因為他是宣告出來指向第一個 node 的節點**，之後回傳的會是 `[dummy.next]` 。

再來多宣告一個 `ListNode *tail = &dummy;` ，我們會利用它來修改 each node 應該指向的下一個 node。

相比結束後，第一步會是將 tail 指向 loser ，如果 l1 == l2 那指向誰都沒差，所以我們選擇保留原位，不修改指向的人。之後記得將 loser 只移動到下一個。

舉例：

l1 = 1 → 2 → 4 → NULL

l2 = 2 → 2 → 3 →8 → NULL

1 round: l1=1 , l2=2
	l1 < l2
	dummy → 1(l1), l1 ++, l1 = 2

2 round: l1=2 , l2=2
	l1 == l2
	dummy → 1(l1) → 2(l2), l2 ++, l2 = 2

3 round: l1=2 , l2=2
	l1 == l2
	dummy → 1(l1) → 2(l2) → 2(l2) , l2 ++ ,l2 = 3

4 round: l1=2 , l2=3
	l1 < l2
	dummy → 1(l1) → 2(l2) → 2(l2) → 2(l1) , l1 ++ ,l1 = 4

5 round: l1=4 , l2=3
	l1 > l2
	dummy → 1(l1) → 2(l2) → 2(l2) → 2(l1) → 3(l2), l2 ++ ,l2 = 8

6 round: l1=4 , l2=8
	l1 < l2
	dummy → 1(l1) → 2(l2) → 2(l2) → 2(l1) → 3(l2) → 4(l1), l1 ++ ,l1 = NULL

7 round: break while ,因為 NULL && 8 = NULL

因為 8 還沒被 tail 指到，所以要判斷誰先到 NULL，要把剩下沒指到的 node，指回去。 
tail->next = (l1 != NULL) ? l1 : l2;
l1 == NULL 所以 tail->next = l2;

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(0);
        ListNode *tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        tail->next = (l1 !=NULL) ? l1 : l2;
        return dummy.next;
    }
};

可以寫得更簡潔

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode l3;
    ListNode* cur = &l3;
    
    for  (; l1 && l2; cur = cur->next)
        (l1->val < l2->val) ? (cur->next = l1, l1 = l1->next) : (cur->next = l2, l2 = l2->next);
        
    cur->next = (l1) ? l1 : l2;
    return l3.next;
}

## [138. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)

這題因為是要 [deep copy](https://en.wikipedia.org/wiki/Object_copying#Deep_copy)，意思是需要複製一個一模一樣的資料，是有實際佔用記憶體的複製，稱為 copy by value。

而另一種我們只創建一個 pointer 並且只有指向預複製的對象，稱之為 [shallow copy](https://en.wikipedia.org/wiki/Object_copying) ，又稱為 copy by address。

int *first, *second;
first = new int[10];
second = first; //shallow copy
second = new int[10];
for (int idx=0;idx<10;idx++) //deep copy
    second[idx] = first[idx];

如果要 deep copy linklist，會面臨一些問題：
1. **next link & random link 的目標尚未創建**
* 因為 next node or random node 尚未創建出來，所以只能先配置 NULL 。
* 等全部創建完再 assign link 。
2. **The new node loses its address**
* 創建的新 node 如果沒有任何 pointer 認養，大家都會變孤兒。宣告一個 pointer array 好像不是很好的解法，畢竟這會造成 **assign random link O(n^2)**。
* 因為是 linklist 所以在配置的時候需要一個一個 node 去掃才能到達目標。所以如果每次 random link 最慘都在 linklist 的最尾巴那就需要 O(n)，然後有 n 個 node ，造就 Time complexity O(n^2)。

而 HashMap 剛好適合處理這個問題。
1. 建立一個 HaspMap ，裡面存放 < Old node , New node > 的記憶體位置。
2. 在 assign link 可以透過先訪問 Key (Old node) 再訪問 Vaule (New node)。

依照上圖 node1 的 random link (紅線)是 node3，可以先找 HashMap 中的 Old node3 再去訪問 New node3。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *cur = head;
        unordered_map<Node*,Node*> Hashmap;
        while(cur){
            Node *copy = new Node(cur -> val); // 先建立 new node
            Hashmap[cur] = copy;// 放入 HashMap
            cur = cur->next;
        }
        
        cur = head;
        while(cur) {
        // assign link
            Hashmap[cur]->next = Hashmap[cur->next];
            Hashmap[cur]->random = Hashmap[cur->random];
            cur=cur->next;
        }

        return Hashmap[head];
    }
};

---

# 中文題目
## [1. Two Sum](https://leetcode.com/problems/two-sum/)

### C++

**R:**
要在一組必有解的陣列中回傳兩個相異數字的 index，這兩個相異數字可以組成 target。

**E:**
所以假設我給一個 {3,3,4} 的陣列，並且我要找 6，喔應該是要回傳 {0,1}，不可以是 {0,0}，{1,1}。

$O(n^2)$

**A:**
很簡單利用兩個 for ，第一個 for 從 array 中指定 1 個 element ，再用第二個 for scan array 其他的 element ，如果第二個 for scan 的其中一個 element 跟第一個 for 指定的 element 加出來為 target ，就可以回傳兩個 for 現在指向 array 的位置 。

$O(n)$

**O:** 這邊引用兩個想法

1. target = x + y
- target - x = y
- 減去 x 後，我們只需要再搜尋 y 是否存在。
2. Hash table
- 為什麼要用 Hash table ，這是因為 Hash table "平均搜尋"時間通常只需要 O(1)，worst case 為O(n) (因為最慘可能要找 n 次。n 為陣列長度，因為可能 hash function 很慘，將所有數字都 hash 到同一個 bucket 裡)，O(1)∗n=O(n)。

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            if (m.count(target - nums[i])) {
                return {m[target - nums[i]], i};
            } else {
                m[nums[i]] = i;
            }
        }
        return {};
    }
};

我們利用 C++ 來解決這個問題。

C++ STL 中的 [unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map) 就是用 hash table 所建立。
儲存的方式會是{key ,value} pair
(Key = 陣列中的數值, Value = 陣列中的位置)
***{key = nums[i] , value = i}***

1. 先宣告一個 `unordered_map<int, int> m`
2. 利用 for loop 來 sacn 整個 array(vector 是加強版的 array)
3. 再利用 if 判斷 target - x = y ，這個 y 是否在這個 Hash table 裡面
* .count 這個 member function 可以搜尋指定的 key 值的個數
* 所以按照剛剛的說法，m.count(裡面是要放 target - nums[i] (x) )
* target - nums[i](x) = y
4. 如果有找到這個 key ，就回傳 vaule 跟當前 i 指向的位置
5. 如果找不掉就將這個數值跟它的位置放入 Hash table

**以 vector = {3,3,4}, target = 6 為例**
1. i = 0, target - num[0] = 3
2. Hash table 找不到 3 (因為剛建立)
* m.count 回傳 0
3. 將 {Key = 3,value = 0} 丟入 hash table
4. i = 1, target - num[0] = 3
5. Hash table 找到 3 (因為剛剛丟入 {3,0})
6. return {0,1}

---

### C

08/20/2021 22:07 Accepted 12 ms 8.8 MB c

沒找到 target 就插入 hash ，所以{ 2, 11, 15} 找 26 時會先插入 11 之後再直接用 15 。

$O(log_n)$
可以再更快，譬如鏈結的方式可以用 [Skip List](https://en.wikipedia.org/wiki/Skip_list)，或許時間複雜度可以降到 O(logn)，但是會增加空間複雜度。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct node{
	long value;
	int index;
	struct node *next;
}newnode;

//每次都插頭
void insert(newnode **hashtable,long value ,int index, int n){
	int t = abs(value) % n;
	newnode *temp = hashtable[t];
	newnode *add = (newnode*)malloc(sizeof(newnode));
	add->value = value;
	add->index = index;
	add->next = temp->next;
	temp->next = add;
}

int search(newnode **hashtable, long target,int n){
	int hashindex = abs(target) % n;
	newnode *temp = hashtable[hashindex]->next;
	while(temp){
		if(temp->value == target)
			return temp->index;
		temp = temp->next;
	}
	return -1;
}

void freeHashTable(newnode **hashtable, int n){
	int i = 0;
	newnode *temp = NULL;
	newnode *delete  = NULL;
	for(i = 0 ; i < n ; i++){
		temp = hashtable[i];
		delete = temp;
		while(temp){
			delete = temp;
			temp = temp->next;
			free(delete);
		}
	}
	free(hashtable);
}
int* twoSum(int nums[], int numsSize, int target) {
    int i = 0, j = 0;
    int n = numsSize, index = 0;
    int* result = NULL;
    newnode** hashTable = (newnode**)malloc(n * sizeof(newnode*));
    // init head node
    for(i = 0; i < n; i++)
        hashTable[i] = (newnode*)calloc(1, sizeof(newnode));
    for(i = 0; i < n; i++) {
        index = search(hashTable, target - nums[i], n);
        if(-1 == index)
            insert(hashTable, nums[i], i, n);
        else {
            result = (int*)malloc(sizeof(int) * 2);
            result[0] = index;
            result[1] = i;//因為減去 target 所以直接回傳 i
            freeHashTable(hashTable, n);
            return result;
        }    
    }
    freeHashTable(hashTable, n);
    return result;
}

int main(int argc ,char** argv){
    int *result = (int*)malloc(sizeof(int) * 2);;
    int numss[2] = {3,3};
    result = twoSum(numss,2,6);
    printf("%d,%d \n",result[0],result[1]);
    free(result);
    return 0;
}

---

For leetcode

**/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct node{
	long value;
	int index;
	struct node *next;
}newnode;

void insert(newnode **hashtable,long value ,int index, int n){
	int t = abs(value) % n;
	newnode *temp = hashtable[t];
	newnode *add = (newnode*)malloc(sizeof(newnode));
	add->value = value;
	add->index = index;
	add->next = temp->next;
	temp->next = add;
}

int search(newnode **hashtable, long target,int n){
	int hashindex = abs(target) % n;
	newnode *temp = hashtable[hashindex]->next;
	while(temp){
		if(temp->value == target)
			return temp->index;
		temp = temp->next;
	}
	return -1;
}

void freeHashTable(newnode **hashtable, int n){
	int i = 0;
	newnode *temp = NULL;
	newnode *delete  = NULL;
	for(i = 0 ; i < n ; i++){
		temp = hashtable[i];
		delete = temp;
		while(temp){
			delete = temp;
			temp = temp->next;
			free(delete);
		}
	}
	free(hashtable);
}
int* twoSum(int* nums, int numsSize, int target , int* returnSize ) {
    int i = 0, j = 0;
    int n = numsSize, index = 0;
//
    *returnSize = 2;
    int *returnValues = malloc((*returnSize) * sizeof(int));
//
    newnode** hashTable = (newnode**)malloc(n * sizeof(newnode*));
    // init head node
    for(i = 0; i < n; i++)
        hashTable[i] = (newnode*)calloc(1, sizeof(newnode));
    for(i = 0; i < n; i++) {
        index = search(hashTable, target - nums[i], n);
        if(-1 == index)
            insert(hashTable, nums[i], i, n);
        else {
            returnValues[0] = index;
            returnValues[1] = i;
            freeHashTable(hashTable, n);
            return returnValues;
        }    
    }
    freeHashTable(hashTable, n);
    return returnValues;
}**

---
## [27. Remove Element](https://leetcode.com/problems/remove-element/)

### C++

**R:**
要從一組陣列 `nums` 中移除 `val`，並且不可以出現空洞，所有被移除數值的位置需要有其他陣列的原本數字填上。

**E:**
`nums` = {3,2,2,3}, `val` = 3，那麽應該輸出 {2,2,_,_}

**A:**
宣告一個 `iterator it`，並且用一個 foor loop 來 scan 這個陣列(scan 陣列，會利用指標來 scan `num[i]`)。

`it`會跟著 num[i] 一起移動，如果 num[i] == val ，那麼因為 num [vector](https://en.cppreference.com/w/cpp/container/vector)，vector 有一個名為 erase 的 Member function，可以用來直接移除數字，並將 vector 後面的數字往前遞補，完全符合題目要求。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        vector<int> :: iterator it;
        it = nums.begin();
        for(int i=0;i<nums.size();i++){
            if(nums[i] == val){
                nums.erase(it);
                it--;
                i--;
            }
            it++;
        }
        return nums.size();
    }
};

## [116. Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)
* [台詞](https://www.notion.so/116-6c21746d74fa4871bf5e8716bfedf43c)

**R**epeat:

給定一個 perfect binary tree，他所有的 leaf 都在同一層，並且只要是 parent node 一定會有兩個children node。

我們需要將這顆 tree 中所有的右節點往它右邊的節點(如果存在，不存在則為 NULL)透過 next 指標指向它。

**E**xamples:

1. 以下圖為例，3 在 2 右邊、5 在 4 右邊、6 在 5 右邊、7 在 6 右邊因此需要透過 struct Node 中的 next 指標來指向。


---

2. 如果只有一個 node ，它既是 root 也是 leaf，因此沒有 chidren ，不需要做任何動作。

但是！他是特殊 case，會這樣說是因為 `Node* root` 可以只傳一個 node ，因此如果用 Recursion method 則需要視為跟“空集合”一樣的 case。

`if(!root || !root->right) return root;`

### C++

這題可用 Recursion 來做，那用 Recursion 的話就要考慮是用 Preorder(DLR)、Inorder(LDR)、Postorder(LRD) 來走訪。先考慮一件事：

如果我們先走訪 node 2(LRD or LDR)，Tree 走訪到 node 2 時，我們應該如何將 node 2 鏈結到 node 3 、node 5 鏈結到 node 6 ?

很顯然沒有辦法將其鏈結起來，這問題也稱為 Local view。因為要鏈結到 node 3 or node 6 都需要 node 2 parent node 1 的幫助(view)。


那 DLR 可以行嗎？答案是肯定的！

如果我們在走訪 Node 1 時先幫 Node 2 中的 Next link 鏈結到 node 3，那就可以解決 Local View 的問題！因為我走訪到 Node 2 就可以直接透過 Next link 訪問 Node 3 進而訪問 Node 6。


所以我們將想法撰寫成 code 其實只有三行。

1. 先將 Current Node 的 left Node 的 Next 指向 Current Node 的 right Node(如果有 Left Node 的話)。

`current->left->next = Current->right;`

2. 第一步破除 Local View 之後，我們再撰寫一個判斷式

`if(current→Next)`

為何需要它？因為如果沒有這條鏈結代表這個 current Node 應該是 Tree 中最右邊的 Node 之一，代表不需要再做鏈結。

再來就是處理會跨越左右子樹的鏈結。

`current->right->next = current->next->left;`

以上三行就貫徹這題的精神 Recursion method 的精神。

class Solution {
public:
    Node* connect(Node* root) {
        if(!root || !root->right) return root;
        root->left->next = root->right;
        if(root->next)
            root->right->next = root->next->left;
        connect(root->left);
        connect(root->right);    
        return root;
    }
};

----