# 演算法作業七 ## 觀念題 ### 第1題: 2-D Maxima Finding Problem - 請比較此兩個問題與其解法，有何相同與相異之處。 - 相似 1. 兩個演算法都是使用 D&C(分治法)策略 2. 合併時都要先看右邊 3. 都要用到支配的概念 - 相異 | **2-D Maxima Finding Problem** | **2-D Ranking Finding Problem** | |:------------------------------:|:-------------------------------:| | 找出不被其他點支配的點 | 找出該點支配的數量 | - 若將此問題，由2-D延伸到3-D，請你嘗試設計出一個解法 1. STEP1: 用x y平面切割成四塊 2. STEP2: 將這四塊遞迴的找不被支配的點，我們分四個象限 3. STEP3: 四塊進行合併 - 第三象限與第四象現尋找max(z)，並各自和二、一合併 - 接下來尋找右邊之max(y)，並執行合併 ### 第2題: Closest Pair Problem - 前處理 1. 以y值排列個點 - Divide 2. 如果該區域只剩下一個點，回傳無限 3. 尋找這區x的中位數，並進行切割(等等用$S_L$,$S_R$表示) 4. (GOTO2)，開始遞迴 - Merge 5. 將$S_L$與$S_R$之回傳數值找最小值，以下以$d$表示 - 將中線L左右擴大d (即$[L+d,L-d$]) - For $P_i$ in 左邊的點P($P \in [L-d,L$]) - let $y$=$P_i.y$ - 計算右邊的在$y+d$到$y-d$的全部點之距離 - 若是上面產生之最小值比d還小，則更新d ### 第3題: Convex Hull Problem - 為何不直接用sort來得到polygon，而要採用merge？ - Sort的複雜度：$O(nlogn)$ - Merge複雜度：$O(n)$ - 使用Merge更有效率 - 請說明如何將polygon，修改成convex hull？ - 刪除內角超過180的節點 ## 程式題 ### 第4題: 將linked list的數列排序 [leetcode 148](https://leetcode.com/problems/sort-list/description/) - Solution 1: Convert to array - 程式碼 :::spoiler Python ```python= class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: arr = [] while head: arr.append(head.val) head = head.next arr.sort() if len(arr) == 0: return None newHead = ListNode(arr[0]) curr = newHead for i in arr[1:]: curr.next = ListNode(i) curr = curr.next return newHead ``` ::: - 執行結果 ![image](https://hackmd.io/_uploads/rkalud8W0.png) - 花費時間: 10分鐘 - 完成程度：靠自己 - 思路 ~~好一開始偷懶的解法，我感到十分羞恥~~ 1. 先將LinkList轉換成array 2. 然後直接sort 3. 最後再轉成LinlList - Solution 2: Merge Sort - 程式碼 :::spoiler C++ ```C++= class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head->next) return head; typedef ListNode* nodePtr; nodePtr slow, fast; slow = head; fast = head->next; while (fast && fast->next){ slow = slow->next; fast = fast->next->next; } nodePtr mid = slow->next; slow->next = NULL; nodePtr left = sortList(head); nodePtr right = sortList(mid); nodePtr newHead = new ListNode(); nodePtr curr = newHead; while (left && right){ if (left->val < right->val){ curr->next = left; left = left->next; } else{ curr->next = right; right = right->next; } curr = curr->next; } curr->next = left ? left : right; return newHead->next; } }; ``` ::: - 執行結果 ![image](https://hackmd.io/_uploads/B1qjudLbA.png) - 花費時間: 1小時 - 完成程度：參考他人 - [ref 1](https://leetcode.com/problems/sort-list/solutions/1795310/python3-o-1-space-simple-and-concise-solution-with-explanation-mergesort-easy-to-understand/) - 思路 0. 分享一下我卡的點: 如何找中間 1. 首先先找中間 - 使用龜兔賽跑法 - 當最快抵達終點最慢的將會是中心點 2. Divide - 分成左右各自執行排序 3. Merge - 用類似雙指針的方式 - 將較小的插入list中 - 直到其中一個null時結束 ps: 其中一個null時另一個可能還沒，我的作法是將還沒的直接接上 - 其他 - [merge sort教學](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e) ### 第5題: 將排序好的數列轉為二元搜尋樹 [leetcode 108](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/) - 程式碼 :::spoiler C++ ```C++= class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { typedef TreeNode* nodePtr; if (nums.size() == 0) return NULL; if (nums.size() == 1) return new TreeNode(nums[0]); int mid = nums.size()/2; nodePtr root = new TreeNode(nums[mid]); vector<int> left(nums.begin(),nums.begin()+mid); vector<int> right(nums.begin()+mid+1,nums.end()); root->left = sortedArrayToBST(left); root->right= sortedArrayToBST(right); return root; } }; ``` ::: - 執行結果 ![image](https://hackmd.io/_uploads/H1tcJFUbA.png) - 花費時間: 30分鐘 - 完成程度: 靠自己 - 思路 0. 其實觀察一下測資可以發現輸入根本就是inorder - Divide 1. 每次取出array的中間 - 遞迴中止條件 - 剩下一個 => 回傳該treenode - 剩下零個 => 回傳NULLPTR 2. 接下來把array分成左右(不包含中間)，並遞迴 - Merge 3. 將左子樹和右子樹接上中心點中 ### 第6題： 美麗數列 [leetcode 932](https://leetcode.com/problems/beautiful-array/description/) - 程式碼 :::spoiler C++ ```C++= class Solution { public: vector<int> beautifulArray(int n) { if (n==1) return vector(1,1); vector<int> old = beautifulArray(n-1); vector<int> res; for (int i:old){ if (2*i-1<=n){ res.push_back(2*i-1); } } for (int i:old){ if (2*i<=n){ res.push_back(2*i); } } return res; } }; ``` ::: - 執行結果 ![image](https://hackmd.io/_uploads/ByObzFUZC.png) - 花費時間: 體感2小時... - 完成程度: 參考別人 - [ref1](https://leetcode.com/problems/beautiful-array/solutions/4673410/beautiful-array-efficient-divide-and-conquer-algo/) - [ref2](https://leetcode.com/problems/beautiful-array/solutions/187669/share-my-o-nlogn-c-solution-with-proof-and-explanation/) - [ref3](https://leetcode.com/problems/beautiful-array/solutions/3692187/recursive-code/) - 思路 ~~真的要抱怨這題有夠難解釋，而且很難想~~ 0. 這題主要要我們產生一個沒有左右相加是自己兩倍的數列 - (odd + even = odd) => 奇數放左偶數放右，可避開 - 如果上一個是美麗數列，那我們用上一個進行映射呢? => 這樣用上一個的平移產生的也是美麗數列 - Divide 1. 先找到上一個的美麗數列 - Conquer 2. 接下來將上一個美數列進行平移處理，使他們相對關係不變 - 奇數，以$2n-1$處理 => 加入array(如果>=N)跳過 - 偶數，以$2n$處理 => 加入array(如果>=N)跳過 :::spoiler proof 平移會產生1~N之數列 給定一集合$S=\{1,2...N-1\}$ 則以$2n-1$平移產生$S_1=\{1,3...2N-1\}$ 則以$2n$平移產生$S_2=\{2,4...2N\}$ 因此這兩個集合聯集，一定有1~N的數列 ::: ## 心得 這周教了D&C，來到我最害怕的單元了，從以前就覺得遞迴好難，真是百事可樂。 BTW，我在理解遞迴上，我都使用stack這個資料結構輔助思考，這樣對某些題型我覺得會比較好思考。 我印象最深的是convex hull，之前影像處理有用過，但是是靠opencv的函數實現，我有空寫寫看leetcode 587好了，感覺很有趣。 這周作業我印象最深的是美麗數列，他根本一點都不美麗@@，anyway，我想超級久，我還看了一堆人的解題報告，想超級久，後來歸納兩個規則 1. (odd + even = odd) => 奇數放左偶數放右 2. 如果上一個是美麗數列，那我們用上一個進行映射呢? => 這樣用上一個的平移產生的也是美麗數列 3. 但我覺得這個還是好難解釋，希望檢討時有電神同學or學長能解釋Orz。