# 演算法導論 HW7
https://hackmd.io/@wang1234/HJMuNhkm2
## 第1題: knapsack problem背包問題(Ch3)
n=4 , M=80 ,
(p₁ , p₂ , p₃ , p₄)=(100,60,30,60)
(w₁ , w₂ , w₃ , w₄)=(20,40,10,30)
p₁/w₁ = 100/20 = 5   ⇒ 1
p₂/w₂ = 60/40 = 1.5   ⇒ 0.5
p₃/w₃ = 30/10 = 3   ⇒ 1
p₄/w₄ = 60/30 = 2   ⇒ 1
20×1 + 10×1 + 30×1 + 40×0.5 = 80
<font color=#3535FF>x₁=1 , x₂=0.5 , x₃=1 , x₄=1</font>

## 第2題: Closest Pair Problem
以分半的方式將集合S從x=L處分成的S_L和S_R，
然後分別計算出他們內部最近點的距離，令其為d_L和d_R，再取兩者的最小值設為d，
而後回到分界線x=L處，以位在x=L-d ~ L區塊的點的y值，例如:有一<font color=＃008000>P點座標(a,b)</font>，
對應到另半邊<font color=＃00A2FF>x=L ~ L+d</font>的區塊，在<font color=＃00A2FF>y=b-d ~ b+d</font>內尋找是否有落點，且實際計算其與P點的距離是否小於d;
若是位於x=L ~ L+d區塊的點，則在x=L-d ~ L區塊搜索
將此交界處檢查一遍後便可得到集合S裡最近點的距離

## 第3題: Convex Hull Problem
<font color="DarkGray" class="small">請說明Convex Hull Problem，
(1)為何不直接用sort來得到polygon，而要採用merge?</font>
<b>sort做法: </b>從左側多邊形中心的一p點連線至左右兩多邊形的頂點，依連線的角度進行排序，得到合併後的多邊形
<b>merge做法: </b>在合併後的多邊形的有三項特性，
其一是p點所在的左側多邊形，全部頂點依然維持逆時針方向，
而右側部分則以縱向上的最低點與最高點分為兩半，右半部分也依然維持逆時針方向，
但位於(右側多邊形)左半部分的頂點要變成順時針方向的排序，
依這些特性整理出三個區塊，再進行merge
<font color=＃00A2FF>因為merge做法的時間複雜度比sort做法的低</font>
<font color="DarkGray" class="small">(2)請說明如何將polygon，修改成convex hull？</font>
<font color=＃00A2FF>將在合併後的多邊形裡，造成reflex angle(反角:內角角度為180°~360°)的節點刪除</font>

## 第4題: 將linked list的數列排序
[148. Sort List](https://leetcode.com/problems/sort-list/)
<font color="Black">解題思路:
> 主要解題的merge sort程式碼式來自其他網頁
> 有merge_sort和merge兩個函式
> 在merge_sort裡用遞迴的方式將list切分成兩半
> 直到傳入的list(nlst)只剩一個或零個成員(空列表)
> 在merge裡則將傳入的兩個list(left,right)比較大小並進行合併</font>

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        def merge(left, right):
            output = []
            while left and right:
                if left[0] <= right[0]:
                    output.append(left.pop(0))
                else:
                    output.append(right.pop(0))
            if left:
                output += left
            if right:
                output += right
            return output

        def merge_sort(nlst):
            if len(nlst) <= 1:
                return nlst
            mid = len(nlst) // 2
            left = nlst[:mid]
            right = nlst[mid:]
            left = merge_sort(left)
            right = merge_sort(right)
            return merge(left, right)
        
        temp=[]
        while head:
            temp.append(head.val)
            head=head.next
        temp=merge_sort(temp)
        p=ListNode(0)
        ans=p
        for i in temp:
            p.next=ListNode(i)
            p=p.next
        return ans.next

花60分鐘，參考:
[Converting a list to a linked list](https://stackoverflow.com/questions/31553576/converting-a-list-to-a-linked-list)
[【Day25】[演算法]-合併排序法Merge Sort](https://ithelp.ithome.com.tw/articles/10278179)
[Python tutorial 20 | Merge Sort （合併排序法）](https://anchi-tang.medium.com/python-tutorial-20-merge-sort-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-dd3e087898a6)

## 第5題: 將排序好的數列轉為二元搜尋樹
[108. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/)
<font color="Black">解題思路:
> 因為題目給的是遞增list,所以可以優先選擇位於列表中間的值來加入BST,做為root或parent
> 由此便能建構出平衡的BST
> 再用遞迴傳入比選到的節點(node)小的部分,以建構左子樹
> 比選到的節點大的部分,則建構右子樹</font>

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def bst(start,end):
            if start > end:
                return None
            mid=(start + end)//2
            root=TreeNode(nums[mid])
            root.left=bst(start,mid-1)
            root.right=bst(mid+1,end)
            return root
        return bst(0,len(nums)-1)

花40分鐘，抄:
[資料結構 - Tree 的介紹(使用Python)](https://newaurora.pixnet.net/blog/post/224703989)
[Easy Python Solution](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/solutions/2407334/easy-python-solution/?page=2&languageTags=python3)

## 第6題： 美麗數列
[932. Beautiful Array](https://leetcode.com/problems/beautiful-array/)
<font color="Black">解題思路:
> 我只有觀察出把奇數與偶數各分一邊,就能分成兩個互不影響的區塊
> 直到去觀摩的Solutions裡的程式碼,才發現只要延續從list分割奇偶數的規則繼續切割,最後再合併便可得到解答</font>

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        nums = list(range(1, n+1))
        
        def helper(nums) -> List[int]:
            if len(nums) < 3:
                return nums
            odd = nums[::2]
            even = nums[1::2]
            return helper(odd) + helper(even)

        return helper(nums) 

花90分鐘，抄:
[Python easy solution](https://leetcode.com/problems/beautiful-array/solutions/1676288/python-easy-solution/?languageTags=python3)
[Python3 solution with detailed explanation - Beautiful Array](https://leetcode.com/problems/beautiful-array/solutions/644612/python3-solution-with-detailed-explanation-beautiful-array/?languageTags=python3&topicTags=divide-and-conquer)

## 心得
這次的程式題都借助其他資訊或答案才完成，對merge sort、Linked List、Binary search tree，甚至包括遞迴，在觀念不清晰或應用不熟練，導致沒能夠自己寫出解法。