---
# System prepended metadata

title: algo-hw5
tags: [Algorithm]

---

# 演算法作業 HW5

## 觀念題
### 第1題: Heap Sort
1. 下圖為Max Heap。Heap Sort的每一回合，會將Heap的最大值刪除後，又恢復為Heap。請畫出第一回合恢復的過程。
![image](https://raw.githubusercontent.com/kevin0920911/algorGIF/main/hw5/hw5-1.gif)
2. 投影片69頁的公式如下，請解釋此公式的含意。
    - 首先，假設樹高為d，並令L為當前層數
        ![image](https://hackmd.io/_uploads/Sy9ndgpCp.png)

    - 然後，我們就可以知道
        - L層時總共有$2^L$個節點
        - 1個節點最糟要比較$2(d-L)$(一個節點最多兩個小孩)
    - 最後我們只要將$\Sigma step*number$即可
    - 公式整理
        ![image](https://hackmd.io/_uploads/BkFa7AICT.png)
        
### 第2題: Problem平均的Lower Bound
- 下圖為二元樹。參考投影片77頁，請算出二元樹的External Path Length，以及葉子平均深度。
![image](https://hackmd.io/_uploads/H1zh4RLR6.png)
    - **External Path Length：** $3*4 + 2*2= 16$
    - **葉子平均深度：** $16/6 = 2.67$
    
### 第3題: Problem Transformation
- Sorting problem reduces to Convex Hull Problem
- 請說明，若要排序五個數字：4,1,3,2,5，如何轉為Convex Hull Problem後，完成排序。
    :::info
    1. 五個數列$<4,1,3,2,5>$
    2. 先做transformation，做成$(x,x^2)$形式
         - $<(4,16),(1,1),(3.9),(2,4),(5,25)>$
    3. 接下來使用Convex Hull解決此問題，可得
        - $<(1,1),(2,4),(3.9),(4,16),(5,25)>$
    4. 在做transformation，做成$x$形式
        - $<1,2,3,4,5>$
    :::   
    - 因此，我們可以發現Sorting problem reduces to Convex Hull Problem
    - 且Convex Hull Problem比較難解決
    - 因此$\Omega(convex) >= \Omega(sort)-\Omega(\alpha)$
    - 因此我們可以說Convex Hull Problem之lower bound是$O(nlogn)$

## 程式題

### 第4題：圓型打字機
- 程式碼
    :::spoiler rust
    ```rust=
    impl Solution {
        pub fn min_time_to_type(word: String) -> i32 {
            let mut currentChr = b'a';
            let mut step = 0;
            for i in word.bytes(){
                let clockwise = i32::abs(i as i32 - currentChr as i32);
                step += std::cmp::min(clockwise, 26-clockwise) + 1;
                currentChr = i;
            }
            step
        }
    }
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/SyIdcLIRp.png)
- 花費時間：10分鐘
- 完成程度：靠自己
- 思路
    1. 這題直接用模擬就好(模擬打字機)
    2. 每一輪打字時去一直找最小值($min(順時鐘,逆時鐘)$)，並且找完後要切換字元
    3. 然後然後，因為打字也要時間，所以每一輪記得+1

### 第5題：跳到最後
- 程式碼
    :::spoiler rust
    ```rust=
    impl Solution {
        pub fn can_jump(nums: Vec<i32>) -> bool {
            if nums.len() == 1{
                return true;
            }

            let mut step = nums[0];
            for i in 0..nums.len(){
                if (step <= 0){
                    return false;
                }
                step -= 1;
                println!("{}",step);
                if nums[i] > step{
                    step = nums[i];
                }

            }
            return true;
        }
    }

    ```
    :::  
- 執行結果
    ![image](https://hackmd.io/_uploads/rkif1PL0a.png)
- 花費時間：20分鐘
- 完成程度：參考網路解法
    - [ref 1](https://leetcode.com/problems/jump-game/solutions/4534808/super-simple-intuitive-8-line-python-solution-beats-99-92-of-users/)
- 思路
    ~~其實看到別人解題方式覺得這題好好玩~~
    1. **大前提：** 只要當前可走步數=0，就代表跟本不可能
    2. ~~那我們可以把這題當成gogoro換電站~~
        - 當下電池：我目前最多可以跳幾步
        - 換電站電量：每一節點提供你可以跳的步數
    3. 所以每一輪的行為是
        - 先判斷：我現在步數>0，如果不是則不可能
        - 步數-1
        - 最後去判斷，當前步數跟充電站的電量是否達到可交換的程度，是就交換

### 第6題：由各行的和與各列的和求矩陣
- 程式碼
    :::spoiler rust
    ```rust=
    impl Solution {
        pub fn restore_matrix(row_sum: Vec<i32>, col_sum: Vec<i32>) -> Vec<Vec<i32>> {
            let rowSize = row_sum.len();
            let colSize = col_sum.len();

            let mut row_sum = row_sum;
            let mut col_sum = col_sum;

            let mut ans = vec![
                vec![0;colSize]
            ;rowSize];

            let mut i = 0;
            let mut j = 0;

            while i<rowSize && j<colSize{
                ans[i][j] = std::cmp::min(row_sum[i],col_sum[j]);
                row_sum[i] -= ans[i][j];
                col_sum[j] -= ans[i][j];

                if row_sum[i] == 0{
                    i += 1;
                }
                if col_sum[j] == 0{
                    j += 1;
                }
            }
            ans
        }
    }
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/BJMbJvURp.png)
- 花費時間：30分鐘
- 完成程度：參考網路解法
    - [ref1](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/solutions/1572656/easy-python-solution-o-n-m-t-beats-100-explanation/)
- 思路
    ~~這題看到別人思路有一瞬間覺得自己超笨~~
    0. 其實這題有點像2D版雙指針
    1. **大前提：** 我們從<0,0>開始推演就好了
    2. 當進入A<i,j>時我們做三件事
        1. $min(row[i],col[j])$
        2. 將row[i]與col[j]分別減去剛剛取的min
            - 為什麼要找最小，因為有減去的動作，以做到避免負數
        3. 最後去看row[i]或col[j]是否為零，如果是就i++orj++
    ps. 剩下沒用到的要補0喔
    3. 以測試資料1舉例
        ![image](https://raw.githubusercontent.com/kevin0920911/algorGIF/main/hw5/hw5-6.gif)
        
## 心得
好快樂，作業直接開放兩周我覺得是非常好的政策，我覺得使我在時間的運用上更有彈性。

這周主要學了貪心，以及提升lower Bound的方法，我印象最深的是Dijksstra演算法(畢竟計算機網路IP層要算這個，然後我去問陳家銓同學他居然回我以為你學過了:( )，我今天上完才發現原來他也用到了貪心的概念，感覺好酷。

貪心法感覺平常寫程式就一直有在用，我以為我這周作業能速速解決，事實證明我太天真了，看來我還需要提升貪心的技巧。