- 动态规划篇
- 第一题： 斐波那契数列
- 第二题： 连续子数组的最大和
- 第三题： 青蛙跳台阶
- 第四题： 跳台阶拓展问题
解题思路：
这道题算是动态规划的入门题了，比较简单，所以放在第一题进行展示，这里还是稍微说一下解题思路。
- 当n>2时，我们只需要利用通项公式：fib(n)=fib(n-1)+fib(n-2) 即可求出fib(n),由于最后都会回到fib(1)、fib(0)的位置，所以需要我们求出fib(1)、fib(0) 。
- 由已知条件第一个位置和第二个位置的数为1，即fib(2)=fib(1)=1，而fib(0)=fib(2)-fib(1)=0,因此当n=1或n=0时，fib(n)=0。
代码部分：
/答题模板
class Solution {
public:
int Fibonacci(int n) {
}
};
class Solution {
public:
int Fibonacci(int n) {
if (n==0||n==1) return n;
return Fibonacci(n-1)+Fibonacci( n-2);
}
};
第二题： 连续子数组的最大和
解题思路：
方法一：
以输入array=[1,-2,3,10,-4,7,2,-5]为例：
- 我们先从第一个数array[0]开始，可以求出array[0],array[0]+array[1],…,array[0]+…+array[7]的八组数之和，然后找到这8组数中最大的数，记最大的数为res2,
- 然后我们对第二个数array[1]继续以上述的方法，如果第二个数中的组数之和大于res2，那么更新res2
- 直到数组结束为止，图片形式的过程如下：
方法一的理解比较容易，但是写出的代码时间复杂度超过了，只跑过了11个用例。话说最后一个用例中的数组是真的大，成千上万个数了。
方法二： 如下图所示：
代码部分：
/答题模板
class Solution {
public:
int FindGreatestSumOfSubArray(vector array) {
}
};
/方法一（可以求解问题，但是时间复杂度不满足）
class Solution {
public:
int FindGreatestSumOfSubArray(vector array) {
int res,res2,temp;
for(int i=0;ires){
res=temp;
}
}
if (i==0||res2
/方法二
class Solution {
public:
int FindGreatestSumOfSubArray(vector array) {
int len=array.size();
// 特判为空的情况
if(len==0){
return 0;
}
vector pre;
int sum=0,ans;
// 求前缀和
for(int i=0;i
第三题： 青蛙跳台阶
这道题的通过率为39%，奈何我不会做，扎心了。故这里借鉴牛客网漫天云天自翱翔的解题思路，加上我自己在补充一点解释，来攻克这道题。
解题思路：
- 假设有n阶台阶，在所有的跳法中，由于青蛙一次只能跳1步或者2步，所以青蛙跳上最后一阶只能由f(n-1)+1 或者f(n-2)+2 这两种情况得来。
即：f(n)=f(n-1)+f(n-2) - 同理:f(n-1)=f(n-2)+f(n-3),以此类推，我们可以得到下面这幅图。
- 相应代码在代码部分给出了，可以通过提交。但是在这之前，我们再仔细分析一波，如下图所示：
- 从图中我们可以看到，以这种方式虽然最后可以算出最终结果，但是在求解过程中，有些结果会被重复计算，这无疑造成了一部分不必要的开销。
- 解决方法： 可以采用一个map存储已经被计算过的值(不采用vector的原因，不确定台阶的数量，无法预先申请确定大小的数组)。
最后，我们给出了两种解决的代码，可以发现，优化后的代码效果更好！
代码部分：
/答题模板
class Solution {
public:
int jumpFloor(int number) {
}
};
/未优化前 运行时间：147ms 占用内存：564KB
class Solution {
public:
int jumpFloor(int number) {
if(number<=1) return 1;
return jumpFloor(number-1)+jumpFloor(number-2);
}
};
//以台阶=4为例，最后的返回结果是
return jumpFloor(3)+jumpFloor(2);
->return jumpFloor(2)+jumpFloor(1)+jumpFloor(1)+jumpFloor(0);
->return 3*jumpFloor(1)+2*jumpFloor(0);
->return 5;
/优化后 运行时间：3ms 占用内存：548KB
class Solution {
public:
map map_flag;//记录已经被计算出来的值
int jumpFloor(int number) {
if(number<=1) return 1;//初始两个台阶的结果
if(map_flag.count(number)){//map.count(Key)的意思是,如果map中存在key，则返回值为1否则为0。
return map_flag[number];
}
return map_flag[number]=jumpFloor(number-1)+jumpFloor(number-2);//未被计算过，存入map;
}
};
第四题： 跳台阶拓展问题
这道题说白了就是找通项公式的问题：
-
以台阶数n=5为例，我们可以发现，青蛙跳台阶存在着这样一个通项公式：
当n<2时，
f
(
n
)
=
1
{f(n) = 1}
f(n)=1 ；当n≥2时，
f
(
n
)
=
2
n
−
1
{f(n) = {2^{n - 1}}}
f(n)=2n−1，（方法一）
-
其实也可以理解为当n≥2时，
f
(
n
)
=
2
∗
f
(
n
−
1
)
{f(n) = 2*f(n - 1)}
f(n)=2∗f(n−1)，（方法二）
-
分析过程如下图所示：
代码部分：
/代码模板
class Solution {
public:
int jumpFloorII(int number) {
}
};
/方法一
class Solution {
public:
int jumpFloorII(int number) {
int res=0;
if(number<=1) return 1;//初始两个台阶的结果
return res=pow(2,number-1); //pow(a,b)表示求a的b次方
}
//不用pow，换成return res=1<<(number-1)也可以，左移表示乘2
};
/方法二（类似于第三题）
class Solution {
public:
map map_flag;//记录已经被计算出来的值
int jumpFloorII(int number) {
if(number<=1) return 1;//初始两个台阶的结果
if(map_flag.count(number)){//map.count(Key)的意思是,如果map中存在key，则返回值为1否则为0。
return map_flag[number];
}
return map_flag[number]=2*jumpFloorII(number-1);//未被计算过，存入map;
}
};
注： 以上题目都是在牛客网的剑指offer题库中刷的，有自己做的，也有不会做看别人精华解题思路，然后总结的。如果侵犯了您的权益，请私聊我。
最后，觉得本文内容对你有所帮助的话，感谢点赞收藏！
算法篇的题库还在持续更新中，小伙伴们不要着急。
导航链接：剑指—链表篇（C++）
导航链接：剑指—队列&栈篇（C++）
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）