python 实现数据结构 lesson 3 栈

假如表达式中允许包含三中括号()、[]、{}，其嵌套顺序是任意的，例如：

正确的格式

错误的格式

编写一个函数，判断一个表达式字符串，括号匹配是否正确

思路

1. 创建一个空栈，用来存储尚未找到的左括号；
2. 便利字符串，遇到左括号则压栈(push)，遇到右括号则出栈(pop)一个左括号进行匹配；
3. 在第二步骤过程中，如果空栈情况下遇到右括号，说明缺少左括号，不匹配；
4. 在第二步骤遍历结束时，栈不为空，说明缺少右括号，不匹配

# coding=utf-8
left = {'{', '[', '('}
right = {'}', ']', ')'}


def match(x):
    stack = []
    for brackets in x:
        if brackets in left:
            stack.append(brackets)
        elif brackets in right:
            if not brackets or not 1 <= ord(brackets) - ord(stack[-1]) <= 2:
                #如果栈为空（'()))'）
                #或是左右括号的ord值差在1和2之间
                return False
            stack.pop()
    return not stack
    #如果栈内没有值，返回True


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

题目

用一个二维数组表示一个简单的迷宫，用0表示通路，用1表示阻断，老鼠在每个点上可以移动相邻的上下左右四个点，设计一个算法，模拟老鼠走迷宫，找到从入口到出口的一条路径。

如图所示

出去的正确线路如图中的红线所示

思路

首先初始化生成一个迷宫，具体情况如下：

1. 用一个栈来记录老鼠从入口到出口的路径
2. 走到某点后，将该点左边压栈，并把该点值置为1，表示走过了；
3. 从临近的四个点中可到达的点中任意选取一个，走到该点；
4. 如果在到达某点后临近的4个点都不走，说明已经走入死胡同，此时退栈，退回一步尝试其他点；
5. 反复执行第二、三、四步骤直到找到出口；

解决代码：

# encoding=utf-8
def initMaze():
    # 初始化迷宫
    maze = [[0] * 7 for _ in range(7)]
    walls = [  # 记录墙的位置
        (1, 3),
        (2, 1), (2, 5),
        (3, 3), (3, 4),
        (4, 2),
        (5, 4)
    ]
    for i in range(7):  # 把迷宫四周设置围墙
        maze[i][0] = maze[i][-1] = 1
        maze[0][i] = maze[-1][i] = 1
    for i, j in walls:  # 把墙的点设置为1
        maze[i][j] = 1
    return maze


def path(maze, start, end):
    i, j = start
    ei, ej = end
    stack = [(i, j)]  # 创建一个stack,让老鼠站到起点位置
    maze[i][j] = 1  # 走过的地方设置为1，表示走过

    while stack:
        i, j = stack[-1]    # 获取老鼠当前位置
        if (i, j) == (ei, ej):
            break
        for (di, dj) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:  # 左右上下是否有出路？
            if maze[i + di][j + dj] == 0:
                stack.append((i + di, j + dj))  # 当前位置进栈
                maze[i + di][j + dj] = 1
                break
        else:
            stack.pop()
    # 退回一步，因为弹出了现有位置，所以再次循环时候，获取老鼠位置时，获取到上一个位置
    return stack


maze1 = initMaze()  # 初始化迷宫
result = path(maze=maze1, start=(1, 1), end=(5, 5))
print(result)

[(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (4, 3), (4, 4), (4, 5), (5, 5)]


Process finished with exit code 0

（C） 背包容量问题

题目

有一个背包能装10kg的物品，现在有6件物品分别为：

编写找出所有能将背包装满的解，如物品1+物品5。

解决代码

#coding=utf-8
def knapsack(t,w):

    #:param t: 背包总容量
    #:param w: 物品重量列表
    stack = []
    n = len(w)
    index = 0#游标指向第一个元素
    while index<n or stack:#栈不为空或者index<n
        while t>0 and index<n:
            if t>=w[index]:
                stack.append(index)
                t -= w[index]
            index += 1#如果背包容量小于w[index]
        if t == 0:#背包装满
            print (stack)
        index = stack.pop()#此时对应t<0的情况，则弹出最后一个进入背包的游标，并继续尝试下一个游标
        t += w[index]
        index += 1
print(knapsack(10,[1,8,4,3,5,2]))