演算法作業05

第1題: Heap Sort

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

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

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

$L$是目前的樹高，

$d$是樹的整體高度

$(d-L)$就是跑到底所需要的成本

$2(d-L)$是因為有左右兩個子節點，所以要

$\times 2$

$2^L$是第

$L$層的總節點數

$2(d-L)2^L$就是第

$L$層所有節點要往左往右跑到

$d$層的總成本

$\sum _{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

$HIJK(3\times 4)+FG(3\times 2)=18$

葉子平均深度

$HIJK(3\times 4)+FG(2\times 2)=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後，完成排序。

如果將每個數字

$X$轉成二維的點

$(X,X^2)$
在二維平面上會呈現一個拋物線(左邊起來的是負數)

再對這筆資料做凸包就會求出排序了

所以要把

$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$

跑完

$ro{w}_0$

	8	6	8
5	5	0	0
7	3	6	8
10	0	0	0

跑完

$ro{w}_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題：心得

已填