---
# System prepended metadata

title: 演算法導論 HW6

---

# 演算法導論 HW6
https://hackmd.io/@wang1234/rJxZfYKM2
## 第1題: Huffman Code
![](https://i.imgur.com/IaqRwRK.png)
    
<font color="Blue">※ Huffman code:</font>
    A : 0110 &emsp;&emsp;&emsp; B : 00 &emsp;&emsp;&emsp; C : 0111 
    D : 010 &emsp; &emsp; &emsp; E : 110&emsp;&emsp;&emsp;F : 10 &emsp;&emsp;&emsp; G : 111
    
<font color="Blue">※ 解碼 : 110 &emsp; 0110 &emsp; 111</font>
&emsp; &emsp; &emsp;⇒&emsp;E &emsp; &emsp; A &emsp; &emsp; G

## 第2題：隔出最多的水
[11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
<font color="Black">
解題思路:
> 使用Two Pointers,在初始時分別指向list的頭尾
> 變數water用於存水量,如果有算出更多水量時,更新water
> 當左指標(finger_l)小於右指標(finger_r)時
> 在每次迴圈更換高度較小的隔板,將其向內限縮
> (我的寫法中只判斷左隔板是否高過右隔板,否則就都更換右隔板)
</font>
```python=
class Solution:
    def maxArea(self, height: List[int]) -> int:
        finger_l,finger_r=0,len(height)-1
        water=0
        while finger_l<finger_r:
            temp_w=min(height[finger_l],height[finger_r])*(finger_r-finger_l)
            if temp_w>water:
                water=temp_w
            if height[finger_l]<height[finger_r]:
                finger_l+=1
            else:
                finger_r-=1
        return water
```
![](https://i.imgur.com/Zp4zYdt.png)
花60分鐘，參考:
* [LeetCode: 11-Container With Most Water 解題紀錄](https://clay-atlas.com/blog/2021/01/15/leetcode-11-container-with-most-water-%E8%A7%A3%E9%A1%8C%E7%B4%80%E9%8C%84/)

## 第3題：跳到最後-V2
[45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)
解題思路:
![](https://i.imgur.com/VORO4NR.jpg)
```python=
class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums)<=1 :
            return 0
        x=0
        c=1
        while x<len(nums)-1:
            temp=0
            if x+nums[x]>=len(nums)-1:
                return c
            for i in range(x+1,x+nums[x]+1):
                if i+nums[i]>temp:
                    temp=i+nums[i]
                    x=i
            c+=1
        return c
```
![](https://i.imgur.com/l4hQbT0.png)
花60分鐘，完全靠自己

## 心得
作業寫起來有種腦袋不夠用的感覺，尤其程式題的第一題，如同參考資料的作者一樣，我一開始選擇歷遍所有可能的隔板組合，然後就遇到Time Limit Exceeded，而後一通胡搞瞎搞，嘗試尋找其它方式，直至最後灰頭土臉的參考別人的想法