Grace Koo's Blog

One thing at a time

0%

DataStructure & Algorithm

Posted on Edited on In
Symbols count in article: 9.9k Reading time ≈ 9 mins.

栈

栈

括号匹配问题

括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LEFT = {'(','[','{'}
RIGHT = {')',']','}'}

def match(expr):
    stack = []
    
    for c in expr:
        if c in LEFT:
            stack.append(c)
        elif c in RIGHT:
            #为空
            if not stack:
                return False
            if not 1 <= ord(c) - ord(stack[-1]) <= 2:
                return False
            stack.pop()
    return not stack

print(match('{{[]}}'))

TRUE

迷宫问题

宫问

最后栈为空说明已经无路可走，如果栈不为空说明找到了一条路径。

为了让表达统一，我们初始化迷宫的时候，将迷宫四周边缘都设成1，这样我们就不用考虑一个点是边界还是非边界点，即所有点都判断上下左右点是否唯一即可。

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
#初始化迷宫
def initMaze():
    maze = [[0] * 7 for _ in range(5 + 2)]
    walls = [(1,3),(2,1),(2,5),(3,3),(3,4),(4,3),(5,4),]
    
    for i in range(5+2):
        maze[i][0] = maze[i][-1] = 1
        maze[0][i] = maze[-1][i] = 1
    
    for i,j in walls:
        maze[i][j] = 1
        
    return maze

#路径选择
def path(maze,start,end):
    
    print(maze)
    
    i,j = start
    e_i,e_j = end
    s = [(i,j)]           #用栈(列表)保存路径节点
    maze[i][j] = 1
    
    while s:         #如果栈不为空,证明还有路可走
        i,j = s[-1]
        if (i,j) == (e_i,e_j):  #如果到达终点
            break
        for di,dj in [(0,-1),(0,1),(-1,0),(1,0)]:    #上下左右四个方向 
            if maze[i+di][j+dj] == 0:       #如果存在为0的可走路径
                maze[i+di][j+di] = 1
                s.append((i+di,j+dj))       #将新的路径加入
                break                       #跳出此循环，执行i,j = s[-1]
        else:                           #如果不存在为0的可走路径
            s.pop()                     #如果发现四周都为1，即无路可走了,执行i,j = s[-1]
   
    return s

maze = initMaze()
print(path(maze,(1,1),(5,5)))

后缀表达式求值

后缀表达式求值

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
"""

后缀表达式求值问题

"""

operators = {
    "+":lambda op1,op2:op1 + op2,
    "-":lambda op1,op2:op1 - op2,
    "*":lambda op1,op2:op1 * op2,
    "/":lambda op1,op2:op1 / op2,
}

#后缀表达式求值，e是表达式
def evalPostfix(e):
    tokens = e.split()
    s = []
    
    for token in tokens:
        if token.isdigit():
            s.append(int(token))
        elif token in operators:
            f = operators[token]
            op2 = s.pop()
            op1 = s.pop()
            s.append(f(op1,op2))

    return s.pop()

print(evalPostfix("2 3 4 * +"))

背包问题

背包问题

背包问题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
"""

背包问题

"""

#t是求解的总重量，w是一个列表，为每个物体的重量，返回值是解

def knapsack(t,w):
    n = len(w)                 #物体的个数
    s = []                     #存放对应物体的下标
    k = 0                      #物体的指针
    
    while s or k < n:   # 当栈里有元素(证明可能还有解)，或者初始指针小于n -- 这两种情况下，解可能存在
        while t > 0 and k < n: 
            if t >= w[k]:      #求解的重量大于某个物体的重量
                s.append(k)    #装入对应物体的指针
                t -= w[k]      #总重减小
            k += 1             #指向下一个物体
        
        if t == 0:             #对应上层while不成立的条件：当t已经为0(也就是已经找到解)
            print(s)
        
        k = s.pop()    #或者指针k已经超出n时，即无解情况，回溯，k指针设为栈顶的元素指针的下一个元素指针
        t += w[k]
        k += 1
        

knapsack(10,[1,8,4,3,5,2])

[0, 2, 3, 5]
[0, 2, 4]
[1, 5]
[3, 4, 5]

队列

队列

Python中队列的接口为：队列接口

Python标准库中的队列deque

队列的方法如下：

队列标准库

屏幕快照 2018-04-06 下午12.34.52

屏幕快照 2018-04-06 下午12.35.04

二项式系数

多项式系数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
杨辉三角形，求解多项式系数问题
"""

from collections import deque
#求解杨辉三角第k层的系数
def yanghui(k): 
    #从第0层，一步一步推算出第k层的系数
    
    q = deque([1]) #第0层系数是1
    
    for i in range(k): # k次推导，i表示当前所在的层
        for _ in range(i): # 第i层需要经过i次出栈操作，才能计算出来结果
            
            q.append(q.popleft() + q[0])
        
        q.append(1)
    
    return list(q)

print(yanghui(4))

[1, 4, 6, 4, 1]

划分无冲突子集

划分无冲突子集

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
"""

划分无冲突子集

"""
from collections import deque

def division(M,n):
    res = []
    q = deque(range(n))
    pre = n
    
    while q:
        cur = q.popleft()
        if pre >= cur:
            res.append([])
            
        for a in res[-1]:
            if M[cur][a]:
                q.append(cur)
                break
        else:
            res[-1].append(cur)
        pre = cur
    return res


N = 9
R = {
    (1,4),(4,8),(1,8),(1,7),
    (8,3),(1,0),(0,5),(1,5),
    (3,4),(5,6),(5,2),(6,2),(6,4)
}
M = [[0] * N for _ in range(N)]
for i,j in R:
    M[i][j] = M[j][i] = 1
    
print(division(M,N))


[[0, 2, 3, 7], [1, 6], [4, 5], [8]]

数字变换(用队列实现广度优先搜索)

数字变换

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
"""

数字变换

"""
from collections import deque

# 将a变成b需要经过几个步骤，使用队列存储转换时的状态
def atob(a,b):
    state_queue = deque([(a,0)]) # 使用元组作为一个元素，第一个值是计算到的数字，第二个值记录现在经过的状态，使用队列记录正在被计算的数字
    checked = {a} # 使用集合记录已经被检查过的数字，要是队列中又出现相同的数字，则不予计算
    
    while True:
        num,state = state_queue.popleft()
        if num == b:
            break   # 跳出循环的条件
        if num < b: # 比b小的数只能通过“+”，“*”操作才有可能得到b，所以忽略“-”操作
            if num * 2 not in checked:
                state_queue.append((num * 2,state + 1))
            if num + 1 not in checked:
                state_queue.append((num + 1,state + 1))
        if num > b:
            if num - 1 not in checked:
                state_queue.append((num - 1,state + 1))
    return state

print("需要通过" + str(atob(3,8)) + "步")  

需要通过2步

二叉树

二叉树

创建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode(object):
    def __init__(self,data,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
    
    def __str__(self):
        return str(self)

A,B,C,D,E,F,G,H,I = [TreeNode(x) for x in "ABCDEFGHI"]
A.left = B
A.right = C
B.right = D
C.left = E
C.right = F
E.left = G
F.left = H
F.right = I

print(C.right.data)

遍历二叉树（前、中、后序）（递归、回溯-栈）

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
class TreeNode(object):
    def __init__(self,data,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
    
    def __str__(self):
        return str(self)

def createTree():
    A,B,C,D,E,F,G,H,I = [TreeNode(x) for x in "ABCDEFGHI"]
    A.left = B
    A.right = C
    B.right = D
    C.left = E
    C.right = F
    E.left = G
    F.left = H
    F.right = I
    return A

# 前序遍历
def preOrder(node):
    if node is None:
        return
    print(node.data)
    preOrder(node.left)
    preOrder(node.right)
    
# 中序遍历
def inOrder(node):
    if node is None:
        return
    inOrder(node.left)
    print(node.data)
    inOrder(node.right)

# 后续遍历
def postOrder(node):
    if node is None:
        return
    postOrder(node.left)
    postOrder(node.right)
    print(node.data)

if __name__ =="__main__":
    root = createTree()
    preOrder(root)
    inOrder(root)
    postOrder(root)

使用递归的开销比较大，下面实现一个迭代版的先序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 回溯的前序遍历
def preOrderIter(root):
    node = root
    s = [] # 使用一个栈存未遍历的节点

    while True:
        # 在节点左子树不为空的情况下，将其左子树一直压栈
        while node:
            print(node.data)
            s.append(node)
            node = node.left
        
        # 如果栈为空，则说明已经遍历完成
        if not s:
            break
        
        # 出栈操作，遍历其右子树
        node = s.pop().right

遍历二叉树（层次遍历 - 队列）

一个节点出队后，才入队它的子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 层次遍历
def levelOrder(root):
    q = deque([root])
    
    # 如果队列不为空
    while q:
        node = q.popleft()
        print(node.data)
        
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

二叉树的深度

采用分而治之的思路，把求一个树的深度转化为它左子树的深度加上右子树的深度。

1
2
3
4
5
6
7
8
# 求二叉树的深度 -- 递归方式
def depth(node):
    if node is None:
        return 0
    dl = depth(node.left)
    dr = depth(node.right)
    
    return max(dl,dr) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
# 求二叉树的深度 -- 非递归方式，层次遍历，只需记录一下当前节点的深度即可
def depth2(root):
    q = deque([(root,1)])
    
    while q:
        node,d = q.popleft()

        if node.left:
            q.append((node.left,d+1))
        if node.right:
            q.append((node.right,d+1))
   
    return d

拷贝二叉树

依旧采用分治的思想，先拷贝左子树，再拷贝右子树，接着拷贝节点。

1
2
3
4
5
6
7
8
9
10
11
def copyTree(node):
    if node is None:
        return None
    
    lt = copyTree(node.left)
    rt = copyTree(node.right)
    
    return TreeNode(node.data,lt,rt)

newTree = copyTree(root)
levelOrder(newTree)

N个节点不同二叉树个数

计算由N个节点，所构成的二叉树的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
def count(n):
    # root : 1
    # left : K [0,n - 1]
    # right : n - 1 - k
    if n == 0 :  # 递归的出口
        return 1
    
    s = 0
    for k in range(n):
        s += count(k) * count(n - 1 - k)
    return s
     
print(count(3))

二叉搜索树

二叉搜索树又作二叉排序树，它可以支持快速的查找。

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
# 对于二叉搜索树的操作

class BinarySearchTree(object):
    def __init__(self):
        self.root = None
    
    def search(self,k):
        node = self.root
        while node and node.data != k:
            if k < node.data:
                node = node.left
            if k > node.data:
                node = node.right
        return node
    
    #同样的实现搜索操作，不过还要返回父节点
    def search_(self,k):
        parent = None
        node = self.root
        while node and node.data != k:
            parent = node
            if k < node.data:
                node = node.left
            if k > node.data:
                node = node.right
        return node,parent
        
    
    def insert(self,k):
        node,parent = self.search_(k)
        # 如果返回到了node的值，说明这个node在节点上存在，则不用执行插入操作
        if node:
            return
        
        # 如果是不存在的，首先构造一个新节点
        node = TreeNode(k)
        
        # 将node插入到parent上
        # 树为空，将整个节点插入到树上，赋为根节点
        if parent is None:
            self.root = node
        elif k < parent.data:
            parent.left = node
        else:
            parent.right = node
        
    
    def delete(self,k):
        pass
    
bst = BinarySearchTree()  
bst.insert(10)
bst.insert(5)
bst.insert(15)
levelOrder(bst.root)

图

图

在Python中使用图

邻接矩阵表示法（有向图、无向图）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 用二维数组表示

# 两个点确定一条边
def Vertical(G,n1,n2):
    Graph[n1][n2] = Graph[n2][n1] = 1
    
N = 5   # 一共5个点
a,b,c,d,e = range(5)
Graph = [[0] * N for _ in range(N)] # 建立一个二维数组保存图
Vertical(Graph,a,b)
print(Graph)

[[0, 1, 0, 0, 0], 
 [1, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0]]

邻接矩阵的缺点：

1.如果图中节点个数很多，边的条数很少，则会浪费资源。

2.访问一个节点的邻接节点，需要遍历一个列表才可以。

邻接集合表示法（有向图和无向图）：

用一个列表存储集合的形式保存节点和边的关系，第一个集合保存节点1，第一个集合保存节点2，以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
"""

邻接集合表示有向图和无向图

"""

# 每一个集合表示对应点相邻的点
G2 = [{b,e},{c,d,e},{b,d},{b,c,e},{a,b,d}]

# 对于b点来说
G2[b]

{2, 3, 4}

邻接列表就是把集合换成列表。

对于带权的边，可以使用邻接字典。

不再使用集合存储，而使用字典存储，其中字典的值表示边的长度。

1
2
3
4
G3 = [{b:4,e:2},{c:5,d:6,e:3}]
G3

[{1: 4, 4: 2}, {2: 5, 3: 6, 4: 3}]

图的深度优先遍历算法DFS

图1

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
G = [
    {1,2,3}, # 0的邻接节点
    {0,4,6}, # 1
    {0,3},   # 2
    {0,2,4}, # 3
    {1,3,5,6},# 4 
    {4,7},   # 5
    {1,4},   # 6
    {5},      # 7
]

# 递归深度优先遍历
def dfs(G,v,visited=set()):
    print(v)
    visited.add(v)
    
    for u in G[v]:
        if u not in visited:
            dfs(G,u,visited)
            
dfs(G,0)
        

# 非递归 --  循环实现深度优先遍历    
def dfsIter(G,v):
    visited = set()
    # 使用栈
    s = [v]
    
    while s:
        u = s.pop()
        
        if u not in visited:
            visited.add(u)
            print(u)
            s.extend(G[u])

dfsIter(G,0)


0
1
4
3
2
5
7
6
0
3
4
6
1
5
7
2

图的广度优先遍历算法BFS

图1

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
G = [
    {1,2,3}, # 0的邻接节点
    {0,4,6}, # 1
    {0,3},   # 2
    {0,2,4}, # 3
    {1,3,5,6},# 4 
    {4,7},   # 5
    {1,4},   # 6
    {5},      # 7
]

from collections import deque

def bfs(G,v):
    # 队列里放未被访问过的元素
    q = deque([v])
    visited = {v}
    
    while q:
        u = q.popleft()
        print(u)
        
        for w in G[u]:
            if w not in visited:
                q.append(w)
                visited.add(w)

bfs(G,0)


0
1
2
3
4
6
5
7

最小生成树算法（Prim算法）

图的生成树：包含所有顶点不能有回环的图。

最小生成树：代价（边的权值）最小的生成树。

最小生成树

Prim

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
G = [
    {1:28,5:10},     # 0
    {0:28,2:16,6:14},# 1
    {1:16,3:12},     # 2
    {2:12,4:22,6:18},# 3
    {3:22,5:25,6:24},# 4
    {0:10,4:25},     # 5
    {1:14,3:18,4:24},# 6
]
import heapq

def prim(G):
    n = len(G)
    v = 0  # 初始顶点设为0
    s = {v}
    
    edges = []
    res = []
    
    for _ in range(n - 1):
        for u,w in G[v].items():
            heapq.heappush(edges,(w,v,u))
            
        while edges:
            w,p,q = heapq.heappop(edges)
            if q not in s:
                s.add(q)
                res.append(((p,q),w))
                v = q
                break
        else:
            raise Exception("not connected gram!")
    
    return res

prim(G)


[((0, 5), 10),
 ((5, 4), 25),
 ((4, 3), 22),
 ((3, 2), 12),
 ((2, 1), 16),
 ((1, 6), 14)]

最短路径算法（Dijkstra算法）

屏幕快照 2018-04-23 下午9.04.07

Dijkstra算法

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
a,b,c,d,e,f = range(6)
G = {
    a:{b:2,c:1,d:4,f:10},
    b:{a:2,c:4,e:3},
    c:{a:1,b:4,d:2,f:8},
    d:{a:4,c:2,e:1},
    e:{b:3,d:1,f:7},
    f:{a:10,c:8,e:7},
}

import heapq

def dijkstra(G,s):
    # D = {},D[c],D[e]
    # 将顶点到其他点的距离初始化为正无穷大
    inf = float('inf')
    D = {v: inf for v in G} # 每个点的距离设成无穷大
    D[s] = 0    # 除了到自己本身，到其余各点距离都是无穷
    P = {}      # 建立父节点的路径
    S = {s}     # 已访问节点
    q = []      # 优先队列
    v = s       # 当前点
    
    # 循环次数
    for _ in range(len(G)-1):
        for u,w in G[v].items():
            d = D[v] + G[u][v]
            if D[u] > d:
                D[u] = d
                P[u] = v
                heapq.heappush(q,(d,u))
        while q:
            _,v = heapq.heappop(q)
            if v not in S:
                S.add(v)
                break
        else:
            break
    
    return D,P

D,P = dijkstra(G,a)
print(D,P)


{0: 0, 1: 2, 2: 1, 3: 3, 4: 4, 5: 9} {1: 0, 2: 0, 3: 2, 4: 3, 5: 2}

拓扑排序算法

拓扑排序算法

首先寻找入度为0的点。添加到队列中，删除其出度的边，再次寻找入度为0的点，添加到队列中。依此类推。

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
G = {
    'C1':['C3','C8'],
    'C2':['C3','C4','C5'],
    'C3':['C4'],
    'C4':['C6','C7'],
    'C5':['C6'],
    'C6':[],
    'C7':[],
    'C8':['C9'],
    'C9':['C7'],
}

def topsort(G):
    indegrees = {v:0 for v in G}
    for al in G.values():
        for v in al:
            indegrees[v] += 1
    q = [v for v in G if indegrees[v] == 0] # 选出所有入度为0的点
    i = 0 # 队头
    while i < len(q):
        for v in G[q[i]]:
            indegrees[v] -= 1
            
            # 判断是否已经入度为0了，若是，则添加到队列中
            if indegrees[v] ==  0:
                q.append(v)
        i += 1
    
    return q if i == len(G) else None # 如果有相互依赖的情况，则返回None
    

topsort(G)


['C1', 'C2', 'C8', 'C3', 'C5', 'C9', 'C4', 'C6', 'C7']

枚举

枚举简介

将可能的解逐一列出。

熄灯问题

动态规划

贪心算法

  • 问题求解时，总是做出在当前来看最好的选择。即，不保证全局最优，仅是在某种意义上的局部最优解。
  • 自顶向下的计算，将原问题归结为子问题。

f(m,n) = f(m-1,n) + f(m,n-1)