---
# System prepended metadata

title: '**演算法作業 HW7**'

---

# **演算法作業 HW7**
<font size=5>**1. knapsack problem背包問題**</font>
---
* **有四件物品，編號由1到4，物品重量依序為20,40,10,30。物品價值依序為100,60,30,60。背包最大限重為80。請說明要放哪些東西(可以放部分)，可以讓背包內物品價值總合最大。**
ans：
用價值除與重量算出每個物品單位重量的價值，從最大的開始放。
分別得出 5, 3/2, 3, 2，放入物品1,3,4，再放入一半的物品2。
總價值為220。

<font size=5>**2. Closest Pair Problem**</font>
---
* **請說明Closest Pair Problem，每回合的合併過程？(可參考PPT13頁)**
合併前取出左右兩邊比較後的最小距離d，
接著在L(分割線)到L-d的區域內，
對每個點擴展出的區域搜尋是否還存在更小的距離並更新d，
最後得出合併後的最小距離。
![](https://i.imgur.com/ty7jOzO.png)

<font size=5>**3. Convex Hull Problem**</font>
---
* 請說明Convex Hull Problem，
**(1)為何不直接用sort來得到polygon，而要採用merge？**
因為使用排序得到多邊形會導致時間複雜度更大。
**(2)請說明如何將polygon，修改成convex hull？**
檢查節點構成的角度是不是反角，是的話就刪除掉。

<font size=6>**Divide and Conquer**</font>
---

<font size=5>**4. 將linked list的數列排序**</font>
---
[Sort List - LeetCode](https://leetcode.com/problems/sort-list/)
這題可以用two pointer模擬氣泡排序，也可以用合併排序。
步驟都一樣，只不過數列中間的指標無法直接取得。
在分割時也要記得把左邊和右邊斷開。
完全靠自己，完成時間：20分鐘。

```c++
/**
 * 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* merge(ListNode* l,ListNode* r)
    {
        ListNode dummy;
        ListNode* t=&dummy;
        while(l||r)
        {
            if(((l && r) && l->val<=r->val)||(!r))
            {
                t->next=l;
                l=l->next;
            }
            else
            {
                t->next=r;
                r=r->next;
            }
            t=t->next;
        }
        return dummy.next;
    }
    ListNode* sortList(ListNode* head) {
        if(!head)
            return nullptr;
        if(!head->next)
            return head;
        ListNode *l=head,*tmp=head,*r;
        //head走兩步，r走一步
        //最後head到結尾，tmp會停在中間的上一個點
        head=head->next;//這邊這樣設只是為了讓tmp少走一次
        while(head && head->next)
        {
            head=head->next->next;
            tmp=tmp->next;
        }
        //將l尾端與r斷開
        r=tmp->next;
        tmp->next=nullptr;
        //合併排序
        l=sortList(l);
        r=sortList(r);
        return merge(l,r);
    }
};
```
![](https://i.imgur.com/36fCuIM.png)

<font size=5>**5. 將排序好的數列轉為二元搜尋樹**</font>
---
[Convert Sorted Array to Binary Search Tree - LeetCode](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/)
因為陣列已經排序好了，從上往下直接把樹建起來就好。
完全靠自己，完成時間：一分鐘。
```c++
/**
 * 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 helper(nums, 0, nums.size()-1);
    }
    
    TreeNode* helper(vector<int>& nums, int left, int right){
        
        //越界
        if(left > right)
            return NULL;
        
        //取現在子陣列的中間作為新節點
        int mid = (left + right) / 2;
        TreeNode* temp = new TreeNode(nums[mid]);
        
        //連接左子樹
        temp->left = helper(nums, left, mid-1);
        
        //連接右子樹
        temp->right = helper(nums, mid+1 , right);
        return temp;
    }
};
```
![](https://i.imgur.com/8lmne9q.png)

<font size=5>**6. 美麗數列**</font>
---
[Beautiful Array - LeetCode](https://leetcode.com/problems/beautiful-array/)
由於奇偶相加除2不會是整數，所以不用在乎奇偶間的情況。
換句話說可以直接把奇偶分開處理，專心處理偶跟偶、奇跟奇的相對位置。
因此將數列依照奇偶分開，並不斷分割，最後從小的美麗數列不斷合併成大的美麗數列。
參考別人答案，完成時間：30分鐘。
```c++
class Solution {
public:
    vector<int> beautifulArray(int n) {
        if(n==1)
            return {1};
        //奇數和偶數加起來除2不是整數
        //因此要確保出現美麗數列只要處理偶數和偶數、奇數和奇數的相對位置
        //所以可以把偶數跟技術分開處理
        //不斷呼叫遞迴從小的美麗數列合併成大的美麗數列
        vector<int>even = beautifulArray(n/2);
        vector<int>odd = beautifulArray(n-(n/2));
        vector<int>ans;
        //下面的操作不會影響是否美麗數列
        for(auto e:even)//偶數部分
            ans.push_back(2*e);
        for(auto e:odd)//奇數部分
            ans.push_back((2*e)-1);
        return ans;
    }
};
```
![](https://i.imgur.com/57PrOwg.png)


<font size=5>**7. 本周心得**</font>
---
期中考的程式題沒有到很難，時間差一點就能繞出來，也許觀念題要寫更快才行。
教學影片和作業沒什麼問題。

---
若有錯誤歡迎指正
