摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #小红的树# 来自专栏

题目的主要信息：没有回路的无向连通图，可以看成树，根结点为1 其中一部分结点染成了红色之后有qqq次询问，每次询问以该结点作为根的子树有多少红色结点具体做法：根据输入的父节点，构建树的邻接表。然后用字符串记录输入的染色信息，再通过dfs构建，对树进行染色，构建dp数组。其中dp[i]d...

C++ 动态规划递归 dfs

2021-10-27

2 656

题解 | #迷宫问题# 来自专栏

题目的主要信息：一个n∗mn*mn∗m的矩阵表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走要求找出从左上角到右下角的最短路线入口点为[0,0][0,0][0,0],第一格一定是可以走的路数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道方法一：d...

C++ dfs 栈递归

2021-10-24

10 2504

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

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

C++ dfs bfs

2021-10-03

3 436

题解 | #寻找牛妹# 来自专栏

题目的主要信息： n个房间一共n-1个通道相连，每个房间可互相到达，这就是一棵无向树牛牛一开始在1号房间，要到另一个房间去找牛妹，这个过程中每条痛道最多只能走两次，且如果当前牛牛有没走过的通道可以走，牛牛就不会去走走过一次的通道每次走过一条通道花费1金币，一共m个查询，每次查询牛妹在xix_i...

C++ dfs

2021-09-26

0 415

题解 | #Tree V# 来自专栏

题目的主要信息：一棵n个节点的完全二叉树，其dfs正序遍历（先左后右dfs）序列记录在a数组中还原这棵树并返回加密后的答案，加密方式为这棵树的所有边的两个端点权值进行异或运算，然后全部相加完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k...

C++ dfs 完全二叉树二叉树

2021-09-17

0 424

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

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

动态规划图递归 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

题解 | #两棵树的问题# 来自专栏

思路：题目的主要信息：有两个结点数都为n，根都是1的树，设根的深度为0 定义点对(x,y)的价值为树1中x和y的最近公共祖先的深度+树2中a[x]和a[y]的最近公共祖先的深度输出所有点对的最大值价值数组b与数组c分别记录树1与树2的各个节点的父节点方法一：暴力解法（超时）具体做法：我们...

树 LCA 倍增算法 dfs 集合

2021-09-03

0 563