# 演算法作業06

## 第1題: Huffman Code

:::info
* 已知一份文件內7個符號出現的頻率為：A:2, B:8: C:3, D:4, E:6, F:10, G:7。
* 請找出此7個符號的Huffman code。
* 若有一組編碼為1100110111，求解碼後的符號。
:::


:::success

| A | B | C | D | E | F | G |
| ---- | --- | ---- | --- | --- | --- | --- |
| 0110 | 00 | 0111 | 010 | 110 | 10 | 111 |

1100110111 => EAG

:::

## 第2題: 換錢問題

:::info
* 新台幣常用的紙鈔、硬幣有1元，5元，10元，50元，100元，500元，1000元。
* 若要提領n元，如何以最少數量的紙鈔、硬幣組成 n 元。
* 請以Greedy策略設計出一個演算法解決換錢問題，並以說明此演算法符合Greedy的3個條件。
:::

:::success
因為幣值都是倍數關係，所以這題可以不用DP，
只要從最大的幣值往下找，可以用減的或除的，都一樣，

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    int coins[7]={1,5,10,50,100,500,1000};
    int n,i,sum=0;
    cin>>n;
    for(i=6;i>=0;i--)
    {
        sum+=n/coins[i];
        n%=coins[i];
    }
    cout<<sum;
}

程式碼大概就是這樣

1. 可以拆分成幾個小問題

- 可以，這個問題可以分成每個幣值可以換多少。

2. 區域最佳解

- 每個幣值都可以找到自己可以換多少，也就是區域最佳解。

3. 全域最佳解

- 從最大的幣值開始慢慢往下的過程，就在做全域的協調，
貪心的從最大的幣值開始就是在找全域最佳解。

:::

## 第3題: Dijkstra演算法

:::info
* 請用Dijkstra演算法找出下圖的由a出發的shortest path tree，並完成右表。
:::


:::success

### 過程

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

### 最後結果

| ( A ) | ( B ) | ( C ) | ( D ) | ( E ) | ( F ) |
|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|
| 0 | 10 | 15 | 22 | 24 | 23 |

### shortest path tree


:::

## 第4題：隔出最多的水

### 解題思路

用雙指針去慢慢往內走
中途一直把短的那邊換成下一支
如果有更大的結果就更新
算是貪心+雙指針ㄅ

### 程式碼

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ma=0,i=0,j=height.size()-1;
        while(i<j)
        {
            ma=max(ma, min( height[i], height[j]) * (j-i));
            (height[i] < height[j]) ? i++ : j--;
        }
        return ma;
    }
};

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


### 花費時間

12分鐘

### 完成程度

完全自己解出

## 第5題：跳到最後-V2

### 解題思路

`jt`是跳的次數
`lma`一次跳越裡目前跳越能跳到的最遠的地方
`ma`目前能跳到最遠的地方

切成每次跳越能到的地方，
實作上就是每次去更新能跳去的地方，
如果這次沒跳到尾端，就再跳一次

### 程式碼

class Solution {
public:
    int jump(vector<int>& nums) {
        int jt=0,ma=0,lma=0,i=0;
        while(ma<nums.size()-1)
        {
            jt++;
            lma=0;
            for(;i<=ma;i++)
            {
                lma=max(lma,nums[i]+i);
            }
            ma=max(lma,ma);
        }
        return jt;
    }
};

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


### 花費時間

7分鐘

### 完成程度

完全自己解出

## 第6題：2個城市的面試排程

### 解題思路

我前面大概半小時在試著把`costs`複製之後分別按照A和B排序之後再取出來
結果我後來想想感覺不太對，所以就砍掉了

後來我才想到不能直接打下去，不然太沒有前瞻性(?)了
把`costs`按照CP值(?)排序
A就是選下去的結果的成本去比較B選下去的成本
把選A好一點的放在前面`N`個
後面`N`個是B選下去的

然後我是寫了才知道Leetcode的cmp要寫成static
下次知道ㄌ

### 程式碼

class Solution {
public:

    static bool cmp(vector<int> a,vector<int> b)
    {
        return a[0]-a[1]<b[0]-b[1];
    }

    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(),costs.end(),cmp);
        int n=costs.size()>>1,sum=0,i;
        for(i=0;i<n;i++)
        {
            sum+=costs[i][0];
        }
        for(;i<costs.size();i++)
        {
            sum+=costs[i][1];
        }
        return sum;
    }
};

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


### 花費時間

55分鐘

### 完成程度

完全自己解出

## 第7題 心得

已填