# 一、課程成果說明
# 二、心得與省思
### 陣列
以往學到陣列以前，常常會使用大量變數來記錄資料，導致常常資料混亂、找不到所需的資料或是程式過於複雜，不易閱讀。學習陣列的操作後可以應用到許多的題目，不但可以存放大量的資料，更可以透過迴圈的方式將每個資料依依存取，不需因設置大量變數而花費許久時間找尋，導致時間白白浪費。
### 雜湊表
##可寫題目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。
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。
### 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
概述：
1. 佇列是將先進來的資料放在前面(Front)，相對後面放在後端(Rear)。
1. 佇列在做取出資料時依照 「先進先出」 的概念去做取出。
1. 佇列的抽象名詞 「enqueue」、「dequeue」 前者是指將資料放進佇列的動作；後者是將資料從佇列取出的動作。
1. 通常佇列有兩種製作方式，第一個是使用陣列(list) 以及deque模組(Python內建模組)，它是由雙向鏈結實作而成的。
兩種不同實作方式的==時間複雜度比較==：
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
概述：鏈結串列以節點(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更新下一個鏈結
```
查找鏈結：
```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一起推進。
## （五）、樹
概述：
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/)
題目敘述：給予一棵樹，從根節點開始走訪，從左邊開始走，走到底後把數字依序輸出。
程式碼：
```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. 嚴格程度來說，一般樹包括二元樹，二元樹包括二元搜索樹。但二元搜索樹不一定是二元樹。
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，同時檢查左右子節點是否存在，存在的話就加入佇列。
Sign in with Wallet
Connect another wallet