---
# System prepended metadata

title: '第1題: Huffman Code'

---

# 第1題: Huffman Code
頻率加總是40
然後先把各頻率由小到大排列,每次最小的2個可以合成一個暫時數,之後暫時數加
到對列中繼續重複步驟,最後會生成二元樹
![](https://i.imgur.com/cg1Km4B.jpg)


A:0110
B:00
C:0111
D:010
E:110
F:10
G:111
# 第2題: 隔出最多的水
1小時,自己完成,其實原本也嘗試過只用一次while,但一直卡在50幾筆,最後只能用稍微暴力一點的,思路就是從右邊往內縮時可以直接跳過比當前flag還小的,而佐內縮時也是
![](https://i.imgur.com/Fqgkr5E.png)
```
class Solution {
public:
    int maxArea(vector<int>& he) {
            int r=he.size()-1;
            int flg=r;
            int ma=min(he[r],he[0])*r;
            while(r){
                if(he[r]>he[flg]||r==flg){
                flg=r;
                int flag=0;
                ma=max(ma,min(he[r],he[0])*r);
                for(int i=1;i<r;++i){
                    if(he[flag]>=he[i]){continue;}
                    else{
                        flag=i;
                        ma=max(ma,min(he[r],he[i])*(r-i));
                    }
                }
                }

                --r;
            }
            return ma;
    }
};
```
# 第3題：跳到最後-V2
10分鐘,自己完成,這題貪心的使用方式比上一題簡單很多了,由後往前跳,可以用貪心省去更新點時所需遍歷的次數,跟dijistra路徑用的方式差不多
```
class Solution {
public:
    int jump(vector<int>& nums) {
         int m=nums.size();
         if(m==1){return 0;}
         
         int cnt=0;
         while(m>1){
        int ma=0;
          for(int j=m-1;j>0;--j){
              if(nums[j-1]+j>=m){ma=max(ma,m-j);}
          }
        m-=ma;
        ++cnt;
         }
         return cnt;
    }
};
```
![](https://i.imgur.com/zL26N8W.png)
# 心得
本周的教學影片學到了最小環的圖形問題,以及完全背包問題的基本核心觀念,以及霍夫曼樹的合併生成方式和貪心算法有關,霍夫曼樹因為上學期有修影像處理導論所以有稍微了解一些,此外老師影片中也有提到單層多對節點演算法(找出所有點22連接且不能交叉或重疊),有最佳解答跟其他方式的解答的詳細解說