---
# System prepended metadata

title: algo-w9
tags: [Algorithm]

---

# 演算法作業八

## 觀念題
### 第1題: Voronoi Diagram
- 請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程
    - 流程
        1. 尋找$S_L$與$S_R$的凸包
        2. 找到$hull(S_L)$與$hull(S_R)$的公切線$P_1,P_2$($P_1$在上面)
            - $SG = P_1$
            - $HP = \emptyset$
        3. 找到SG的中垂線BS
            - $HP = HP U BS$
            - 如果$SG = P_2$，goto step5
        4. 找到下一邊，並更新$SG$
        5. 將延伸的線discard，並執行合併
- 過程
    ![image](https://github.com/kevin0920911/algorGIF/blob/main/hw8/VD%20-%201.gif?raw=true)
### 第2題: Voronoi Diagram的應用
- 請說明The Euclidean all nearest neighbor problem為何，以及如何應用VD來解此問題？
    - Input: 一個點A
    - Ooutput: 找到離點A最近的點P
- 方法
    - 用VD 演算法產生圖
    - 將VD劃分的區域產生的每一個點畫出水平線 => 產生多個region
    - 先將客人位置找出在哪一條平線
    - 再將客人位置找出在哪一條平線的region
    ![image](https://hackmd.io/_uploads/ryvoKilz0.png)
### 第3題: FFT
- 當輸入為：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，請說明如何應用FFT得到結果(只須說明計算過程，不用算出結果)？
    1. 如果 size == 2
        - $b_0 = a_0+a_1$
        - $b_1 = a_0-a_1$
    - Divide
        2. 將array分成兩個
            - $\{a_0,a_2\dots\}$
            - $\{a_1,a_3\dots\}$
    - Merge
        3. 合併兩array
            - $b_j = c_j + w^{-j}d_j$
            - $b_j+n/2 = c_j - w^{-j}d_j$
- 計算過程
    ![image](https://github.com/kevin0920911/algorGIF/blob/main/hw8/FFT-3.gif?raw=true)
## 程式題

### 第4題: 由Preorder與Inorder建構二元樹
[leetcode 105](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)
- 程式碼
    :::spoiler C++
    ```C++=
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int root = 0;
            return build(preorder,inorder,root,0,inorder.size()-1);
        }
    private:
        TreeNode* build(vector<int>& preorder, vector<int>& inorder,int& root,int left,int right){
            typedef TreeNode* nodePtr;
            if (left > right) return NULL;
            int mid = left;
            while (inorder[mid] != preorder[root]) mid++;

            root++;
            nodePtr newNode = new TreeNode(inorder[mid]);
            newNode->left  = build(preorder,inorder,root,left,mid-1);
            newNode->right = build(preorder,inorder,root,mid+1,right);

            return newNode;
        }
    };
    ```
    :::
- 執行結果 
    ![image](https://hackmd.io/_uploads/Hy2WpsgGA.png)
- 花費時間: 10分鐘
- 完成程度: 靠自己
- 思路
    - ~~資料結構作業有ㄟ酷酷酷~~
    - 切入點: preorder中，第一個就是中間
    - 找到中間的節點 => 製作出一個左右為null之節點
    - Divide
        - 將inorder切成兩個子樹，並繼續遞迴的生成
    - Merge
        - 將左子樹與右子樹接上中間節點就好了
### 第5題: 由Postorder與Inorder建構二元樹
[leetcode 106](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/)
- 程式碼
    :::spoiler C++
    ```C++=
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int root = postorder.size() - 1;
            return build(postorder,inorder,root,0,inorder.size()-1);
        }
    private:
        TreeNode* build(vector<int>& postorder, vector<int>& inorder,int& root,int left,int right){
            typedef TreeNode* nodePtr;
            if (left > right) return NULL;
            int mid = left;
            while (inorder[mid] != postorder[root]) mid++;

            root--;
            nodePtr newNode = new TreeNode(inorder[mid]);
            newNode->right = build(postorder,inorder,root,mid+1,right);
            newNode->left  = build(postorder,inorder,root,left,mid-1);


            return newNode;
        }
    };
    ```
    :::
- 執行結果 
    ![image](https://hackmd.io/_uploads/HJMT0slGC.png)
- 花費時間: 10分鐘
- 完成程度: 靠自己
- 思路
    - 切入點: postorder的中間節點是從後面開始的
    - 找到中間的節點 => 製作出一個左右為null之節點
    - Divide
        - 將inorder切成兩個子樹，並繼續遞迴的生成
    - Merge
        - 將左子樹與右子樹接上中間節點就好了
### 第6題：由Pretorder與Postorder建構二元樹
[leetcode 889](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)
- 程式碼
    :::spoiler C++
    ```C++=
    class Solution {
    typedef TreeNode* nodePtr; 
    private:
        unordered_map<int,int> hashTable;
        int root = 0;
    public:
        nodePtr constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
            for (int i=0;i<postorder.size();i++) hashTable[postorder[i]] = i;

            return  bulid(preorder,postorder,0, postorder.size()-1);
        }
        nodePtr bulid(vector<int>& preorder, vector<int>& postorder, int left,int right){
            if (left>right || root>=preorder.size()) return NULL;

            int val = preorder[root++];

            nodePtr node = new TreeNode(val);
            if (root >= preorder.size() || left==right) return node;

            int post = hashTable[preorder[root]];
            node -> left  = bulid(preorder,postorder,left,post);
            node -> right = bulid(preorder,postorder,post+1,right-1);

            return node; 
        }
    };
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/HycMk3xMA.png)
- 花費時間: 1小時
- 完成程度: 有參考他人
    - [ref](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/solutions/3617169/easy-to-understand-97-beats-c/)
- 思路
    - 卡點: 我一直想說怎麼可能有唯一解 :(
    - 其實概念跟上面差不多
    - 找到中間的節點(這邊以preorder找) => 製作出一個左右為null之節點
    - Divide
        - 將postorder切成兩個子樹，並繼續遞迴的生成
            - 需要注意的是，因為中間節點在右邊所以記得要剔除掉範圍內
    - Merge
        - 將左子樹與右子樹接上中間節點就好了
## 心得
這周繼續上周的進度D&C，學了VD與FFT，一開始以為FFT最難，結果後來發現VD才是大魔王，後來實際操作看看才比較熟悉一點點，感覺困難度超高0.0。

FFT之前在影像處理聽過，我看到數學式還覺得這個東西看起來好難，結果沒想到他居然是用分治法，真佩服想出這些演算法的人。

作業的部分，資料結構就被強迫寫了，所以體感上覺得很輕鬆，真棒。

