xqxls

题解

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

/ 注册

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

题解 | #牛牛恨66# 来自专栏

题意整理输入正整数。在到之间，有多少个数字不包含连续的，则输出多少。方法一（记忆化递归） 1.解题思路递归终止条件：当输入为0时，只有1不含66，返回1；当输入为1时，1到10这十个数都不含66，返回10。递归如何推进：当前位（第i位）可以选择6，也可以不选择6。如果选择6，...

java 记忆化递归动态规划

2021-08-01

0 726

题解 | #牛妹的招聘# 来自专栏

题意整理有n个同学，每个同学都有一个聪明值和一个勤奋值。从这个n个同学中选出若干同学，使得总的聪明值累加和和勤奋值累加和最大，但是聪明值累加和、勤奋值累加和必须大于0。方法一（单调栈） 1.解题思路牛妹想选择一些同学作为同事，如果最终有N个同学，那么总的组合数就是（每个同学，要么选，...

java 单调栈动态规划 01背包

2021-08-01

0 563

题解 | #数组中只出现一次的数（其它数出现k次）# 来自专栏

题意整理给定一个数组。求数组中只出现一次的数。方法一（哈希表） 1.解题思路记录数组中每一个数出现的次数，并将数组中的数作为键，出现次数作为值添加到哈希表中，然后遍历哈希表，当某个键对应的值为1时，直接返回对应的键，即找到了只出现一次的数。动图展示： 2.代码实现 import ja...

java 哈希表位运算

2021-07-31

3 808

题解 | #牛牛的数列# 来自专栏

方法一（递归） 1.解题思路递归终止条件：向左寻找时，寻找到索引0终止；向右寻找时，到索引nums.length-1终止。递归如何推进：向左寻找时，如果大于左边元素，直接由左边索引子序列加一，否则重置为1；向右寻找时，如果小于右边元素，直接由右边索引子序列加一，否则重置为1。每一层递归返回什...

java 动态规划递归

2021-07-30

1 599

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

题意整理给定字符串。求这个字符串的最长回文子序列。回文序列是指，如果将原序列翻转后与原序列相等，那么这个序列是回文序列。方法一（记忆化递归） 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

题解 | #最大公约数# 来自专栏

题意整理输入整数a和b。求a和b的最大公约数。方法一（暴力法） 1.解题思路由于是a和b的最大公约数，那么它的范围一定在1到之间，我们逆序遍历这个区间，找到能同时被a和b整除的数即可。 2.代码实现 import java.util.*; public class Solution ...

java 迭代递归辗转相除法最大公约数

2021-07-28

0 616

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

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

java 动态规划记忆化递归树

2021-07-28

4 978

题解 | #kmp算法# 来自专栏

题意整理给定模式串S和主串T。求模式串S在主串T中出现的次数。方法一（朴素模式匹配） 1.解题思路首先进行特殊情况判断，如果模式串长度大于主串，或者主串为空，返回0。然后分别遍历主串和模式串，只要当前字符相等，模式串和主串均后移一位，如果不相等，模式串重新回退到索引0的位置，同时主串...

java 模式匹配 kmp 数组

2021-07-28

15 2194