# 演算法 HW5

## :book: 觀念題

### 第一題 Heap Sort
1. 下圖為Max Heap。Heap Sort的每一回合，會將Heap的最大值刪除後，又恢復為Heap。請畫出第一回合恢復的過程。
* Ans:
2. 投影片69頁的公式如下，請解釋此公式的含意。
* Ans:
==是指在建構過程所需要的比較次數(從有parent的層級做總和運算)。
由下往上，每個parent都要檢查，所以將每層結果相加。==
2^L^ : 在第L層的最大node數。
2(d-L) : 每一個數值掉到最下層所需要的比較次數(in worst case)
2(d-L)* 2^L^ 每一層所有節點resort所需要的比較次數。
### 第二題 Problem平均的Lower Bound
* 下圖為二元樹。參考投影片77頁，~~已知最高點(root)的深度為1~~(修正)，請算出二元樹的External Path Length，以及葉子平均深度。
* External Path Length
$$ 4 ∗ 3 + 2 ∗ 2 = 16 $$
* 葉子平均深度
$$ {16 \over 6 }= {8 \over 3 }$$

### 第三題 Problem Transformation
* Sorting problem reduces to Convex Hull Problem
* 請說明，若要排序五個數字：4,1,3,2,5，如何轉為Convex Hull Problem後，完成排序。
A(Sorting problem) reduces to B(Convex Hull Problem)
A : (4,1,3,2,5) -> B : {(4,16),(1,1),(3,9),(2,4),(5,25)}
==-> {(1,1),(2,4),(3,9),(4,16),(5,25)} -> 1,2,3,4,5==
## :desktop_computer: 程式題 Greedy類型 (使用語言 : C++)

### 第四題 圓型打字機

* leetcode 1974
* 時間:30分鐘
* 自己完成的程度 : 完全靠自己
* 思路 :
:::success
先計算每次順時針移動所需的時間(取絕對值)。
* 若結果<=13，則表示順時針比較快。
* 若結果大於13(即移動超過半圈)，則表示逆時針移動會比較快，所需時間即==26-順時針移動所需時間==。
:::
* 程式碼 :

class Solution
{
public:
    int minTimeToType(string word)
    {
        int second=0;
        char now=' ';
        word='a'+word; //指針一凱史只到a，直接將a家在字串頭
        for(int i=1; i<word.size(); i++)
        {
            if(abs(word[i]-word[i-1])>13)
                second=second+(26-abs(word[i]-word[i-1]));

            else
                second+=abs(word[i]-word[i-1]);

        }
        return second+word.size()-1; //扣掉a的長度
    }
};

* 通過截圖

### 第五題 跳到最後

* leetcode 55
* 時間:1小時
* 自己完成的程度：參考網路
* 思路 :
:::success
設一個變數用來儲存可達的最遠距離。
並計算可達的index的數值是否可超過原本儲存的最遠距離。
* 若此最遠距離可以剛好抵達或超過終點，則回傳true。
* 若該index(i)>最遠可達距離，則回傳false。
:::
* 程式碼:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int far=0;
        for(int i=0;i<nums.size();i++)
        {
            if(far>=nums.size()-1)
                return true;
            else if(i>far)
                return false;
            if(far<i+nums[i])
                far=i+nums[i];
        }
        return true;
    }
};

* 通過截圖

## :pushpin:心得

### 第六題 本週心得
這次上課內容有heap sort，在之前資料結構的時候也有學到，所以這次接觸起來比較輕鬆。
Problem Transformation則是第一次接觸，說實在有點陌生，還需要多了解一下。
貪婪演算法也是第一次聽過，之前解題好像也用過此方法，只是經過本次程式作業才知道真正的名稱。

###### tags: `演算法`