Leetcode刷题——BFS算法

数据结构:采用队列

应用场景:在图中查找最短距离

BFS算法框架

# 计算start到target的最短距离
def BFS(start,target):
    q = collections.deque() # 队列
    visited = set() # 已经走过的节点
    
    q.append(start)
    visited.add(start)
    step = 0
    
    while len(q):
        # 队列中的所有节点向四周扩散
        for i in range(len(q)): # 对当前的队列进行遍历
            cur = q.popleft() # 取出队列头
            if cur == target:
                return step
            for x in cur.adj(): # cur的相邻节点
                if x not in visited:
                    q.append(x)
                    visited.add(x)
        step+=1

双向BFS

使用双向BFS必须知道终点

传统的 BFS 框架就是从起点开始向四周扩散,遇到终点时停止;而双向 BFS 则是从起点和终点同时开始扩散,当两边有交集的时候停止。

1.不再使用队列,使用set判断集合是否有交集

2.while循环的最后交换q1和q2的内容,所以只要默认扩散 q1 就相当于轮流扩散q1和q2

3.whie循环开始的时候,交换q1与q2,使q1为其中短的(比2优化)

4.时间复杂度都一样

二叉树的最小深度(简单)

来自算法小抄

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root == None: return 0
        q = collections.deque()
        visited = set()
        q.append(root)
        visited.add(root)
        step = 0
        while len(q):
            for i in range(len(q)):
                cur = q.popleft()
                if cur.left == cur.right == None: # 已经抵达叶子节点
                    return step+1
                for x in [cur.left,cur.right]:
                    if x == None: continue
                    if x not in visited:
                        q.append(x)
            step+=1

打开转盘锁(中等)

来自算法小抄

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def up(cur,pos):
            cur = list(cur)
            if cur[pos] == '9':
                cur[pos] = '0'
            else:
                cur[pos] = str(int(cur[pos]) + 1)
            return ''.join(cur)
        def down(cur,pos):
            cur = list(cur)
            if cur[pos] == '0':
                cur[pos] = '9'
            else:
                cur[pos] = str(int(cur[pos]) - 1)
            return ''.join(cur)
​
        def BFS(target):
            deads = set(deadends)
            q1 = set()
            q2 = set()
            q1.add("0000")
            q2.add(target)
            step = 0
​
            while len(q1) and len(q2):
                temp = set()
                if len(q1) > len(q2): # 选择最短的集合为q1
                    q1,q2 = q2,q1
​
                for cur in q1:
                    if cur in deads:
                        continue
                    if cur in q2:
                        return step
                    deads.add(cur)
                    for pos in range(4): 
                        for x in [up(cur,pos),down(cur,pos)]: # pos为拨动的位置
                            temp.add(x)
                q1 = temp
                step+=1
            return -1
        return BFS(target)

对称二叉树(简单)

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        q = collections.deque()
        q.append(root)
        while len(q):
​
            values = []
            for i in range(len(q)):
                cur = q.popleft()
                if cur == None: 
                    values.append('null')
                    continue
                values.append(cur.val)
                for x in [cur.left,cur.right]:
                    q.append(x)
            if values != values[::-1]: return False
        return True

二叉树的层序遍历(中等)

class Solution:
    def levelOrder(self, root):
        if root == None:return []
        q = collections.deque()
        q.append(root)
        res = []
        while len(q):
            res.append([i.val for i in q])
            for i in range(len(q)):
                cur = q.popleft()
                for x in [cur.left,cur.right]:
                    if x == None: continue
                    q.append(x)
        return res

二叉树的层序遍历II(中等)

class Solution:
    def levelOrderBottom(self, root):
        if root == None:return []
        q = collections.deque()
        q.append(root)
        res = []
        while len(q):
            res.append([i.val for i in q])
            for i in range(len(q)):
                cur = q.popleft()
                for x in [cur.left,cur.right]:
                    if x == None: continue
                    q.append(x)
        return res[::-1]

N 叉树的层序遍历(中等)

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if root == None:return []
        q = collections.deque()
        q.append(root)
        res = []
        while len(q):
            res.append([i.val for i in q])
            for i in range(len(q)):
                cur = q.popleft()
                for x in cur.children:
                    if x == None: continue
                    q.append(x)
        return res

填充每个节点的下一个右侧节点指针(中等)

class Solution:
    def connect(self, root):
        if root == None: return root
        q = collections.deque()
        q.append(root)
        
        while len(q):
            len_q = len(q)
            for i in range(len_q):
                cur = q.popleft()
                if i < len_q - 1 and len(q) > 0:cur.next = q[0]
                for x in [cur.left,cur.right]:
                    if x == None: continue
                    q.append(x)
        return root

发表评论