.jpeg)
經過這麼久的努力leetcode初級基礎題目我們已經走過一輪了，但我們一直沒進一步認識資料結構與演算法，我想在這暫停一下，先來理解基礎結構，之後的題目會比較好上手。
LinkedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class SingleLinkedList:
def __init__(self):
self.head = None
self.tail = None
return
def add_list_item(self, item):
if not isinstance(item, ListNode):
item = ListNode(item)
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
list1 = SingleLinkedList()
list1.add_list_item(1)
list1.add_list_item(2)
list1.add_list_item(3)
list1.add_list_item(4)
list1.add_list_item(5)
while list1:
if list1.head != None:
print(list1.head.val)
list1.head = list1.head.next
else: break
# 1->2->3->4->5
|
ListNode結構就是一個值(val)跟一個鏈結(next)指到下個node。
有點像區塊鏈的結構(也有個鏈)，但區塊鏈的鏈是之前節點的雜湊，內容也複雜得多。上面說明Python的寫法，也說明如何寫一個簡單的單向串列加val操作。
StackAndQueue
1
2
3
4
5
6
7
8
9
| list = []
list.append(1)
list.append(2)
list.append(3)
Stack: [].pop()
# [] <->
Queue: [].pop(0)
# <- 0 [] <-
|
Stack, Queue結構就是一個列表[]。
不一樣的是，Stack是先進後出，Queue是先進先出(所以pop(0)表示從頭開始取出。
TreeAndGraphs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insertLeft(self, val):
if self.left == None:
self.left = TreeNode(val)
else:
self.left.insertLeft(val)
def insertRight(self, val):
if self.right == None:
self.right = TreeNode(val)
else:
self.right.insertRight(val)
sampleTree = TreeNode(1)
sampleTree.insertLeft(2)
sampleTree.insertRight(3)
sampleTree.right.insertLeft(4)
sampleTree.right.insertRight(5)
# 1
# / \
# 2 3
# / \
# 4 5
|
Tree的結構跟LinkedList差不多，但next分成左右2個。
上面說明如何添加節點與子樹
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| class Vertex:
def __init__(self, node):
self._id = node
self._adjacent = {} # dict: key = neighbor, value = weight
def get_id(self):
return self._id
def set_neighbor_weight(self, neighbor, weight=0):
self._adjacent[neighbor] = weight
def get_weight(self, neighbor):
return self._adjacent[neighbor]
def get_neighbors(self):
return self._adjacent.keys()
def get_degree_centrality(self):
return len(self._adjacent)
def get_weighted_degree_centrality(self):
return sum(self._adjacent.values())
class Graph:
def __init__(self):
self._vertDict = {} # key = node id, value = Vertex
def __iter__(self):
return iter(self._vertDict.values())
def add_vertex(self, node):
if node in self._vertDict:
return self._vertDict[node]
else:
vertNew = Vertex(node)
self._vertDict[node] = vertNew
return vertNew
def get_vertex(self, node):
return self._vertDict[node] if node in self._vertDict else None
def get_vertices(self):
return self._vertDict.keys()
def get_count_vertices(self):
return len(self._vertDict)
def get_count_edges(self):
count = 0
for vert in self._vertDict.values():
count += vert.get_degree_centrality()
return count
def add_edge(self, frm, to, w=0):
self.add_vertex(frm)
self.add_vertex(to)
self._vertDict[frm].set_neighbor_weight(self._vertDict[to], w)
|
由多個節點(Vertex)組成並用邊(Edge)連接的就可以稱做是一個Graph，邊也可以有權重。
Algorithms
常見的搜尋，排序要掌握好，還有興趣就參考這個吧。