# 演算法作業05

## 第1題: Heap Sort

### 1-1. 下圖為Max Heap。Heap Sort的每一回合，會將Heap的最大值刪除後，又恢復為Heap。請畫出第一回合恢復的過程


### 1-2. 投影片69頁的公式如下，請解釋此公式的含意。

$\sum\limits_{L=0}^{d-1}2(d-L)2^L$

:::info
$L$是目前的樹高，$d$是樹的整體高度
$(d-L)$就是跑到底所需要的成本
$2(d-L)$是因為有左右兩個子節點，所以要$\times 2$
:::

:::info
$2^L$是第$L$層的總節點數
:::

:::info
$2(d-L)2^L$就是第$L$層所有節點要往左往右跑到$d$層的總成本
:::

:::success
$\sum\limits_{L=0}^{d-1}2(d-L)2^L$
就是枚舉$L$從$0$到$d-1$，把第$L$層所有節點要往左往右跑到$d$層的總成本加起來
:::

## 第2題: Problem平均的Lower Bound

### 下圖為二元樹。參考投影片77頁，請算出二元樹的External Path Length，以及葉子平均深度。


#### External Path Length

:::success

$HIJK (3\times4) + FG (3\times2)=18$

:::

#### 葉子平均深度

:::success

$HIJK (3\times4) + FG (2\times2)=16$
葉子數量是$6$
葉子平均深度是$\frac{16}{6}=\frac{8}{3}$

:::

## 第3題: Problem Transformation

### Sorting problem reduces to Convex Hull Problem
### 請說明，若要排序五個數字：4,1,3,2,5，如何轉為Convex Hull Problem後，完成排序。

:::info

如果將每個數字$X$轉成二維的點$(X,X^2)$
在二維平面上會呈現一個拋物線(左邊起來的是負數)
再對這筆資料做凸包就會求出排序了

:::

:::success
所以要把$4,1,3,2,5$轉換成$(4,16),(1,1),(3,9),(2,4),(5,25)$
然後就能對這組資料進行凸包問題了
:::

## 第4題：圓型打字機

### 解題思路

先寫一個`atob`計算從字母甲到字母乙的距離(比較漂亮)

然後再模擬並記錄轉輪盤的過程成本

最後再加上輸出的成本

### 程式碼

class Solution {
public:

    int atob(char a,char b)
    {
        return ((a<=b)?min(b-a,a+'z'-b-'a'+1):min(a-b,b+'z'-a-'a'+1));
    }

    int minTimeToType(string word) {
        char ch='a';
        int sum=0;
        for(int i=0;i<word.size();i++)
        {
            sum+=atob(ch,word[i]);
            ch=word[i];
        }
        return sum+word.size();
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

15分鐘

### 完成程度

完全自己解出

## 第5題：跳到最後


### 解題思路

### 程式碼

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int ma=0,i;
        for(i=0;i<nums.size()&&i<=ma;i++)
        {
            ma=max(ma,i+nums[i]);
        }
        return i==nums.size();
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

15分鐘

### 完成程度

完全自己解出

## 第6題：由各行的和與各列的和求矩陣

### 解題思路

一開始先把每個$colSum[col]$丟進$ans[0][col]$

初始：

| $Sum$ | 8 | 6 | 8 |
| --- | --- | --- | --- |
| 5 | 8 |6 | 8 |
| 7 | 0 | 0 | 0 |
| 10 | 0 | 0 | 0 |

維護每$row$的數字，從左邊開始將數字往下壓
如果不夠就到下一個$col$，太多就丟到下一$row$

跑完$row_0$

| | 8 | 6 | 8 |
| --- | --- | --- | --- |
| 5 | 5 | 0 | 0 |
| 7 | 3 | 6 | 8 |
| 10 | 0 | 0 | 0 |

跑完$row_1$

| | 8 | 6 | 8 |
| --- | --- | --- | --- |
| 5 | 5 | 0 | 0 |
| 7 | 3 | 4 | 0 |
| 10 | 0 | 2 | 8 |

結束

#### 附上我想的過程的畫畫(沒有按照順序畫，都在亂畫)


### 程式碼

class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
        vector< vector<int> > ans(rowSum.size(),vector<int>(colSum.size(),0));
        int i,j;
        for(i=0;i<colSum.size();i++)
        {
            ans[0][i]=colSum[i];
        }
        for(i=0;i<rowSum.size();i++)
        {
            int d=rowSum[i];
            for(j=0;j<colSum.size();j++)
            {
                if(d>0)
                {
                    if(ans[i][j]>d)
                    {
                        ans[i+1][j]=ans[i][j]-d;
                        ans[i][j]=d;
                        d=0;
                    }
                    else
                    {
                        d-=ans[i][j];
                    }
                }
                else
                {
                    if(i+1<rowSum.size())
                    {
                        ans[i+1][j]=ans[i][j];
                        ans[i][j]=0;                        
                    }
                }
            }
        }
        return ans;
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

44分鐘

### 完成程度

完全自己解出

## 第7題：心得

已填