摸鱼学大师

题解

未归档(8)

/ 注册

全部文章 / 题解（共32篇）

题解 | #岛屿数量# 来自专栏

题目主要信息: 给定一个01矩阵，其中1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛只考虑矩阵中上下左右为相邻，斜方不算相邻求矩阵中表示的岛屿的个数具体思路: 矩阵中多处聚集着1，要想统计1聚集的堆数而不重复统计，那我们可以考虑每次找到一堆相邻的1，就将其全部改成0，而将...

C++ 递归 dfs

2022-02-16

1 455

题解 | #岛屿数量# 来自专栏

题目的主要信息：给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛只考虑上下左右为相邻判断岛屿的个数方法一：dfs 具体做法：可以从上到下从左到右依次遍历矩阵，每次遇到一个1则岛屿数记为1，然后将与这个1及与其相邻的所有1全部置为0，相当于这个岛屿已经被统...

C++ bfs dfs

2021-12-09

0 558

题解 | #在二叉树中找到两个节点的最近公共祖先# 来自专栏

题目的主要信息：给定一棵二叉树以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点二叉树非空，且每个节点值均不同方法一：路径比较法具体做法：利用dfs求得根节点到两个目标节点的路径，然后遍历两条路径依次比较，找到两条路径第一个不相同的节点即是...

C++ 递归 dfs 二叉树

2021-12-04

0 450

题解 | #二叉树中和为某一值的路径(三)# 来自专栏

题目的主要信息：给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点，如下图所示：方法一：两次dfs 具体做法：可以使用两次dfs解决，第一次dfs遍历二叉树每个结...

C++ 哈希表 dfs 二叉树

2021-12-04

23 1145

题解 | #二叉树中和为某一值的路径(一)# 来自专栏

题目的主要信息：给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径路径定义为从树的根结点开始往下一直到叶子结点所经过的结点路径只能从父节点到子节点，不能从子节点到父节点要求：空间复杂度 O(n)O(n)O(n)，时间复杂度 O(n)O(n...

C++ dfs 栈递归二叉树

2021-12-04

0 359

题解 | #二叉搜索树的第k个节点# 来自专栏

题目主要信息：给定一棵结点数为n二叉搜索树，需要其中的第k小的TreeNode结点值返回第k小的节点值即可不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1 保证n个节点的值不一样思路：根据二叉搜索树的性质，其中序遍历是由大到小的，由此仅需要中序遍历找到第k个小的结...

C++ 递归栈 dfs

2021-12-01

1 449

题解 | #二叉树的深度# 来自专栏

题目的主要信息：输入一棵二叉树，求该树的深度从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度方法一：递归（dfs）具体做法：对于一棵二叉树而言，其深度等于根结点这个1层+左子树和右子树深度的最大值，而每个子树我们都可以看成根节点，于是我们可以对这...

Java dfs bfs 队列

2021-12-01

0 368

题解 | #红和蓝# 来自专栏

题目的主要信息：一棵无向树，给每个顶点染成红色或蓝色每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点无法完成染色输出-1，完成染色输出每个结点的颜色具体做法：首先叶子结点因为只与父亲结点相连，所以叶子结点与父亲结点同色，因此我们可以利用dfs从根节点开始递归遍历树，从叶子结点...

C++ 动态规划 dfs

2021-11-01

1 796

题解 | #旅游# 来自专栏

题目的主要信息：地图上有 n 个城市，它们之间通过 n-1 条道路联通，即一棵无向树第一天会在 s 市住宿，并游览与它距离不超过 1 的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过 1 的所有城市不能住在一个已经浏览过的城市，最多要游览多少天因为每个会去到与这个城市相连...

C++ 动态规划 dfs

2021-11-01

7 576

题解 | #火车进站# 来自专栏

题目的主要信息：给定n列火车的入栈序列，0<n<100<n<100<n<10，用数列1-9表示每列火车火车只能从一个方向进，另一个方向出，只有站内的火车出去了，另外的才能进去要求输出所有火车出站的方案，以字典序排序输出方法一：全排列+栈具体做法：我...

C++ dfs 递归回溯栈

2021-10-30

2 650