摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10949人学习

全部文章（共105篇）

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

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

递归动态规划跳台阶数学

2021-07-27

0 407

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

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

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

2021-07-27

0 549

题解 | #01背包# 来自专栏

题目的主要信息：背包体积固定为V，从所有物品中选择几件物品，加起来体积不超过V，使加起来质量最大。所有数据大于0，无特殊情况方法一：递归（超时）递归是一种分治法，我们可以如下考虑： xix_ixi为1或0，表示对于物品iii取或者不取，viv_ivi表示物品iii的体积，wiw_i...

01背包动态规划递归

2021-07-26

3 985

题解 | #不相邻最大子序列和# 来自专栏

思路：题目的主要信息：在数组中，选取一组序列，使和最大选取的数中，位置不能相邻可以不选或是选一个数方法一：递归（超时）具体做法：对于n个元素的数组，如果最后一个数字被选择了，则前一个数字必不会被选，那就是n-2的结果加上最后一个数字，如果最后一个数字没有被选择，则是n-1的结果，选取其...

动态规划递归数组子序列

2021-07-25

0 557

题解 | #孩子们的游戏(圆圈中最后剩下的数)# 来自专栏

思路：题目的主要信息：从0到n-1（首尾相接）中每次去掉第m个数，下一次从去掉数的下一个开始，直到剩下最后一个数返回的是最后一个数有数为0的特殊情况方法一：递归具体做法：n个数相后去掉第m个数，还剩下n-1个数，依然要继续去掉第m个数。由此，从(n,m)的问题变成了(n-1,m)的子问...

数学递归迭代链表约瑟夫环

2021-07-25

0 571

题解 | #矩阵最长递增路径# 来自专栏

思路：题目的主要信息：矩阵内是非负数，求最长的递增路径的长度移动方向可以是上下左右，不能超出边界，这将是递归的判定条件同一条路径不能有重复的单元格，需要有记忆方法一：深度优先搜索具体做法：使用一个dp二维数组作为缓存，记忆该单元格是否访问过的同时记录以该单元为起点的最长路径是多少（0就...

dfs bfs 递归队列拓扑排序

2021-07-24

0 1032

题解 | #表达式求值# 来自专栏

思路：题目的主要信息：支持+ - *三种符号的运算器，其中优先级+ - 是一级，*更高一级支持括号运算方法一：栈 + 递归具体做法：对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。优先级处理我们可以借助栈，当遇到符号的时候如果是+，正常入栈，如果是...

表达式求值递归栈

2021-07-24

0 604

题解 | #输出二叉树的右视图# 来自专栏

思路：题目的主要信息：利用二叉树中序遍历结果及先序遍历结果构建一棵二叉树打印二叉树的右视图，即二叉树每层最右边的结点元素节点值互不相同可以发现解这道题，我们有两个步骤：建树打印右视图首先建树方面，先序遍历是根左右的顺序，中序遍历是左根右的顺序，因为节点值互不相同，我们可以根据...

二叉树右视图递归 dfs 层次遍历建树栈

2021-07-24

16 3667

题解 | #合并二叉树# 来自专栏

思路：题目的主要信息：合并（相加）二叉树位置相同的结点缺少的结点用另一棵树来补，若都缺则返回NULL 方法一：递归先序遍历同时先序遍历两棵树即可完成。具体做法：首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。然后依据先序遍历的特点，根左右的顺序递归访问。 c...

二叉树层次遍历先序遍历递归队列合并二叉树

2021-07-21

0 592

题解 | #把数字翻译成字符串# 来自专栏

思路：题目的主要信息：字母到数字分别为1-26映射，没有0 输入的数字是字符串，故非常大，超过了long long的表示范围但凡出现11-19，21-26的就可能出现两种译码结果求总后的译码结果种类方法一：递归（超时）具体做法：遍历字符串，每到一位，可以查看它是可以跨越两步还是只能...

动态规划字符串递归

2021-07-21

0 717