# **演算法作業 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，
最後得出合併後的最小距離。
<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);
}
};
```
<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;
}
};
```
<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;
}
};
```
<font size=5>**7. 本周心得**</font>
---
期中考的程式題沒有到很難，時間差一點就能繞出來，也許觀念題要寫更快才行。
教學影片和作業沒什麼問題。
---
若有錯誤歡迎指正
Sign in with Wallet
Connect another wallet