Tag Archives: dfs

323. Number of Connected Components in an Undirected Graph

解题思路：一道图的题目，给出顶点的个数以及顶点之间的连接，求连通分量，与图的题目一样，先通过给出的边的信息建立图的矩阵表示。 然后依次遍历所有的点，统计可以进行dfs的次数，就是连通分量的个数。 时间复杂度：O(V + E) / 空间复杂度 O(V)

1192. Critical Connections in a Network

解题思路：这道题前不久才加入leetcode题库，也被Amazon加入OA，迅速上升到第七位高频，在6个月的时间内被问189次。不过我不认为这是一道很好的面试题，因为要解题需要知道一个叫Tarjan的算法，才能求图中的一个关键边/桥(如果删除该边，图中的连通分量将会增加)。 这道题需要遍历路径，应该只能用DFS解，leetcode的标注为hard，难应该就难在DFS中每一层的处理比较复杂，除此之外都是图的基本知识，如果对Tarjan算法有一定的了解，是一个非常好练习DFS的机会。 Tarjan算法：对于每一个顶点需要两个信息： 访问顶点的timestamp：该顶点在整个dfs的遍历中的顺序，这个值一旦设定不改变 顶点的lowLink：与该顶点连接的最低的timeStamp，这个值需要根据dfs遍历来更新 如果在处理完所有的点之后，如果： current.timeStamp < next.lowLink 那么从 current -> next 就是一个关键边/桥。 关于Tarjan算法的细节可以参考Youtube视频。 时间复杂度：O(V + E) 需要访问每一个顶点以及与顶点连接的边 空间复杂度：O(V + E）需要根据给出的边建立图并存储每个顶点的两个信息

1254. Number of Closed Islands

解题思路：一道在矩阵上做dfs的题目，leetcode的典型问题模型，求岛的数量，但这一次但岛的定义变为完全包围起来的岛。 在每一层的处理以及如何进行下一层的dfs不变，变化的只有dfs的返回条件 如果dfs越界则明显岛不被包围(下表索引超出矩阵范围)，返回false 如果遇到水域(grid[i][j] == 1)， 返回true 直到遍历完整个矩阵 时间复杂度 O(m * n) / 空间复杂度 O(1)

1261. Find Elements in a Contaminated Binary Tree

解题思路：这是一道比较综合的题目，设计两个函数，其中的一个是构造函数。为了实现函数的功能，需要完善类的设计，添加一个成员变量存储转换后的树的根节点，因为输入是在形参里，会随着函数的结束而销毁。两个函数的实现也都非常的直观，算是另外的两个leetcode题目的结合吧。 时间复杂度：O(n) / 空间复杂度： O(1)

1219. Path with Maximum Gold

解题思路：本题的做法比较简单且直观，遍历给出的金矿矩阵，如果有金子，则依次为起点开始进行dfs，为了节省空间，将访问过的金矿的数量设置为0，当本层的递归结束之后再将它恢复为原来的值。 注意：这道题目不能采用dfs + memorization，因为对于一个固定的点来说，它的终止条件对于不同的起始点是不一样的，例如一个二维的矩阵 [[1, 2], [3, 4]], 如果以1作为开始点，4 的返回值应该为(2, 3)(分别从不同的方向访问4)，可如果从2 开始作为起始点访问，它的值应该是4(1 + 3)。所以在描述中限定了规模为 15 * 15 且最多有25 个金矿。 时间复杂度：假设金矿分布满，每一次的递归有三个不同的选择， 为 O(3 ^ (m * n)) 空间复杂度：O(1)

1245. Tree Diameter

解题思路：本题是一道图上做有记忆的dfs搜索的题目，是无向图，给定的输入是图的各个边，题目中给出一个关键信息(Each node has labels in the set {0, 1, …, edges.length})可知图中没有环，如果是有环的图这个题是无解的。最好的证明方法就是反正法，如果有环的话标号最大的节点必然小于边的数量，例如[0, 1], [1, 2], [0, 2], 三个节点且三条边，但编号最大的节点小于边的数量。 作为一个无向不联通图，节点主要分为两种类型，一种可以称为叶节点(这个并非是官方的名字，只是我自己叫着方便)，即只有一个边与它连接，除来叶节点之外的节点则至少有两个边相连。 题目要求找出最长的一个path依次来定义这个tree的直径，很显然直径的选择是从一个叶节点到另外一个叶节点，在构建完图之后找到所有的叶节点，开始进行dfs的遍历，找出其中最长的一条路径来定义树的直径。 这个题目的模型与 568. Maximum Vacation Days 最大的不同是在计算过的值的记忆部分。 在568中每个节点的进与出的部分很清晰的分离，因此只要计算过一次，下一次递归不团从哪个节点进，都返回同样的答案。 本题则需要根据不同的输入返回不同的结果，所以memo的数据结构也不一样，对于每一个节点，需要用一个map来对应该节点到下一个节点的答案。这个地方需要使用map，而不是vector，因为需要使用到下一个节点的序号来索引。如果选择vector，无法将序号转换成下表。 时间复杂度：对于每一个节点而言，图需要计算各个出的值，复杂度为 O(e) 空间复杂度：存储每个节点到每一个方向的值 O(e)

568. Maximum Vacation Days

解题思路：这是一道在图上做有记忆dfs的题目，图的信息通过矩阵给出。一共有N个城市，城市之间的连同关系在 flights 矩阵中，代表着dfs中下一次递归的可行选择。另外一个给出的信息是K个星期中在每一个城市可以得到的假期数量，题目要求找出K个星期中最多的假期，这也是每次递归中需要累加的值，K也是递归终止的条件。 为了节省时间复杂度，需要另外分配一个memo的矩阵将之前计算过的值保留，如果这个值不为 0 每次递归直接返回。 注意：给出的航班信息表中没有每个城市到自己的航班，即flight[i][i] 为0 ，这个符合常识，但并不符合题意。因为两个星期之间并不一定非要飞到另外一个城市，如果呆在本地假期更多也可以不飞，需要做一个预先的处理就是将 flights[i][i] 全部置为1。 时间复杂度：这个取决于矩阵的稀疏程度，也就是到下一个城市可以的选择，这个有由flights 矩阵给出，假设每两个城市之间都有相互连接的航班，共需要做K次的选择，每次计算后将结果保存避免不必要的时间消耗，最终的复杂度为 O(N * K) 空间复杂度：为每个城市在每个星期分配一个变量保存计算过的值，复杂度 O(N * K)