【算法-面试】广度优先遍历bfs专题

本文主要是介绍【算法-面试】广度优先遍历bfs专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. BFS

• 111 二叉树的最小深度
• 725 打开转盘锁
• 773 滑动拼图

2. 题目

【111 二叉树的最小深度】

def minDepth(root):'''给定⼀个⼆叉树，找出其最⼩深度，最⼩深度是从根节点到最近叶⼦节点（没有⼦节点的节点）的最短路径上的节点数量leetcode: 111 二叉树的最小深度input:  [3,9,20,null,nul, 15, 7]3/   \9     20/  \15   7output: 2思路：1.2.3.'''if root is None:return 0q, depth = [root], 1while len(q) != 0:size = len(q)for i in range(size):cur = q[0]q.remove(q[0])if cur.left is None and cur.right is None:return depthif cur.left is not None:q.append(cur.left)if cur.right is not None:q.append(cur.right)depth += 1return depth

【725 打开转盘锁】

def openLock(deadends, target):'''你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。leetcode: 725 打开转盘锁input1: deadends = ["0201","0101","0102","1212","2002"], target = "0202"output1: 6input2:deadends = ["8888"], target = "0009"output2:1思路：1.2.3.'''def plus_one(s, i):new_s = []for ss in s:new_s.append(ss)if new_s[i] == '9':new_s[i] = '0'else:new_s[i] = str(int(new_s[i]) + 1)return "".join(new_s)def minus_one(s, i):new_s = []for ss in s:new_s.append(ss)if new_s[i] == '0':new_s[i] = '9'else:new_s[i] = str(int(new_s[i]) + 1)return "".join(new_s)q = ['0000']visited = set()step = 0while len(q) != 0:size = len(q)for i in range(size):cur = q[0]q.remove(q[0])if cur in deadends:continueif cur == target:return stepfor j in range(4):up = plus_one(cur, j)if up not in visited:q.append(up)visited.add(up)down = minus_one(cur, j)if down not in visited:q.append(down)visited.add(down)step += 1return -1

【773 滑动拼图】

def slidingPuzzle(board):'''在⼀个 2 x 3 的棋盘 board 上有 5 块卡⽚，⽤数字 1~5 来表示 , 以及⼀块空缺⽤ 0 来表示。⼀次「移动」定义为选择 0 与⼀个相邻的数字（上下左右）进⾏交换。进⾏若⼲次移动，使得 board 的结果是 [[1,2,3],[4,5,0]]，则谜板被解开。给出⼀个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能通过移动解开谜板，则返回-1。leetcode: 773  滑动拼图input:board = [[1,2,3],[4,0,5]]output:1input:board = [[1,2,3],[5,4,0]]output:-1input:board = [[4,1,2],[5,0,3]]output:5思路：1.2.3.'''m, n, target = 2, 3, "123450"start_str = ""for i in range(m):for j in range(n):# 转换为一维的start_str += str(board[i][j])neighbor = [[1, 3],[0, 4, 2],[1, 5],[0, 4],[3, 1, 5],[4, 2]]def modify_str(s, i, v):if i >= len(s):print("[warning] can't modify string!")return sa = [_ for _ in s]a[i] = vnew_s = "".join(a)return new_sq, visited, step = [start_str], set(start_str), 0while len(q) != 0:size = len(q)for i in range(size):cur = q[0]q.remove(q[0])if target == cur:print(step)return stepidx = 0for i in range(6):if cur[i] == '0':idx = ibreakfor j in neighbor[idx]:before, after = cur[i], cur[j]new_board = modify_str(cur, i, after)new_board = modify_str(new_board, j, before)if new_board not in visited:q.append(new_board)visited.add(new_board)step += 1print(-1)return -1

【测试例】

if __name__ == "__main__":# print(openLock(["0201", "0101", "0102", "1212", "2002"], "0202"))# print(openLock(["8888"], '0009'))slidingPuzzle([[1,2,3],[4,0,5]])slidingPuzzle( [[1,2,3],[5,4,0]])slidingPuzzle([[4,1,2],[5,0,3]])

这篇关于【算法-面试】广度优先遍历bfs专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---