---
# System prepended metadata

title: 一、課程成果說明

---


# 一、課程成果說明
# 二、心得與省思 

### 陣列　
以往學到陣列以前，常常會使用大量變數來記錄資料，導致常常資料混亂、找不到所需的資料或是程式過於複雜，不易閱讀。學習陣列的操作後可以應用到許多的題目，不但可以存放大量的資料，更可以透過迴圈的方式將每個資料依依存取，不需因設置大量變數而花費許久時間找尋，導致時間白白浪費。

### 雜湊表

##可寫題目Two SUm的感想以及與以往不同的解決方式 eg:一班陣列使用On*2、可用雜湊縮寫On

### 佇列　

### 鏈結串列　

### 樹
最常應用在根目錄資料夾，子資料夾，網頁的DOM結構等
### 二元樹

### 二元搜尋樹

# 三、心路歷程
##學這門課的動機、心得感想、遇到的挫折、如何突破窘境、以及對未來德展望

# 四、前言

為了能進一步的優化程式碼，同時降低執行程式所需的時間，更有效率的解決問題，因而學習資料結構與演算法。在學習的途中也能訓邏輯思考能力，面對程式時能多方面地探討問題，不再是單方面的「暴力」解決問題。




# 五、大綱

1. 資料結構：「儲存資料的結構。」
基本資料結構大致分為：陣列(Array)、鏈表(Linked List)、哈希表(Hash Table)、推疊(Stack)、佇列(Queue)、樹(Tree)、二元樹搜尋樹。
  1. 演算法：「解決一道問題的方法或步驟。」
例如：廣度優先(BFS)以及深度優先(DFS)。每個方法不同，因此需視情況來選擇，才能達到較佳的程式效率。
4. 時間複雜度有log時，在電腦中常常是以2為底。
  1. 結論：因此選擇合適資料結構以及演算法能將問題更有效率的解決。

# 六、課程實作
　目錄：
 （一）、陣列　
    （二）、雜湊表　
    （三）、佇列　
    （四）、鏈結串列
    （五）、樹
    （六）、二元樹
    （七）、二元搜尋樹
## （一）、陣列 Array
概述：
 1. 「連續性」儲存於記憶體位置的一種資料結構。
 1. 在Python中可用串列(List)進行設計。
 1. 讀取或修改時間複雜度為O(1)
 1. 刪除則是O(n)，因需移動陣列。
 
### LeetCode [2656. Maximum Sun With Exactly K Elements](https://leetcode.com/problems/maximum-sum-with-exactly-k-elements/description/)
題目敘述： 
給定一個nums陣列、數字K，每次從陣列中取出最大值(相同則取後者)計算總和並將取出的數+1放回陣列，一共執行K次此操作。

程式碼：
```python!=
class Solution:
    def maximizeSum(self, nums: List[int], k: int) -> int:
        scores = 0
        for i in range(k):
            tmp = max(nums)
            scores+=tmp
            nums.append(tmp+1)
        return scores
```
程式說明：
雖然題目敘述有說移除陣列並加入新數字，但因每次取數為最大且+1放回去，因此放回去的數依然是最大，不會影響答案。
先設置一個變數存放總和，使用一個迴圈執行k次，每次從陣列中找出最大值暫存tmp，接著加進scores，並把tmp+1存在陣列中。
另外此題目也許有更快的解法（數學解），但練習陣列操作更為重要。
## （二）、雜湊表 Hast Table
概述：
1. 可以使平均時間複雜度Ｏ（１）情況下，快速查找資料
2. 當輸入特定的關鍵字時，會回傳對應的資料
如：輸入某人名字時，回傳其綽號或其他資料。
3. key為鍵值即輸入的關鍵字，接著透過其對應的索引值（index）連結到儲存資料的地方（value）。鍵值可以對應到不同的index，但index只能對應到自己的value。

![你的段落文字](https://hackmd.io/_uploads/rk4AnOVtyl.png)

4. 雜湊表的運作是將鍵值透過雜湊函數換算成索引值，最後對應到資料。
    (1)雜湊函數有許多的種類，如使用鍵值位元運算、string轉ASCII、除法餘數哈希等等
    (2)資訊安全與哈希函數息息相關，將密碼透過哈希函數轉換乘亂數，以達到防止密碼過於容易被獲取。
5. 雜湊表可能會遇到碰撞的問題，如不同的鍵值卻對應到了相同的索引值。通常有兩種解決方法
    (1) 使用不同的雜湊函數再執行一次
    (2) 開放定指法:讓某個碰撞的鍵值往下對應新的index，若還是碰撞就接著找下一個index，如此循環。

雜湊表實作：
```python!=
hash_table ={}
hash_table["陳小名"]="台南市"
hash_table["黃小名"]="台北市"
hash_table["王小名"]="高雄市"
#建立雜湊表

print(hash_table)#印出雜湊表

del hash_table["陳小名"]#刪除雜湊表中的陳小名鍵值

if "陳小名" in hash_table:#確認是否刪除
    print("exist")
else:
    print("no exist")
```
運用雜湊表計算字母的出現次數:
```python!=
a="acbTTQWSd" #建立需要計算次數的字串

ht={}#建立雜湊

for i in a:#將字串丟入i，如果i出現過雜湊就+1，否則給予初始值1。
    if i in ht:
        ht[i]+=1
    elif i not in ht:
        ht[i]=1
        
        
print(ht.items())#查看每個字母對應的vale(出現次數)
```
### LeetCode [217. Contains Duplicate](https://leetcode.com/problems/contains-duplicate/description/)
題目敘述：
給定一個數字陣列nums，如果陣列中任意數字出現兩次以上回傳true，否則false。
程式碼：
```python!=
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        ht={}
        for i in nums:
            if i in ht:
                ht[i]+=1
            elif i not in ht:
                ht[i]=1
        for i in nums:
            if ht[i]>=2:
                return True
        return False
```
程式說明：
當計算陣列的出現的字數時，可以建立一個雜湊表，將未出現過的數字存入並對應值設1。首先使用迴圈將陣列全部跑過一遍，如果存在就+1，不存在就設為1。最後再跑一次迴圈，依依檢查如果有出現次數>=2就回傳True，否則False。
特別的是這樣想法對於筆者來說寫起來直觀清楚，如果將第二個迴圈刪除，當判斷存在是順手判斷是否>=2，則可以優化時間複雜度，從46ms縮為11ms。
![未命名設計 (1)](https://hackmd.io/_uploads/rJMcOsBF1g.png)

### LeeCode [1. Two Sum](https://leetcode.com/problems/two-sum/description/)
題目敘述﹔
給予一個陣列nums、數字target，如果陣列中兩個數相加會等於target，則回傳那兩數在陣列中的index位置。

程式碼：
```python!=
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ht={}
        remain=0
        for index,num in enumerate(nums):
            remain=target-num
            if remain in ht:
                return [ht[remain],index]
            else:
                ht[num]=index
        return None

```
程式說明：
首先建立一個雜湊表和剩餘數(變數remain)，接著走訪一個陣列，可以使用函數enumerate將陣列中的數值與其index位置分別傳至變數「num」和「index」。每次開始時將target和取出的num相減得到remain，判斷remain是否出現在雜湊表中，如果有則回傳remain所對應的值以及num位於nums的index。而如果沒有則將此num設為鍵值，其索引值設為對應的值。如此一來便可邊走訪邊建立。

## （三）、佇列 Queue


 ![資料](https://hackmd.io/_uploads/rJopFGQ8a.png)
 概述：
 1. 佇列是將先進來的資料放在前面(Front)，相對後面放在後端(Rear)。
 1. 佇列在做取出資料時依照 「先進先出」 的概念去做取出。
 1. 佇列的抽象名詞 「enqueue」、「dequeue」 前者是指將資料放進佇列的動作；後者是將資料從佇列取出的動作。
 1. 通常佇列有兩種製作方式，第一個是使用陣列(list) 以及deque模組(Python內建模組)，它是由雙向鏈結實作而成的。

兩種不同實作方式的==時間複雜度比較==：

![資料 (1)](https://hackmd.io/_uploads/SkKuDNQUa.png)

1. 陣列刪除資料因為「先進先出」的概念，且是連續的記憶體空間，因此需要移動n-1筆資料往前，所以時間複雜度O(n)。
1. 陣列較方便但慢；佇列較快但不方便。兩者都可以使用，依據情境不同去做選擇。


使用deque實作佇列:
```python!=
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)

item = queue[1]
print(item) #輸出2

item = queue.popleft() #取最前端

print(item) #輸出1
```

使用陣列實作佇列:
```python!=
queue = []
queue.append(1)
queue.append(2)
queue.append(3)

item = queue.pop(0) #取出index[0]的位置回傳

print(item,queue) #輸出1跟[2,3]
```

### LeetCode [933. Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/description/)
題目敘述：回傳每一次呼叫時前3000毫秒，呼叫此函數的次數，包括每次呼叫。
```python!=
class RecentCounter:

    def __init__(self):
        self.queue=deque()

    def ping(self, t: int) -> int:
        queue=self.queue
        start=t-3000
        queue.append(t)
        while (queue and queue[0]<start):
            queue.popleft()
        return len(queue)
```
程式說明：將每次呼叫的時間點放入佇列，設置開始時距離3000毫秒，如果queue放入的時間已經超過3000毫秒範圍且佇列不為空，就將它移除佇列，最後回傳佇列長度，即為本次呼叫與其他次呼叫，不相差3000毫秒的總次數。

## （四）、鏈結串列 Lined List

![資料 (1)](https://hackmd.io/_uploads/r1YLKECXT.png)
概述：鏈結串列以節點(Node)為單位，在節點1中開頭存放著一個任何型態的資料，而指標指向下一個記憶體位置(也就是節點2中的資料)。舉例來說假設節點1的資料在記憶體位置中01，節點2的資料在記憶體位置中是04，因此節點1中的指標設為04，如此就可以連結到節點2。

 補充：鏈結與陣列優缺點：
 1. 陣列：「陣列是存放在連續的記憶體空間」優點在於使用index查找資料較為快速，相對的缺點是新增或刪除時較為慢，需要移動整個陣列，時間複雜度O(n)；
 1. 鏈結：「具有跳躍性的，記憶體位置不連續」，優點在於新增或刪除較為快速，資料是分散的因此不需要移動鏈結，時間複雜度O(1)，缺點則是在查找資料時，因為不知道一資料所存放記憶體位置，會造成需要從頭開始找，節點1指標往節點2，直到找到為止，因此時間複雜度O(n)。

建立鏈結：
``` python!=
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
        #宣告節點

node1=ListNode(1)
node2=ListNode(2)
node3=ListNode(3)
#創建三個節點，節點1的值為1，節點2為2...以此類推，
#此時彼此為獨立的

node1.next=node2 #將node2節點放入node1的指標
node2.next=node3 #將node2節點放入node1的指標

head=node1 #共用同個鏈結，避免忘記node1建立的鏈結，為新鏈結。

current_node=head 
#建立變動的鏈結，直到這行以前Leetcode都會給予，為避免動到head。
```

走訪鏈結：

``` python!
while current_node: #當current_node不等於None(空值)時條件成立，進入迴圈
    print(current_node.val) #印出當前current_node的值
    current_node=current_node.next #將當前current_node更新下一個鏈結
```
![資料 (2)](https://hackmd.io/_uploads/Syz-Fr0mT.png)

查找鏈結：
```python!=
while current_node: 
#當current_node不等於None(空值)時條件成立，進入迴圈
    if current_node.val ==2: 
#直到找出current_node值=2
        print("2 in current_node") 
        break
    current_node=current_node.next 
#將當前current_node更新下一個鏈結
```
插入鏈結：
```python!=
while current_node:
    
    if current_node.val==2: #選擇位置
        
        new_node=ListNode(4) #建立新節點
        new_node.next = current_node.next 
#將節點下個位置設為current節點的下個位置

        current_node.next=new_node 
#將current節點的下個位置變為new_node
        break
    
    current_node=current_node.next 
#current_node更新下一個鏈結
```

刪除鏈結：
```python!=

previous = None #保存先前的節點

while current_node:
    
    if current_node.val==2: 
        #選擇位置 遺忘值為2的節點(節點2)，讓前一個與後一個連接
        
        if previous: #判斷是不是首節點
            
            previous.next=current_node.next #此時previous=None，
            #使previous下一個(head)的位置變成，current的下一個位置(節點2)
            
        else:
            
            head=current_node.next #直接讓head變為current的下個節點，變相刪除
        break
        
    previous=current_node #previous變成目前current，使previous保持上一個
    
    current_node=current_node.next #current_node更新下一個鏈結
```
### LeedCode [203\. Remove Linked List Elements](https://leetcode.com/problems/remove-linked-list-elements/)
題目敘述：給予一個value，刪除鏈結中具有相同value的節點，可能不只一個。
程式碼：
```python!=
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        prev=None
        curr=head
        
        while curr:
            if curr.val ==val:
                if prev:
                    prev.next=curr.next
                else:
                    head=curr.next
                curr=curr.next

            else:
                prev=curr
                curr=curr.next


        return head
```
程式說明：當curr不指向空時，鏈結會一直走訪。首先可能會遇到首節點刪除的問題，因此一開始curr指向head首節點，而prev指向空。當curr在遍歷時遇到相同值，且如果prev指向空，說明目前位於首節點。則直接將head=curr.next，curr往前推進，若非首節點則將pre下個節點設置為curr的下個節點，即跳過了當前節點。如果沒有相同則prev跟curr一起推進。

## （五）、樹
![你的段落文字](https://hackmd.io/_uploads/HJfmRvOK1x.png)

概述：
1. 一種非線性的資料結構，常利用節點儲存資料。可以有很多個子節點，但鏈結串列只有一個，不可有迴路，兩點之間只會有一個邊。
2. 如上圖，節點表示樹中存放的資料；分支度表示其有幾個子節點；最上層的1因為沒有節點指向它，所以稱之為根節點，相對的節點沒有子節點稱為葉節點。
3. 一的節點具有子節點，針對這部分則稱該節點為父節點，往下連結的稱為子節點，有相同父節點則稱為兄弟節點。
4. 從樹根到最深葉子高度稱為樹的深度。具有相同水平層級則為同一階層。如圖編號1為在第一階層；2和3第二階層；4、5、6、7位於第三階層。
5. 可以使用鏈結或陣列來實作樹。

利用鏈結串列實作樹：
```python!=
class TreeNode:
    def __init__(self,value): #初始化數值
        self.value=value
        self.children=[]
        
    def add_child(self,child_node): #新增子節點函數
       self.children.append(child_node) #將當前節點加入至子節點

root = TreeNode("1")#建立節點的資料
child2=TreeNode("2")
child3=TreeNode("3")

root.add_child(child2)#串聯根節點的子節點2、3
root.add_child(child3)

child2_1=TreeNode("4")
child2_2=TreeNode("5")

child2.add_child(child2_1)#串聯2節點的子節點4、5
child2.add_child(child2_2)

child3_1=TreeNode("6")
child3_2=TreeNode("7")

child3.add_child(child3_1)#串聯根節點的子節點6、7
child3.add_child(child3_2)
```
### LeetCode [590\. N-ary Tree Postorder Traversal](https://leetcode.com/problems/n-ary-tree-postorder-traversal/)
題目敘述：給予一棵樹，從根節點開始走訪，從左邊開始走，走到底後把數字依序輸出。![image](https://hackmd.io/_uploads/HyQOE_uYJx.png)
程式碼：
```python!=
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        v=[]
        def dfs(node):
            if not node:
                return
            for children in node.children:
                dfs(children)
            v.append(node.val)
        dfs(root)
        return v
```
程式說明：會用到DFS和走訪二元樹的概念，要特別注意的是二元樹只要加入左右節點，但一般樹可能有多個節點，因此需要迴圈走訪每個節點。建立一個陣列來記錄走訪過的節點，利用DFS的特性遞迴往下走訪，因為有多的分支，需要迴圈要將節點的所有節點進入dfs，之後每走訪就新增節點至v陣列裡。終止條件則是沒有節點時就return。最後只要把root丟入dfs中，最後回傳v陣列就可以了。
## （六）、二元樹
概述：
1. 與一般樹不同的是，每個節點最多有兩個子節點，且有序從左至右填入節點。
2. BFS遍歷二元樹時將根節點存放佇列中，佇列不為空時訪問、取用最前端節點，並將其子節點放入佇列最尾端。不斷重複直到佇列為空。
3. DFS遍歷二元樹時將根節點存放遞迴式中，如果節點為空則return，遞迴左右子節點，如此往下直到空，則再回頭往分支子節點往下遞迴，如此重複。

建立二元樹：
```python!=
class TreeNode:
    
    def __init__(self,value): #初始化數值
        self.val=value
        
        self.left=None
        
        self.right=None
        
root=TreeNode(1)#建立各節點值

node2=TreeNode(2)

node3=TreeNode(3)

node4=TreeNode(4)

node5=TreeNode(5)

node6=TreeNode(6)

node7=TreeNode(7)


root.left=node2#將根節點的左右子節點串聯

root.right=node3


node2.left=node3

node2.right=node4


node3.left=node5

node3.right=node6


```
BFS遍歷二元樹
```python!=

from collections import deque

class TreeNode:
    
    def __init__(self,value): #初始化數值
        
        self.val=value
        
        self.left=None
        
        self.right=None
        
        
root=TreeNode(1)#建立各節點值

node2=TreeNode(2)

node3=TreeNode(3)

node4=TreeNode(4)

node5=TreeNode(5)

node6=TreeNode(6)

node7=TreeNode(7)


root.left=node2#將根節點的左右子節點串聯

root.right=node3

node2.left=node4

node2.right=node5


node3.left=node6

node3.right=node7


queue=deque()

queue.append(root)

v=[]


while queue:
    
    node=queue.popleft()#走訪節點 順手移除最前端
    
    v.append(node.val)#注意要的是節點的值
    
    if node.left:#若不為空，將左子節、右子節點加入queque
        
        queue.append(node.left)
        
    if node.right:
        
        queue.append(node.right)
        
print(v) #將印出1、2、3、4、5、6、7

```

DFS遍歷二元樹：
```python!=
class TreeNode:
    
    def __init__(self,value): #初始化數值
        
        self.val=value
        
        self.left=None
        
        self.right=None
        
        
root=TreeNode(1)#建立各節點值

node2=TreeNode(2)

node3=TreeNode(3)

node4=TreeNode(4)

node5=TreeNode(5)

node6=TreeNode(6)

node7=TreeNode(7)


root.left=node2#將根節點的左右子節點串聯

root.right=node3


node2.left=node4

node2.right=node5


node3.left=node6

node3.right=node7


v=[]


def dfs(node):
    
    if node is None:
        return
    
    v.append(node.val) #將訪問節點值加入陣列中
    
    dfs(node.left)#往左遞迴
    
    dfs(node.right)#往右遞迴
    
dfs(root)

print(v)#走訪順序1 2 4 5 3 6 7

```
### LeetCode Code [102\. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

題目敘述：使用BFS的順序走訪二元樹，每層訪問為一個陣列，最終使用二維陣列存放這些陣列。
程式碼：
```python!=
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        from collections import deque
        if not root:
            return []
        ans=[]
        queue=deque()
        queue.append(root)

        while queue:
            tmp=[]
            level_size=len(queue)

            for i in range(level_size):
                k=queue.popleft()
                tmp.append(k.val)
                if k.left:
                    queue.append(k.left)
                if k.right:
                    queue.append(k.right)
                
            ans.append(tmp)
        return ans
```
程式說明：因為根可能為空所以要先檢查。接著將根放入進入佇列，初始化暫存陣列tmp，並測量當前queue的長度，跑一個迴圈把當前階層的所有節點跑完，注意的是要確認是否節點還有子節點，有的話就加入queue。並把值存入tmp中，然而跑完迴圈時每層子節點都已經加入，因此階層長度會剛好可以跑完下層所有節點。最終每跑完一層將陣列tmp加入到ans陣列中。

## （七）、二元搜尋樹

![你的段落文字 (1)](https://hackmd.io/_uploads/H1nPLYuKyg.png)



概述：
1. 嚴格程度來說，一般樹包括二元樹，二元樹包括二元搜索樹。但二元搜索樹不一定是二元樹。
2. 左子節點小於父節點，右子節點大於父節點。左子樹小於父子樹，右子樹大於父子樹。
3. 查找某個數時，例如找8，8>7左半數皆小於7，所以只要往右邊走。每次都可以砍半找，因此時間複雜度log(n)。

二元搜尋樹建立：
```python!=

from collections import deque

class TreeNode:
    
    def __init__(self,value): #初始化數值
        
        self.val=value
        
        self.left=None
        
        self.right=None
        
        
def insert(root,v):
    
    if root.val==None: #確認節點是否為空，空則可直接插入
        
        root.val=v
        
    elif v<root.val: #如果節點值小於根節點則左邊走
        
        if root.left is None: #如果根節點左子樹為控則插入
            
            root.left=TreeNode(v)
        else:
            
            insert(root.left,v) #否則再做一次遞迴 使它可以插入
            
    else:#如果節點值大於根節點往右
        
        if root.right is None:  #右節點是否為空
            
            root.right=TreeNode(v)
            
        else:
            
            insert(root.right,v)#否則再做一次遞迴
            
    return "OK"

r=TreeNode(7)

insert(r,5)

insert(r,9)

insert(r,3)

insert(r,6)

insert(r,8)

insert(r,10)


#下列為BFS走訪確認樹的建立


queue=deque()

queue.append(r)

v=[]

while queue:
    
    node=queue.popleft()#走訪節點 順手移除最前端
    
    v.append(node.val)#注意要的是節點的值
    
    if node.left:#若不為空，將左子節、右子節點加入queque
        
        queue.append(node.left)
        
    if node.right:
        
        queue.append(node.right)
        
print(v) #將印出7、5、9、3、6、8、10
```
### LeetCode [938\. Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/)

題目敘述：給予一個二元搜尋樹、兩個變數low、high，走訪二元搜尋樹中符號兩數之間的所有數，並且相加。
程式碼：
```python!=
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        from collections import deque
        if not root:
            return
        ans=0
        q=deque()
        q.append(root)
        while q:
            tem=q.popleft()
            if tem.val>=low and tem.val<=high:
                ans+=tem.val
            if tem.left:
                q.append(tem.left)
            if tem.right:
                q.append(tem.right)
        return ans
```
程式說明：使用BFS、佇列走訪二元搜尋樹，如果取出的數字位在題目範圍內就加入到ans，同時檢查左右子節點是否存在，存在的話就加入佇列。