# 1103757喬伊波伊HW5
## 1. Heap Sort
### 1-1. 下圖為Max Heap。Heap Sort的每一回合，會將Heap的最大值刪除後，又恢復為Heap。請畫出第一回合恢復的過程。
解：
### 1-2. 投影片69頁的公式如下，請解釋此公式的含意。
解：
## 2.Problem平均的Lower Bound
* ### 下圖為二元樹。參考投影片77頁，已知最高點(root)的深度為1，請算出二元樹的External Path Length，以及葉子平均深度。
解：
## 3.Problem Transformation
* ### Sorting problem reduces to Convex Hull Problem
* ### 請說明，若要排序五個數字：4,1,3,2,5，如何轉為Convex Hull Problem後，完成排序。
解：
## 4.圓型打字機[Minimum Time to Type Word Using Special Typewriter](https://leetcode.com/problems/minimum-time-to-type-word-using-special-typewriter/)
* ### 解題思路：
建立一個nowword來當比較和可用ascii code來相減的變數，相減後如果大於13代表換個方向走會比較好所以26-movsec，若沒有沒事，最後在更新movesecond和nowword的data，以此類推直到迴圈的i大於等於word.size()。
* ### 程式碼：

int minTimeToType(string word) {
    char nowword='a';
    int movesecond=0;
    for(int i=0;i<word.size();i++){
        int a=int(nowword);
        int b=int(word[i]);
        int movesec=abs(a-b);
        if(movesec>13){
            movesec=26-movesec;
        }
        movesecond+=(movesec+1);
        nowword=word[i];
    }
    return movesecond;
}

* ### 畫面截圖：

* ### 花費的時間：30min

* ### 完成比例：看老師下面給的提示

## 5.跳到最後[Jump Game](https://leetcode.com/problems/jump-game/)
* ### 解題思路：
建立一個temp變數，存index+nums[index]和temp的最大值，在比較看是否temp<i如果是的話就return false，否則迴圈繼續執行到結束後return true。
* ### 程式碼：

bool canJump(vector<int>& nums) {
    int temp=0;
    for(int i=0;i<nums.size();i++){
        if(temp<i)return false;
        temp=max(i+nums[i],temp);
    }
    return true;
}

* ### 畫面截圖：

* ### 花費的時間：30min

* ### 完成比例：有看solution

## 6.由各行的和與各列的和求矩陣[Find Valid Matrix Given Row and Column Sums](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/)
* ### 解題思路：
這題完全想不到怎麼寫，只能看solution裡面最容易理解的來參考，這參考的解法是先用迴圈中的迴圈，然後看rowsum[i]有沒有比colsum[j]小，有的話做一些讓我看很久的value update，沒有的話做跟上面差不多的value update，但看了很久還是沒有很了解，希望老師上課可以詳細講解。
* ### 程式碼：

vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
    int r=rowSum.size();
    int c=colSum.size();
    vector<vector<int>> a(r, vector<int> (c,0));
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            if(rowSum[i]<colSum[j]){
                a[i][j]=rowSum[i];
                colSum[j]=colSum[j]-rowSum[i];
                rowSum[i]=0;
            }
            else{
                a[i][j]=colSum[j];
                rowSum[i]=rowSum[i]-colSum[j];
                colSum[j]=0;
            }
        }
    }
    return a;
}

* ### 畫面截圖：

* ### 花費的時間：50min

* ### 完成比例：有看solution
## 7.本週心得：
這星期的作業程式題是，上演算法以來最難的一次，有些看solution還不太了解為什麼要這樣做，感覺有點再背公式的感覺，希望老師下次上課可以詳細講解和分解解題過程，因為如過這樣用背的沒有完全了解它背後的詳細解法，程式能力就無法進步，再麻煩老師了，謝謝！