摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #牛妹的蛋糕# 来自专栏

思路：题目的主要信息：每天吃掉蛋糕总数的1/3，再额外吃1个吃到第n天还剩下1个蛋糕，问最开始总共有多少蛋糕这是一个数学问题，可以用递归、动态规划、迭代处理。方法一：递归具体做法：第n天还剩下1一个蛋糕，那么总蛋糕数就是n-1的子问题+1的3/2，可以写出如下递归： class Sol...

递归迭代动态规划数学模拟

2021-07-29

0 539

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

思路：题目的主要信息：求给定数组的一个子序列，该子序列修改一个元素后可以变成完全递增序列，可以不用修改要求返回子序列的最长长度基本思路就是遍历数组中的所有元素，检查如果该元素后一个元素大于前一个元素，我们可以找到以它前一个元素结尾的最长递增序列加上以它后一个元素开始的最长递增序列，二者相...

动态规划数列递归最长递增子序列

2021-07-28

0 549

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

思路：题目的主要信息：找到给定串中的最长回文子序列的长度子序列不同于字串，不要求字符全部相邻回文序列是指这个序列无论从左读还是从右读都是一样的方法一：递归（超时）性质：一个字符串的最长回文子序列等于该字符串与其逆序的最长公共子序列。具体做法：我们可以利用上述性质，构造字符串s的逆序字符...

动态规划子序列字符串递归回文序列

2021-07-28

0 610

题解 | #加起来和为目标值的组合# 来自专栏

思路：题目的主要信息：从数组num找出所有加起来等于target的组合每个组合num中每个元素只能用1次返回的值必须是非递减次序，组合不能重复方法一：递归+枝剪具体做法：对于排序后的num数组中第一个元素，我们可以考虑如果它比target大，那么后续都会比target大，没有加起来等于...

回溯递归枝剪哈希表数组

2021-07-28

0 1342

题解 | #集合的所有子集# 来自专栏

思路：题目的主要信息：有一个没有重复元素的整数集合S，经测试S的元素本就是升序求所有子集，子集顺序不定，子集中无重复内容，但是子集中的元素必须是升序方法一：穷举法具体做法：学过离散数学就知道，如果集合的元素是个，那就有个子集，如果我们枚举一一构造，那就需要做一个到的映射，我们可以想到二进...

子集集合数组二进制递归回溯

2021-07-28

0 682

题解 | #括号生成# 来自专栏

思路：题目的主要信息：求n对括号的全部合法组合，左右括号之间任意组合，只要合法就行需要输出所有的结果方法一：暴力构造+栈验证具体做法：首先构造一个"(((((((......))))))"形式的字符串，然后调用STL的next_permutation函数遍历其每一个排...

括号栈递归回溯枝剪字符串

2021-07-27

0 527

题解 | #平衡二叉树# 来自专栏

思路：平衡二叉树的性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。判断某二叉树是否为平衡二叉树，就需要判断任意一结点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则。则可以相当将问题不断分成子问题，使用递归。方法一：自顶向下考...

递归平衡二叉树二叉树

2021-07-27

0 450

题解 | #二叉树的镜像# 来自专栏

思路：题目的主要信息：将二叉树镜像，即将其所有左右子树交换我们可以考虑自底向上依次交换二叉树的左右结点。方法一：递归具体做法：采用递归的方法，首先深入到二叉树的叶子结点，交换其左右，然后依次往上交换。 class Solution { public: TreeNode* Mirr...

递归栈二叉树镜像遍历

2021-07-27

0 455

题解 | #跳台阶扩展问题# 来自专栏

思路：题目的主要信息：对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数（与斐波那契数列不一样） n为正整数，求青蛙跳上n级台阶的方案数方法一：暴力解法具体做法：对于n个阶梯，如果青蛙第一次选择跳1阶，那么它有还剩下n-1阶，如果选择跳2阶，那么它还剩下n-2阶以此类推，后面剩...

递归动态规划跳台阶数学

2021-07-27

0 395

题解 | #斐波那契数列# 来自专栏

思路：题目的主要信息：斐波那契数列每项的公式为:，从0开始，，求出斐波那契数列的第n项 n最大不超过39，结果不会超出int的范围，不用考虑long long 方法一：递归具体做法：根据公式，每次返回，结束递归的点就是1或者0 class Solution { public: in...

斐波那契数列动态规划递归记忆化

2021-07-27

0 0