在我們開始進入解題之前這邊有一些解題的小技巧想跟大家分享，對了~這些方法是Python內建的Library，所以其實寫法上比較固定，沒有甚麼特別的。如果讀者用的是其他語言，可以找看看相對應的語言的那個功能要怎麼做呦。

Array

在python裡面使用Array我們用一個中括號就可以了，如果我們要加值進去就用append()

arr = []
arr.append(1)

另外假如我們一開始想要初始化，一個長度為10的Array裡頭都是0，我們可以這樣寫

arr = [0]*10

如果要宣告一個2D Array這個比較特別大家可以記一下啦，以下例子會建立高為5，寬為10的2D Array。

weight, height= 10, 5
matrix = [[0 for x in range(weight)] for y in range(height)]

HashMap/Set

HashMap在python裡我們用大括號來表示，如果要用key去取value就要這樣寫

hash_map={
    'a': 1,
    'b': 2,
}
# get the value of key 'a'
hash_map['a']

如果要增加新的key/value，就會是這樣。

hash_map={
    'a': 1,
    'b': 2,
}
# add new key/val pair
hash_map['c'] = 3

有時候如果我們要計算一個Array裡面元素出現的個數，我們會這樣寫，原因是如果count裡面沒有那個對應的key，我們在count[element]取值時會報錯。

arr = [1,1,1,2,2,2,2,2,3]
count={}
for element in arr:
    if element in count:
        count[element]+=1
    else:
        count[element] = 1

如果覺得太麻煩，其實可以用內建的Counter來撰寫就可以囉

from collections import Counter
arr = [1,1,1,2,2,2,2,2,3]
count = Counter(arr)

Set的話也是用內建的Library就可以，新增或刪除分別是add, remove,看值有沒有在就用in

my_set = set()
my_set.add(1)
my_set.remove(1)

1 in my_set

LinkedList

LinkedList的話題目會幫我們建好Node class所以只需要記得用node.next取得下一個節點的位子就好。

# Go to next node
node = node.next

Tree

樹的話跟LinkedList一樣題目都會幫你建好Node Class不用太擔心，只需要知道node.left跟node.right還有base case是if not node即可。

# left node
left = node.left
# right node
right = node.right
# base case
if not node:
    return

Heap

在python裡heap的Library是heapq，要把Array轉成heap是利用heapify()，取值用heappop()，塞值用heappush()，這邊用法比較特別大家要注意一下喔。

arr = [5,7,8,6,3,1,4]
# heapify
heapq.heapify(arr)
# heap push
heapq.heappush(arr, 9)
# heap pop
heapq.heappop(heap)

還有Python的Heap預設是min heap如果要使用max heap，只要把值*-1在append就好了，取出來的時候記得也要*-1喔。

# max heap push
num = 9
heapq.heappush(arr, -1*num)
# max heap pop
num = -1*heapq.heappop(heap)

Stack/Queue

Stack的話在Python裡我們一樣用中括號來宣告即可(跟Array一樣)，有append跟pop，peek的話就用[-1]，在python裡array[-1]就是從後面數來第一個的意思。
Queue我們會利用deque模組，一樣是內建的，我們會用append，pop的話記得要用popleft這個function喔！

# Stack
stack = []
# stack append
stack.append(1)
stack.append(2)
# stack pop
stack.pop()
# stack peek
stack[-1]

# Queue
from collections import deque
queue = deque()
# queue append
queue.append(1)
queue.append(2)
# queue pop
queue.popleft()
# queue peek
queue[0]

Sort

另外Sort的話非常簡單，我們在Array後面打.sort()就可以，如果今天我們Array裡的element是有兩個值，我們想用第二個值當key來排序，就要用Lambda來寫。

# sort single element array
arr = [8,4,5,3,9,5,10]
arr.sort()

# sort by second element
a = [[1,10],[5,7],[9,5], [6,6]]
a.sort(key=lambda l:l[1])

最大最小值

有時候我們如果要取得一個最大的值，可以用math.inf，要最小的話加一個-號變成-math.inf就可以囉。

# max val
math.inf
#min val
-math.inf

淺談空間複雜度

我故意把空間複雜度留到這個單元才來跟大家介紹的原因是，如果大家之前有理解時間複雜度，那空間複雜度學起來會超級簡單的。
其實空間複雜度跟時間複雜度的算法跟觀念是一模一樣的，差別在於，空間複雜度所探討的是「最多會耗費多少記憶體空間」？如果你的演算法需要額外生成一個Array並且這個Array的長度是依照你的input有線性成長的，那我們就會說空間複雜度是O(n)，相同的如果我們的演算法永遠都只有一個或2個pointer，不管input多大，他始終還是兩個pointer，那我們的空間複雜度就是O(1)，最後要記得，遞迴的空間複雜度不可能是O(1)，因為一定會有Call Stack拉！

時間跟空間複雜度其實很多時候是一個需要權衡的議題，很多時候我們可以用空間來換取更好的時間，這部分我們會在解題的時候讓大家體會啦。

解題心法

這邊我要先聲明，剛開始在解題的時候是很難一下子就知道要怎麼解的，當然隨著題數的慢慢增加，對於一看到問題的直接反應會更快，這邊提供一個通用的Pattern讓大家可以照著這樣的思考去看一個題目。

• Step 1 : Brute Force，也就是我們俗稱的暴力破解法，遇到一個問題的時候先想想怎麼用暴力破解法去實作。
• Step 2: 從暴力破解法中找出「一直重複」或是「最花時間」的步驟。有時候暴力破解法之所以會慢就是因為他不斷重複一些相同的運算，或是用了一些比較花時間的資料結構去處理比較不適合的問題。
• Step 3: 把問題反過來想。有時候Step1跟Step2都找不到好的解答時不彷把問題「從後面往前看」，或是換個角度看，會有不一樣的想法喔。
• Step 4: 想不出來就看解答吧，沒關係的，實力都是累積出來的。如果真的都想不出來，就去看看大神是怎麼解的吧，記得學起來就是自己的，就算是看別人的，只要我們有本事學起來，都是自己的知識財富呦。

結論

到今天終於把演算法跟資料結構還有一些解題會用到的技巧都講解完了，明天就會開始解題啦，如果讀者在這過程中有遇到甚麼問題，可以往回看然後多想一想，這樣會有不同的收穫喔！另外，我選擇的題目是我覺得蠻「有趣」又好懂的，我認為這樣是最快可以讓大家熟悉資料結構及演算法的方式，所以如果大家覺得想要有更多的挑戰，可以自己再去找更難的題目來做看看呦！