可以做砍价链接的网站,做公司网站要注意哪些问题,wordpress主题中心开发,合肥网站制作模板推荐前言
本专栏旨在通过分类学习算法#xff0c;使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目#xff0c;帮助您深度理解每种算法#xff0c;避免出现刷了很多算法题#xff0c;还是一知半解的状态 专栏导航
二分查找回溯#xff08;Backtracking使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目帮助您深度理解每种算法避免出现刷了很多算法题还是一知半解的状态 专栏导航
二分查找回溯Backtracking双指针滑动窗口深度优先搜索广度优先搜索贪心算法单调队列堆Heap 算法解析
深度优先搜索Depth-First Search简称 DFS是一种用于遍历或搜索树、图结构的算法。与广度优先搜索不同深度优先搜索会尽可能深地遍历图的分支直到到达末端然后回溯到上一个分叉点继续探索未被遍历的分支。
DFS 可以通过递归或栈数据结构来实现。递归实现的代码结构较为简洁而非递归实现则使用栈来模拟递归过程。以下是 DFS 的基本步骤 选择起点从一个起点节点开始遍历。 访问节点访问当前节点并将其标记为已访问。 递归遍历邻居对于当前节点的每一个未访问的邻居节点递归地调用 DFS 方法。 回溯在访问完当前节点的所有邻居后回溯到上一个节点继续执行步骤3。 重复重复上述步骤直到所有从起点可达的节点都被访问。
DFS 的特点是优先沿着一条路径深入探索直到尽头后再回溯。这种特性使得 DFS 不仅适用于求解路径问题还常用于拓扑排序、连通性检测、求解迷宫等问题。
以下是一个使用递归实现 DFS 的 Python 示例
def dfs(graph, node, visited):if node not in visited:print(node) # 可以在这里处理节点visited.add(node) # 将节点标记为已访问for neighbor in graph[node]:dfs(graph, neighbor, visited) # 递归访问邻居节点# 示例图
graph {A: [B, C],B: [A, D, E],C: [A, F],D: [B],E: [B, F],F: [C, E]
}# 创建一个集合用于存储已访问的节点
visited set()# 从节点 A 开始 DFS
dfs(graph, A, visited)在这个示例中我们定义了一个图的邻接表表示并使用递归方法实现了 DFS 算法。当我们从节点 ‘A’ 开始遍历图时算法会深入访问每个节点直到所有节点都被探索到。这里的 visited 集合用于记录已经访问过的节点以防止节点被重复访问。 实战练习
省份数量
有 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]
官方题解 岛屿数量
给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
示例 1 输入grid [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“0”,“0”,“0”] ] 输出1
示例 2 输入grid [ [“1”,“1”,“0”,“0”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“1”,“0”,“0”], [“0”,“0”,“0”,“1”,“1”] ] 输出3
提示 m grid.length n grid[i].length 1 m, n 300 grid[i][j] 的值为 ‘0’ 或 ‘1’
官方题解
