栈解决括号匹配问题
一个字符串中包含小括号、中括号、大括号，判断该字符串中的括号是否匹配
- ()()[]{} 匹配
- ([{()}]) 匹配
- []( 不匹配
- [(]) 不匹配
def check_str(test_str):
tmp_list = []
for item in list(test_str):
if item in ["(", "[", "{"]:#左括号全部入栈
tmp_list.append(item)
else:
if tmp_list:
last = tmp_list.pop()#左括号出栈比较
if item == last:
continue
else:
return False
else:#右括号有剩余
return False
if tmp_list:#左括号有剩余
return False
else:
return True
test_str = "([)]"
print(check_str(test_str))
栈解决迷宫问题
竖直方向为x轴，水平方向y轴，1表示墙，0表示路，起点(1,1)，终点(8,8)。在起点和终点之间找到一条路（不要求最近）
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [
lambda x,y:(x-1,y),#上
lambda x,y:(x,y+1),#右
lambda x,y:(x+1,y),#下
lambda x,y:(x,y-1),#左
]
def solve_maze(x1,y1,x2,y2):
stack = []
stack.append((x1,y1))
maze[x1][y1] = 2 #走过的路标记为2
while stack:
cur_node = stack[-1]
if cur_node == (x2,y2):
print("找到一条路")
print(stack)
return True
for dir_func in dirs:
next_node = dir_func(*cur_node)
if maze[next_node[0]][next_node[1]] == 0:
stack.append(next_node)
maze[next_node[0]][next_node[1]] = 2
break
else:
stack.pop()
else:
print("没路了")
solve_maze(1,1,8,8)
队列解决迷宫问题
广度优先，能找到一条最短的路，如果有多条都是最短该算法只算出其中一条
import queue
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [
lambda x,y:(x-1,y),#上
lambda x,y:(x,y+1),#右
lambda x,y:(x+1,y),#下
lambda x,y:(x,y-1),#左
]
def solve_maze(x1,y1,x2,y2):
node_queue = queue.Queue()
node_queue.put((x1,y1,None))
maze[x1][y1] = 2 #标记走过的路为2
out_nodes = [] #存放出队列的节点
while not node_queue.empty():
cur_node = node_queue.get() #出队列
out_nodes.append(cur_node)
if (cur_node[0],cur_node[1]) == (x2,y2):
break
for dir_func in dirs:
next_node = dir_func(cur_node[0],cur_node[1])
if maze[next_node[0]][next_node[1]] == 0:
node_queue.put((next_node[0], next_node[1], len(out_nodes) - 1))
maze[next_node[0]][next_node[1]] = 2 #标记走过的路为2
else:#队列空，没有路
print("没有路")
return False
#拼接所有路径
res_nodes = []
last_node = out_nodes[-1]
while last_node[2] != None:
res_nodes.append((last_node[0],last_node[1]))
last_node = out_nodes[last_node[2]]
print("找到一条路")
print(res_nodes[::-1])
return True
solve_maze(1,1,8,8)
