摸鱼学大师

题解

未归档(8)

/ 注册

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

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

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

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

2021-07-27

0 0

题解 | #二维数组中的查找# 来自专栏

题目的主要信息：矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复找到矩阵中有没有给定元素即可方法一：暴力法具体做法：从上到下每行，每行中从左至右遍历二维数组，依次查找。 class Solution { public: bool Find(in...

二维数组二分法查找

2021-07-27

0 498

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

思路：题目的主要信息：找到两个数a与b的最大公约数 a与b最小为1，无特殊情况最常规的求公因数，以下罗列几种方法。方法一：穷举法具体做法：优先考虑a与b一个是另一个因子的情况，可以直接返回。然后找到较小值，由小到大穷举2到较小值的所有数字，遇到公约数更新答案。 class Solution...

最大公约数辗转相除更相减损

2021-07-27

0 412

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

思路：题目的主要信息：一棵树树的结点数为n 其中序遍历递增但是题中并没有提到结点中的数据如何，只要数据任意组合的话，任何二叉树都可以有一个中序递增序列，因此这道题就化为结点数为n的二叉树有多少种，这就变成了算法中的卡特兰数（Catalan数）的问题：如果没有结点，只有空树一种形态，则 ...

动态规划卡兰特数二叉树中序遍历大整数

2021-07-27

1 610

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

思路：题目的主要信息：在文本串T中找到模板串S出现的次数 S不为空要求时间空间最多为方法一：暴力法（不会超时，但不符合要求）具体做法：遍历文本串，每次截取下标后m个与文本串比较，如果相同则答案加一。需要注意后面要留出m位防止访问越界。 class Solution { public: ...

KPM 字符串匹配

2021-07-27

1 477

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

思路：题目的主要信息： n长度的数组，每个元素表示从该数下标位置最多可往后跳跃多少个从1开始，无0的情况方法一：动态规划（可能会超时）题目要求的是找出从1跳到n最快的路径，即所需步数最短，我们可以想到遍历所有的路径，从中找出步数最短的路径。具体做法：我们可以用dp[i]表示第i个元素到最后...

动态规划贪心数组

2021-07-27

0 956

题解 | #主持人调度# 来自专栏

思路：题目的主要信息： n个活动，有各自的区间一个主持人不能在相交的区间工作将相交的区间分成一组，最后组数即是主持人的数量数字为int型的范围，可能会出现负数方法一：排序+遍历比较具体做法：利用辅助数组单独各个活动开始的时间和结束时间，然后分别进行排序。遍历个活动，如果某个活动开始的时...

贪心堆排序

2021-07-26

0 542

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

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

01背包动态规划递归

2021-07-26

3 980

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

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

动态规划递归数组子序列

2021-07-25

0 549

题解 | #矩阵乘法# 来自专栏

思路：题目的主要信息：求两个矩阵相乘结果，两个矩阵一定存在，不用排除特殊情况两个矩阵都为的矩阵方法一：暴力法具体做法：直接遍历二维矩阵的每个元素，其中等于a b两个矩阵的行乘列叠加即可。 class Solution { public: vector<vector<i...

矩阵乘法

2021-07-25

0 573