xqxls
xqxls
全部文章
分类
二叉树技巧总结(2)
未归档(3)
题解(292)
归档
标签
去牛客网
登录
/
注册
xqxls的博客
TA的专栏
297篇文章
4人订阅
xqxls的题解
297篇文章
4409人学习
全部文章
(共297篇)
题解 | #信封嵌套问题#
来自专栏
题意整理 给定n个信封。 将长和宽较大的信封套在长和宽较小的信封上(必须严格大于)。 方法一(动态规划) 1.解题思路 当信封长度从小到大排列的时候,我们只需要让对应的宽度也从小到大就能完成信封嵌套,而让宽度从小到大排列,可以转化为求宽度序列的最长递增子序列。但是如果信封长度相同,宽度如何处理呢...
java
动态规划
二分
2021-07-29
1
850
题解 | #数的划分#
来自专栏
题意整理 给定一个整数n和一个整数k,将n分成k份。 每份不能为空,问有多少种分法(组合相同,排列不同的算同一种分法)。 方法一(暴力递归) 1.解题思路 递归终止条件:已经分了k份。 递归如何推进:份数加一,剩余的数字rest要减去已经分配的,而use是当前尝试分配的(只要小于rest,都可...
java
递归
动态规划
2021-07-29
3
876
题解 | #最大公约数#
来自专栏
题意整理 输入整数a和b。 求a和b的最大公约数。 方法一(暴力法) 1.解题思路 由于是a和b的最大公约数,那么它的范围一定在1到 之间,我们逆序遍历这个区间,找到能同时被a和b整除的数即可。 2.代码实现 import java.util.*; public class Solution ...
java
迭代
递归
辗转相除法
最大公约数
2021-07-28
0
595
题解 | #二叉树的个数#
来自专栏
题意整理 给定一颗节点个数为n的二叉树,二叉树中序遍历单调递增。 求有多少种这样的二叉树。 方法一(记忆化递归) 1.解题思路 由于该二叉树中序遍历单调递增,所以可以假设n个节点的值分别为1,2,……n。这与其他单调递增的情况相比,二叉树的树形数目一样多。我们任意取一个节点为根节点,然后左子树的...
java
动态规划
记忆化递归
树
2021-07-28
4
958
题解 | #kmp算法#
来自专栏
题意整理 给定模式串S和主串T。 求模式串S在主串T中出现的次数。 方法一(朴素模式匹配) 1.解题思路 首先进行特殊情况判断,如果模式串长度大于主串,或者主串为空,返回0。 然后分别遍历主串和模式串,只要当前字符相等,模式串和主串均后移一位,如果不相等,模式串重新回退到索引0的位置,同时主串...
java
模式匹配
kmp
数组
2021-07-28
14
2162
题解 | #几步可以从头跳到尾#
来自专栏
题意整理 给定一个数组A。 如果A数组中索引i对应值为t,说明可以从i处往后跳t步。 求从1出发跳到n,至少需要跳几次 方法一(从后往前贪心) 1.解题思路 基本思路是从后往前找能到达目标格子的前一个格子,然后在所有满足条件的格子中选择一个尽可能靠前的格子(贪心),找到之后,立即跟新目标格子的位...
java
贪心
数组
动态规划
2021-07-26
4
838
题解 | #主持人调度#
来自专栏
题意整理 有n个活动即将举办,每个活动都有一个开始时间和结束时间。 现在派若干个主持人来主持活动,要求每一个主持人主持的活动中,各个活动的时间段(开始时间到结束时间)不重叠。 方法一(优先队列) 1.解题思路 首先对startEnd按开始时间从小到大排序,如果开始时间相同,则按结束时间排序。 ...
java
堆
优先队列
贪心
排序
2021-07-26
18
2464
题解 | #未排序数组中累加和为给定值的最长子数组长度#
来自专栏
题意整理 给定一个未排序数组。 求累加和为k的子数组中最长的那个子数组的长度。 方法一(枚举) 1.解题思路 首先构建前缀和数组, 表示原数组索引0到i-1之间所有元素之和。 然后按子数组可能的长度,进行逆序枚举。 当某个长度下,子数组累加和刚好等于k,则直接返回。 2代码实现 import...
java
前缀和
哈希表
数组
2021-07-25
0
646
题解 | #字典树的实现#
来自专栏
题意整理 构造一个数据结构,用来处理字符串。 这个数据结构可以插入、删除、查询字符串。 查询分两种,一种是查询字符串是否出现过,另一种是查询前缀单词出现次数。 方法一(TrieNode实现) 1.解题思路 首先构建一个TrieNode结构,包括一个TrieNode类型的child数组,用于记录所...
java
字典树
前缀树
数组
数据结构
2021-07-24
8
961
题解 | #序列化二叉树#
来自专栏
题意整理 序列化:给定一颗二叉树,将二叉树的节点信息转化为字符串存储起来。 反序列化:给定一个序列化后的字符串,根据字符串还原出二叉树。 方法一(DFS) 1.解题思路 序列化:将大问题拆分为小问题,每次如果还可以递归,就将当前层拆分为当前层的左孩子,加上当前层的右孩子,加上当前层节点值。递归...
java
递归
队列
DFS
BFS
树
2021-07-22
0
633
首页
上一页
21
22
23
24
25
26
27
28
29
30
下一页
末页