# 演算法導論 HW5
https://hackmd.io/@wang1234/BJuobddW9
## 第1題: Heap Sort
<font color="DarkGray" class="small">1-1. 下圖為Max Heap。Heap Sort的每一回合，會將Heap的最大值刪除後，又恢復為Heap。請畫出第一回合恢復的過程。</font>

<font color="DarkGray" class="small">1-2. 投影片69頁的公式如下，請解釋此公式的含意。</font>
<font color="DeepSkyBlue">此公式為建構一個heap tree所需要的時間複雜度,
計算從0到d-1每一層的比對次數然後加總,
2(d-L)是在第L層的node要確認其位置,所需的比對次數,
2ᴸ則是在第L層的node數量</font>

## 第2題: Problem平均的Lower Bound
<font color="DarkGray" class="small">下圖為二元樹。參考投影片77頁，已知最高點(root)的深度為1，請算出二元樹的External Path Length，以及葉子平均深度。</font>
External Path Length = 3x2+4x4 = <font color="DeepSkyBlue">22</font>
葉子平均深度 = 22/(2+4) ≒ <font color="DeepSkyBlue">3.67</font>

## 第3題: Problem Transformation
<font color="DarkGray" class="small">請說明，若要排序五個數字：4,1,3,2,5，如何轉為Convex Hull Problem後，完成排序。</font>
<font color="DeepSkyBlue">先將sorting的input轉換為Convex Hull的input
4,1,3,2,5 ⇒ (4,16),(1,1),(3,9),(2,4),(5,25)
然後解決Convex Hull Problem</font>
<font color="DeepSkyBlue">再將Convex Hull的output結果轉換為sorting要的結果
(1,1),(2,4),(3,9),(4,16),(5,25) ⇒ 1,2,3,4,5</font>

## 第4題：圓型打字機
[1974. Minimum Time to Type Word Using Special Typewriter](https://leetcode.com/problems/minimum-time-to-type-word-using-special-typewriter/)
<font color="Black">
解題思路:
> 判斷下一位要輸出的字元照a到z的順序去轉動,
> 如果差距超過a到z距離的一半(>13),表示反向轉過去的差距更小,所以加a到z距離減去順向轉的距離,
> 否則,加上順向轉的距離即可,
> 注意:計算距離要加絕對值
</font>

class Solution:
    def minTimeToType(self, word: str) -> int:
        now='a'
        s=0
        for i in word:
            if abs(ord(i)-ord(now))>(ord('z')-ord('a')+1)/2:
                s+=(ord('z')-ord('a')+1)-abs(ord(i)-ord(now))
            else:
                s+=abs(ord(i)-ord(now))
            now=i
            s+=1
        return s

花40分鐘 , 參考:
[Day 23：1974. Minimum Time to Type Word Using Special Typewriter - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/articles/10278881)

## 第5題：跳到最後
[55. Jump Game](https://leetcode.com/problems/jump-game/)
<font color="Black">
解題思路:
> 先做一次如果nums的長度小於等於1時,return值必為True的判斷,
> 而後變數x紀錄頭一個還沒計算過距離的數字,
> far表示目前可到達的最遠處,more_far存放far的變動,
> 從x=0開始,在它可達的最遠距離內,nums的數字逐一計算可達的最遠處,
> 如果發現有到nums的最後一位,return True,
> 或是如果大於前一次紀錄的far,將新的最遠距離存在more_far,
> 然後更新x和far等數值,
> 若是沒算得更遠的可達距離,就結束while迴圈,return False
</font>

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums)<=1 :
            return True
        x=0
        far=x+nums[x]
        more_far=far
        while more_far!=0:
            for i in range(x,far+1):
                if i+nums[i]>=len(nums)-1:
                    return True
                elif i+nums[i]>more_far:
                    more_far=i+nums[i]
            x=far+1
            if more_far==far:
                more_far=0
            far=more_far
        return False

花60分鐘 , 完全靠自己

## 第7題：由各行的和與各列的和求矩陣
[1605. Find Valid Matrix Given Row and Column Sums](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/)
<font color="Black">
解題思路:
> for迴圈由上而下,由左而右,逐一填入可能的最大值,
> 即為對應的rowSum和colSum的最小值,
> 而後在對應的rowSum和colSum中減去已經填入的數,
> 這樣最後如果rowSum和colSum都已歸零,剩餘的空位也自然都會補上0,也是一種符合題目要求的解
</font>

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        col, row = len(colSum), len(rowSum)
        array=[[0 for _ in range(col)] for _ in range(row)]
        for i in range(row):
            for j in range(col):
                if(min(colSum[j],rowSum[i]))>=0:
                    temp=min(colSum[j],rowSum[i])
                else:
                    temp=0
                array[i][j]=temp
                colSum[j]-=temp
                rowSum[i]-=temp
        return array

花60分鐘 , 參考:
[【每日一题】1605. Find Valid Matrix Given Row and Column Sums, 10/5/2020](https://www.youtube.com/watch?v=UygOEphZDe8)

## 心得
近兩周的作業有明顯感覺不只上課內容變多變難,影片需要反覆觀看之外,程式題的部分也不像之前看完題目就能想到解法的雛形