摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10911人学习

全部文章（共32篇）

题解 | #牛妹的野菜（权值最大的路径）# 来自专栏

思路：题目的主要信息：一个有向无环图，路径是单向从小序号到大序号，每个节点有权值求图中一条权值和最大的路径，并以字符串输出这条路径方法一：动态规划具体做法：我们可以用动态规划的方式来解决。首先利用给出的路径数组构建一个邻接矩阵，我们以weigh数组表示从每个节点开始的最长路径的长度，pa...

空间记忆搜索递归动态规划 dfs 图

2021-09-03

0 660

题解 | #回路# 来自专栏

题目的主要信息： n个节点，m条边，数组edge记录的是有边的两个节点判断这个图是否有从1号节点开始的回路方法一：dfs 具体做法：首先我们构建图。然后从节点1开始进行深度优先搜索，遍历与其相连的每一个节点，每到一个节点不能遍历前序节点或者已经访问过的，然后每次需要判断是否回到了节点1，如...

回路图 bfs dfs 递归队列

2021-08-26

0 711

题解 | #连通块# 来自专栏

思路：题目的主要信息： n个房间，n-1条通道连通，这就是一棵树树每个节点值记录在x数组去掉树的一些边，使之成为k个子树，且每个子树的节点值和大于等于m，问可行性方法一：dfs具体做法：主体思路是，将树分成每个部分刚好大于等于m，看是否有大于等于k个子树。首先构建图，利用深度优先搜索自底...

dfs bfs 递归树子树和

2021-08-17

0 578

题解 | #扩散II# 来自专栏

思路：题目的主要信息： n个节点，n-1条边使之连通，这就是一棵树（注意不一定是二叉树），每条边代表距离为1 一共m次污染，每次发生在数组元素x[i]，影响范围是与发生点距离不超过y[i]（发生点视为距离为0），影响范围所有节点污染指数增加z[i] 污染指数初始值全部为0，求m次污染发生后，每个...

dfs 递归排序

2021-08-16

0 565

题解 | #我们的距离# 来自专栏

思路：题目的主要信息：一棵树每边长度为1，节点到节点的距离为某个节点的权值现求树每个节点的权值方法一：两次dfs具体做法：我们可以用两次dfs解决这个问题。第一次dfs遍历这棵树，找到每个节点有多少个子节点，第二次dfs遍历每个节点，根据第一次找到的子节点数推算出到其他任何节点的距离。...

bfs dfs 树队列递归

2021-08-08

0 686

题解 | #通讯网络# 来自专栏

思路：题目的主要信息： n个节点，n-1条边，使之全部连通，这就是一棵树权值就是通话质量，任意去掉一条边，求影响的最大的通话质量（有n个城市受影响，就要用n乘上去掉边的权值）即影响的城市数为去掉边后两个子树节点数相乘，因此我们找到，其中是去掉权值为的边后子树的节点数。这道题需要求子树的...

dfs 子树节点数递归

2021-08-06

0 553

题解 | #最长路径# 来自专栏

思路：题目的主要信息： n个节点，n-1条边，使之全部连通，这就是一棵树树中任意节点的路径最长值，就是求树的直径首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度优先搜索到另一最远距离就是树的直径。方法一：两次深度优先搜索具体做法：我们需要用哈希表来存储树的边结...

最长路径树的直径 dfs bfs 递归队列哈希表

2021-08-06

0 687

题解 | #树的子结构# 来自专栏

思路：题目的主要信息：给定两棵二叉树树的层次遍历序列判断二叉树B是否为A树的子树约定空树不是任意一个树的子结构方法一：两层先序遍历具体做法：对A树的每个结点递归遍历（先序），寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是A树与B树同步先序遍历，遍历完一个B树或者有不相...

二叉树子树 dfs 先序遍历中序遍历

2021-07-27

0 471

题解 | #矩阵最长递增路径# 来自专栏

思路：题目的主要信息：矩阵内是非负数，求最长的递增路径的长度移动方向可以是上下左右，不能超出边界，这将是递归的判定条件同一条路径不能有重复的单元格，需要有记忆方法一：深度优先搜索具体做法：使用一个dp二维数组作为缓存，记忆该单元格是否访问过的同时记录以该单元为起点的最长路径是多少（0就...

dfs bfs 递归队列拓扑排序

2021-07-24

0 1031

题解 | #输出二叉树的右视图# 来自专栏

思路：题目的主要信息：利用二叉树中序遍历结果及先序遍历结果构建一棵二叉树打印二叉树的右视图，即二叉树每层最右边的结点元素节点值互不相同可以发现解这道题，我们有两个步骤：建树打印右视图首先建树方面，先序遍历是根左右的顺序，中序遍历是左根右的顺序，因为节点值互不相同，我们可以根据...

二叉树右视图递归 dfs 层次遍历建树栈

2021-07-24

15 3625