# 演算法 HW6

## :book: 觀念題

### 第一題 Minimum Spanning Tree
1. 請以Kruskal方法，找出下圖的最小生成樹。請依序列出所選擇加入的邊。
* 將邊由小到大排序。
* 由小到大將邊加入forest(不能形成迴圈)，直到找到n-1個邊。
2. 同上題，請改為使用Prim(從a開始)方法。
* 會有兩個集合 : A(被選入的點集合)、B(未被選入的點集合)，且會有一個初始選入的點。
* 並從A裡面的點的相鄰點中找到最小權重的邊所連到的節點，將其節點加入A。
* 直到所有點都被巡過了。

### 第二題 Single Source Shortest Path
* 請用Dijkstra演算法找出下圖的由A出發的shortest path tree，並完成右表(共五回合)。

| 回合 | 已選取點 | 選取點 | (B) | \(C\) | (D) | (E) | (F) |
|:----:| ----------- |:------:|:------:|:------:|:------:|:------:|:------:|
| 1 | A | A | ==10== | 15 | +∞ | +∞ | +∞ |
| 2 | A,B | B | - | ==15== | 22 | +∞ | 25 |
| 3 | A,B,C | C | - | - | ==22== | 25 | 25 |
| 4 | A,B,C,D | D | - | - | - | 24 | ==23== |
| 5 | A,B,C,D,F | F | - | - | - | ==24== | - |
| 6 | A,B,C,D,F,E | E | - | - | - | - | - |

### 第三題 Huffman Code
* 已知一份文件內7個符號出現的頻率為：A:2, B:8, C:3, D:4, E:6, F:10, G:7。
* 請找出此7個符號的Huffman code。
* 

| A | B | C | D | E | F | G |
|:----:| --- | ---- | --- | --- | --- | --- |
| 0110 | 00 | 0111 | 010 | 110 | 10 | 111 |
* 若有一組編碼為1100110111，求解碼後的符號。
110 0110 111 -> E A G

## :desktop_computer: 程式題 Greedy類型 (使用語言 : C++)

### 第四題 隔出最多的水

* leetcode 11
* 時間:20分鐘
* 自己完成的程度 : 完全靠自己
* 思路 :
:::success
因為這個題目不需要考慮中間隔板高度，僅需要考慮最旁邊的高度及兩者間的距離，因此
直接計算最大容量 -> ==min(左邊高度，右邊高度) * 兩者距離==;
偌大於原本所記錄的最大容量，則更新最大容量。
且
因為左右兩邊高度會影響最大容量，因此將==較短隔板那邊的index向內縮==，尋找是否更高的隔板可使容量增加。
:::
* 程式碼 :

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0;
        int right=height.size()-1;
        int max=0;
        while(left<right)
        {
            int vol=0;
            vol=min(height[left],height[right])*(right-left);
            if(vol>max)
                max=vol;
            if(height[right]>height[left])
                left++;
            else if(height[right]==height[left])
            {
                left++;
                right--;
            }
            else
                right--;
        }
        return max;
    }
};

* 通過截圖

### 第五題 跳到最後-V2

* leetcode 45
* 時間:40分鐘
* 自己完成的程度：參考網路
* 思路 :
:::success
先判斷目前可到達的最遠位置，並記錄上一次到達之最遠距離。
若現在index為上一次可達最遠之位置 -> 需要再跳一次 -> 次數+1。
並將本次最遠位置設為目前最後一次可達最遠位置。
:::
* 程式碼:

class Solution {
public:
    int jump(vector<int>& nums) {
        int times=0;
        int far=0;
        int end=0;
        
        for(int i=0;i<nums.size()-1;i++)
        {
            far=max(far,nums[i]+i);
            if(i==end)
            {
                times++;
                end=far;
            }
        }
        return times;
    }
};

* 通過截圖

## :pushpin:心得

### 第六題 本週心得
本次觀念題的部分，幾乎離散都有教過，都還有些印象，所以在看影片和寫觀念題的時候，比較輕鬆。
而程式題的部分，不曉得為甚麼，還是有些障礙，看來需要多練練了。

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