xqxls

题解

二叉树技巧总结(2) 未归档(3)

/ 注册

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

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

题意整理给定n个节点，n-1条边组成的无向连通图，有a、b两节点，分别位于1和x。求a和b同时移动到同一节点所经过的最多的节点数（路径必须包括1）。方法一（DFS） 1.解题思路首先建立邻接表，用于访问某个节点的所有子节点。然后初始化dist1和dist2，分别记录某节点到1节点所经...

java DFS BFS

2021-09-06

0 660

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

题意整理给定一颗有n个节点的树，每个节点的值初始为0或1。求有多少条从根节点到叶子节点的路径（要求路径上节点值得累加和小于等于2）。方法一（DFS） 1.解题思路首先建立邻接表，用于访问某个节点的所有子节点。从根节点开始递归，并且初始化一个num为2，每到一个节点，num减去对应节点...

java DFS BFS 树

2021-09-05

0 474

题解 | #父子情深# 来自专栏

题意整理给定一颗有n个节点的树，每个节点权值初始为0。现在有一个查询集合，集合中每一项提供两个参数r和v，每次查询将r节点及其子节点的权值增加v。返回最终每个节点的权值。方法一（DFS） 1.解题思路首先建立邻接表，用于访问某个节点的所有子节点。初始化查询中当前根节点的权值。按照...

java 递归 DFS BFS

2021-09-05

0 551

题解 | #牛牛晾衣服# 来自专栏

题意整理给定n件带水的衣服，用一个数组记录每个衣服的水滴数。现在要将所有衣服烘干，有两种方式，一种是自然烘干，每件衣服减少一滴水；另一种是机器烘干，其中一件衣服减少k滴水，剩下的衣服减少一滴水（自然烘干）。求最少花多长时间将所有衣服烘干。方法一（枚举） 1.解题思路首先确定花费时间的...

java 二分查找枚举

2021-09-04

0 636

题解 | #新集合# 来自专栏

题意整理给定一个集合包含1到n共n个数，从中选若干数出来组成新的集合。规定一个限制数组，限制数组里的每一个数对不能同时出现在新集合中。求这样的新集合有多少个。方法一（二进制枚举） 1.解题思路定义1个mask，表示1到n有没有出现过，若mask最低位为1，则表示1出现过，次低位为1，...

java 组合递归二进制

2021-09-03

1 553

题解 | #找出重复的数# 来自专栏

题意整理给定一个长度为n+1的序列，包含1到n之间的数。有一个数重复了，找出重复的数。方法一（数学） 1.解题思路先计算出序列中所有数字的和。然后计算1到n所有数字的和。由于序列中有一个重复了，所以序列和中多算了一次，从序列和中减去1到n所有数的和，即时那个重复的数字。动图展示...

java 数学异或

2021-09-03

1 617

题解 | #中序序列# 来自专栏

题意整理给定一颗二叉树的先序遍历序列和后序遍历序列。求中序遍历序列（如果某个节点只有一个子节点，则必是左子节点）。方法一（递归+重建二叉树） 1.解题思路在每次递归中，可以确定当前根节点在先序遍历开头处，后续遍历结尾处。在后续遍历中找到当前节点的第一个左子节点，则后续遍历中，该节点之前...

java 递归哈希表

2021-09-03

4 953

题解 | #序列取反问题# 来自专栏

题意整理给定一个序列，序列中每个下标对应一个值，选定一个下标i，则从i到的区间所有数都做一个标记。最后的目标是将所有的数都打上标记，问所有可能的方案中期望步数是多少。方法一（排列+费马小定理+快幂法） 1.解题思路对于任意均满足条件：若，则这两个条件一定满足其中1个。所以，如果，要么，...

java 排列费马小定理快幂法差分数组前缀和

2021-09-02

0 527

题解 | #最大最小# 来自专栏

题意整理给定一个数组。求所有的区间中，满足区间最大值大于等于最小值对应的区间个数。方法一（暴力） 1.解题思路先确定左端点，然后遍历所有的右端点。每次记录最大值和最小值，只要最大值大于等于最小值，则结束内循环。将满足条件的区间数加入到结果变量。直到确定完所有的左端点。动图展示：...

java 单调栈二分

2021-09-01

0 444

题解 | #消息压缩# 来自专栏

题意整理有一段长度为n的消息，要将消息分成若干组，每组2个消息。第一个消息长度必须是4，第二个消息长度不能为0。求有多少种分割方法。方法一（递归） 1.解题思路递归终止条件：如果剩下的长度为0，说明正好完成分割，返回一种方案。递归如何推进：首先减去4，表示第一个消息的长度，然后第二...

java 递归动态规划

2021-09-01

0 569