# 演算法 HW7

## :book: 觀念題

### 第一題 knapsack problem背包問題(Ch3)
有四件物品，編號由1到4，物品重量依序為20,40,10,30。物品價值依序為100,60,30,60。背包最大限重為80。請說明要放哪些東西(可以放部分)，可以讓背包內物品價值總合最大。

* ans
1: 100/20=5
2: 60/40=1.5
3: 30/10=3
4: 60/30=2
東西 : 1號 (20) 2號(20) 3號(10) 4號(30)
價值 : 5 * 20 + 3 * 10 + 2 * 30 + 1.5 * 20 = 100 + 30 + 60 + 30 = 220
總重 : 80

### 第二題 Closest Pair Problem
請說明Closest Pair Problem，每回合的合併過程？(可參考PPT13頁)

* ans
1. 先進行排序 → 較容易找出需要做比較的點
2. 若只有一個點 → 距離為無限大
3. 找出中線L，分兩等分(S_L，S_R)，不斷分割每群只剩一個點
4. 找出每群最短距離(d_L，d_R)，算出d=min(d_L,d_R)
5. 有一點P其x值介於L-d和L之間，其y表示為yp，並找出所有所有介於L和L-d以及yp-d和yp+d之間的點。若找到一點和P的距離小於d，則將d值改為此距離。

### 第三題 Convex Hull Problem
請說明Convex Hull Problem，
(1)為何不直接用sort來得到polygon，而要採用merge？
(2)請說明如何將polygon，修改成convex hull？

:::success

給定一平面上的點集合，找出一個最小的凸多邊形可以包含所有的點。
1.先找出多邊形(sort or merge)
2.找凸多邊形(reflex angle)
:::
* ans
* 第一題
因為merge的時間複雜度<sort的時間複雜度
* sort : 將向量角度做排序，即可得到一個多邊形。而排序的間複雜度至少為nlogn，若選擇排序，會使時間複雜度變得更大。
* merge : 左邊的凸多邊形的點順序不變，接著先找出右邊凸多邊形的最高及最低的點，此兩點可把一個凸邊行切成左右兩邊，左邊的順序為順時針，右邊為逆時針。因此會得到三組以排序好的序列。再將此三組序列進行merge即可得到一個多邊形。(依照向量)
* 第二題
檢查每一個點的內角是否超過180度(reflex angle)，若有超過，則將該點刪除。(Graham scan)
## :desktop_computer: 程式題 Divide and Conquer (使用語言 : C++)

### 第四題 將linked list的數列排序

* leetcode 148
* 時間:20分鐘
* 自己完成的程度 : 參考網路
* 思路 :
:::success
1.先放入vector內，在進行sort，再放進list內進行回傳。
2.使用merge sort進行排序。
:::
* 程式碼 :
* vector

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            vector<int> nums;
            ListNode* temp=head;
            while(temp)
            {
                nums.push_back(temp->val);
                temp=temp->next;
            }
            sort(nums.begin(),nums.end());

            ListNode* ans=new ListNode;
            ListNode* answer=ans;
            for(int i=0;i<nums.size();i++)
            {
                ans->next=new ListNode(nums[i]);
                ans=ans->next;
            }
            return answer->next;
        }
    };

* merge sort

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            // 是空的list或是只有一個，直接回傳
            if(head==NULL || head->next==NULL)
                return head;
            ListNode *temp=head,*slow=head,*fast=head;
            // 使用兩個指標，一個一次前進一個，一個一次前進兩個
            // 當快指標走到最後的時候，慢指標會剛好走到中間
             while (fast && fast->next) 
             {
                 temp=slow;
                 slow=slow->next;
                 fast=fast->next->next;
             }
            // 此時，slow剛好到中間
            temp -> next = NULL;  //斷開
             return Merge(sortList(head), sortList(slow));
        }
        //Merge Sort
        ListNode* Merge(ListNode *L1,ListNode *L2)
        {
            ListNode* t1=new ListNode;
            ListNode* t2=t1;
            while(L1 && L2)
            {
                if(L1->val<L2->val)
                {
                    t2->next=L1;
                    L1=L1->next;
                }
                else
                {
                    t2->next=L2;
                    L2=L2->next;
                }
                t2=t2->next;
            }

            if(L1)
                t2->next=L1;
            if(L2)
                t2->next=L2;
            return t1->next;
        }
    };

* 通過截圖
* vector
* merge sort

### 第五題 將排序好的數列轉為二元搜尋樹

* leetcode 108
* 時間:15分鐘
* 自己完成的程度：靠自己
* 思路 :
:::success
因已知依排序好數列，因此只須將此數列一值分割成兩等分，並將其中間值訂為root，直到數列全被巡過。
:::
* 程式碼:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return solve(nums,0,nums.size()-1);
    }
    TreeNode* solve(vector<int> &nums,int head,int tail)
    {
        if(head>tail)
            return NULL;
        
        int mid=head+(tail-head)/2;
        
        TreeNode* temp=new TreeNode;
        temp->val=nums[mid];
        
        temp->left=solve(nums,head,mid-1);
        temp->right=solve(nums,mid+1,tail);
        
        return temp;
    }
};

* 通過截圖
### 相關題(自由作答)
* leetcode 109
* 時間:15分鐘
* 自己完成的程度：靠自己
* 思路 :
:::success
先將提供的list轉為vector。
因已知依排序好數列，因此只須將此數列一值分割成兩等分，並將其中間值訂為root，直到數列全被巡過。
:::
* 程式碼:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        ListNode *temp=head;
        vector<int> nums;
        while(temp)
        {
            nums.push_back(temp->val);
            temp=temp->next;
        }
        return solve(nums,0,nums.size()-1);
    }
    TreeNode* solve(vector<int> &nums,int head,int tail)
    {
        if(head>tail)
            return NULL;
        
        int mid=head+(tail-head)/2;
        
        TreeNode* temp=new TreeNode;
        temp->val=nums[mid];
        
        temp->left=solve(nums,head,mid-1);
        temp->right=solve(nums,mid+1,tail);
        
        return temp;
    }
};

* 通過截圖

## :pushpin:心得

### 第六題 本週心得
遞迴之前一年級就有碰過了，但沒有學得很好，所以本次在寫程式題的時候有點吃緊，希望可以越來越熟悉。

###### tags: `演算法`