xqxls

分类

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

/ 注册

TA的专栏 297篇文章 4人订阅

297篇文章 4409人学习

全部文章（共248篇）

题解 | #最长回文子序列# 来自专栏

题意整理给定字符串。求这个字符串的最长回文子序列。回文序列是指，如果将原序列翻转后与原序列相等，那么这个序列是回文序列。方法一（记忆化递归） 1.解题思路递归终止条件：左边界和右边界之间只含一个元素，或只含两个元素。递归如何推进：如果左边界和右边界相等，则可以将两边分别向中间压缩一...

java 记忆化递归动态规划

2021-07-30

3 789

题解 | #信封嵌套问题# 来自专栏

题意整理给定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 2161

题解 | #几步可以从头跳到尾# 来自专栏

题意整理给定一个数组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