xqxls

分类

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

/ 注册

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

297篇文章 4447人学习

全部文章（共28篇）

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

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

java 记忆化递归动态规划

2021-07-30

3 816

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

题意整理给定n个信封。将长和宽较大的信封套在长和宽较小的信封上（必须严格大于）。方法一（动态规划） 1.解题思路当信封长度从小到大排列的时候，我们只需要让对应的宽度也从小到大就能完成信封嵌套，而让宽度从小到大排列，可以转化为求宽度序列的最长递增子序列。但是如果信封长度相同，宽度如何处理呢...

java 动态规划二分

2021-07-29

1 871

题解 | #数的划分# 来自专栏

题意整理给定一个整数n和一个整数k，将n分成k份。每份不能为空，问有多少种分法（组合相同，排列不同的算同一种分法）。方法一（暴力递归） 1.解题思路递归终止条件：已经分了k份。递归如何推进：份数加一，剩余的数字rest要减去已经分配的，而use是当前尝试分配的（只要小于rest，都可...

java 递归动态规划

2021-07-29

3 888

题解 | #二叉树的个数# 来自专栏

题意整理给定一颗节点个数为n的二叉树，二叉树中序遍历单调递增。求有多少种这样的二叉树。方法一（记忆化递归） 1.解题思路由于该二叉树中序遍历单调递增，所以可以假设n个节点的值分别为1，2，……n。这与其他单调递增的情况相比，二叉树的树形数目一样多。我们任意取一个节点为根节点，然后左子树的...

java 动态规划记忆化递归树

2021-07-28

4 978

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

题意整理给定一个数组A。如果A数组中索引i对应值为t，说明可以从i处往后跳t步。求从1出发跳到n，至少需要跳几次方法一（从后往前贪心） 1.解题思路基本思路是从后往前找能到达目标格子的前一个格子，然后在所有满足条件的格子中选择一个尽可能靠前的格子（贪心），找到之后，立即跟新目标格子的位...

java 贪心数组动态规划

2021-07-26

4 871

题解 | #正则表达式匹配# 来自专栏

题意整理用模式串来检验整个匹配串。模式串中的'.'匹配任何字符，'*'表示它前面的字符可以出现任意次（即0到无穷次）。方法一（记忆化递归） 1.解题思路递归终止条件：当模式串走完的时候，递归终止，如果此时，原串也走完了，则匹配成功；如果没走完，则匹配失败。每一层递归从上一层获取什么：...

java 递归动态规划

2021-07-21

6 974

题解 | #股票交易的最大收益（二）# 来自专栏

题意整理已知股票每一天的价格波动最多持有一只股，也就是买入时，必须卖出之前持有的股最多交易两次，求最大收益方法一（动态规划） 1.解题思路本题的难点在于交易次数进行了限定，可以多开一维空间来存储交易次数。所以可以用三维dp来求解。状态定义：第一维表示交易天数，第二维表示交易次数，第...

java 动态规划状态压缩

2021-07-18

6 1155

题解 | #股票(无限次交易)# 来自专栏

题意整理已知股票每一天的价格波动。最多持有一只股，也就是买入时必须卖出之前持有的股。可以无限次买入和卖出股票，求最大收益。方法一（贪心） 1.解题思路为了在股票交易中获得最大收益，我们肯定希望在极小值点买入，在邻近的极大值点卖出，由于是邻近的极大值点，所以在买入点和卖出点之间股票肯定是...

java 动态规划贪心

2021-07-18

0 703