手机wap网站多少钱,网页版微信小程序在哪,无锡百度快速排名,无锡网站建设无锡速联科技前言
本专栏旨在通过分类学习算法#xff0c;使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目#xff0c;帮助您深度理解每种算法#xff0c;避免出现刷了很多算法题#xff0c;还是一知半解的状态 专栏导航
二分查找回溯#xff08;Backtracking使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目帮助您深度理解每种算法避免出现刷了很多算法题还是一知半解的状态 专栏导航
二分查找回溯Backtracking双指针滑动窗口深度优先搜索广度优先搜索贪心算法单调队列堆Heap 算法解析
广度优先搜索Breadth-First Search简称 BFS是一种遍历或搜索树结构或图结构的算法。它从一个节点开始逐层层次遍历节点的邻居然后是邻居的邻居以此类推直到找到所需的解或遍历完所有可达的节点。
BFS 的核心思想是先访问离起始点最近的节点也就是说它先宽后深地访问节点这就是“广度优先”的含义。这种算法一般使用队列数据结构来实现。
以下是 BFS 的基本步骤 初始化队列首先将起始节点放入队列中。 遍历队列中的节点只要队列不为空就从队列的前端取出一个节点并检查它是否是目标节点。 如果找到目标根据问题的需要可以返回结果或继续搜索。如果不是目标将该节点的所有未访问的邻居节点加入队列的后端。 标记已访问节点为了避免重复访问节点需要记录已经访问过的节点。可以在节点数据结构中添加一个访问标记或者使用一个单独的数据结构如哈希表来存储已访问节点。 重复步骤2继续执行步骤2直到队列为空或找到目标。
BFS 通常用于解决以下类型的问题
最短路径问题在无权图中找到两个节点之间的最短路径。连通性问题检查图中的两个节点是否连通或者图是否完全连通。层次遍历层次遍历树结构或图结构如二叉树的层次遍历。
以下是一个在无向图中进行 BFS 的 Python 示例
from collections import dequedef bfs(graph, start, target):visited set() # 创建一个集合用于存储已访问的节点queue deque([start]) # 创建一个队列并将起始节点加入队列while queue:node queue.popleft() # 从队列中取出一个节点if node target:return True # 如果该节点是目标则返回Truevisited.add(node) # 将该节点标记为已访问for neighbor in graph[node]:if neighbor not in visited:queue.append(neighbor) # 将所有未访问的邻居加入队列return False # 队列为空未找到目标返回False# 示例图
graph {A: [B, C],B: [A, D, E],C: [A, F],D: [B],E: [B, F],F: [C, E],
}# 调用 BFS
print(bfs(graph, A, F)) # 输出True在这个例子中我们定义了一个图的邻接表表示并实现了 BFS 算法来找到从节点 ‘A’ 到节点 ‘F’ 的路径是否存在。这个 BFS 实现会返回一个布尔值标识是否找到了目标节点。 实战练习
省份数量
有 n 个城市其中一些彼此相连另一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected 其中 isConnected[i][j] 1 表示第 i 个城市和第 j 个城市直接相连而 isConnected[i][j] 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1
输入isConnected [[1,1,0],[1,1,0],[0,0,1]] 输出2
示例 2
输入isConnected [[1,0,0],[0,1,0],[0,0,1]] 输出3
提示
1 n 200n isConnected.lengthn isConnected[i].lengthisConnected[i][j] 为 1 或 0isConnected[i][i] 1isConnected[i][j] isConnected[j][i]
官方题解 二叉树的层序遍历II
给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历
示例 1
输入root [3,9,20,null,null,15,7] 输出[[15,7],[9,20],[3]]
示例 2 输入root [1] 输出[[1]]
示例 3 输入root [] 输出[]
提示
树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000
官方题解
