摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #反复横跳# 来自专栏

题目的主要信息：一张带权无向图，图中任意两点间有且仅有一条路径，这是一棵无向树计算从任意点出发并访问完所有节点经过边的权值之和的最小值分析：首先，如果我们要从一个点到达其他所有点，每条边我们必须经过一次，因为任意两点之间有且仅有一条路径。然后，因为可以到树叶以后再回溯访问，再到另外的枝，...

动态规划图递归 dfs 树的直径

2021-09-14

1 612

题解 | #旋转跳跃# 来自专栏

思路：题目的主要信息：给出一个长为n的排列p，即1到n的任意一个组合一共有m对，每对表示交换排列p中序号为和中的元素，注意是序号而不是下标 m对使用次数与顺序不受限制，求任意次操作之后能得到的字典序最小的排列是什么方法一：并查集具体做法：可以用并查集的思想来解决，解释一下为何是并查集：假...

并查集 dfs 递归排序

2021-09-13

0 465

题解 | #最多节点数# 来自专栏

思路：题目的主要信息： n个节点n-1条边的无向连通图，即一棵无向树两个节点a与b，其中a在节点1，b在节点x，两点移动速度相同，求a和b移动到同一节点所需的最多节点数，需要包括1号节点在内方法一：dfs具体做法：我们可以使用两次dfs分别求得树中每个节点到节点1和节点x的距离，然后遍历找...

bfs dfs 递归队列

2021-09-12

0 636

题解 | #路径数目# 来自专栏

思路：题目的主要信息：一棵以1为根节点的树，节点值为0或者1 最多经过两个值为1的节点的情况下，求有多少条从根达到叶结点的路径方法一：dfs具体做法：我们首先根据题目给出的边信息构建邻接矩阵，可以访问某个节点的所有相邻节点。然后从根节点开始dfs递归，递归过程不断更新路径中1的数量coun...

bfs dfs 队列递归

2021-09-12

0 460

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

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

题解 | #牛牛打怪兽# 来自专栏

思路：题目的主要信息：数组A表示n只怪兽的血量攻击第只怪兽时，必须同时打到第和第只怪兽，每次攻击一滴血（没有这三只怪兽则无法攻击）怪兽血量归零后还可以继续受到攻击需要使用最少多少次组合拳才能把所有怪兽打死，如果打不死请输出-1 方法一：贪心+ 迭代具体做法：首先，组合拳一定要打至少3只...

贪心递归数组

2021-08-14

0 585

题解 | #简单变向# 来自专栏

思路：题目的主要信息：的跑道，要从到每次下一步列号必须加1，行号可以是本行或者邻近的一行，比如1行可以到1行或者2行，2行可以到1行或者2行或者3行，3行可以到2行或者3行数组x，y分别是路障的行列坐标，有路障的位置不能经过问路径种类有多少，取模1e+7 方法一：动态规划具体做法：用辅...

动态规划递归空间记忆数组

2021-08-11

0 504