大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说算法分析（七）：斐波那契数列「建议收藏」,希望您对编程的造诣更进一步.
这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战
前言
- 这道题就是找出这个数列的第 n 个节点，而这个数列有个特地点就是第 n 个数字 = n-1 + n-2 两个数字之和，所以我们一般这种有两种解法，递归和迭代
- 题目地址：leetcode-cn.com/problems/fe…
第一种解法：迭代法
- 看到这种一个数等于前两个数之和的题目，第一个想法就需要存储以前的数字，一般都是用数组
- 第一步，创建一个数组
- 第二步，给前两个数组复制0 和 1
- 第三步，进行循环遍历，第 n 个数 = 第 n-1 个数 + 第 n-2 个数，然后存起来
- 第四步，将数组下标为 n 的数字返回
- 代码如下：
class Solution {
public int fib(int n) {
int[] ans = new int[105];
ans[0] = 0;
ans[1] = 1;
if(n==0)
return 0;
if(n==1)
return 1;
for(int i=2;i<=n;i++){
ans[i] = (ans[i-2] + ans[i-1])%1000000007;
}
return ans[n];
}
}
- 但是你想想，如果第 n 个数足够大，那岂不是要创建一个很大的数组，但是数组除了第 n-1 个数和第 n-2 个数是有用的，之前的都是没用的，所以我们使用双指针法
- 使用两个指针分别指向第 n-1 个数和第 n-2 个数，然后每次循环就替换这两个指针
- 代码如下：
class Solution {
public int fib(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
int pre = 0;
int cur = 1;
int sum = 0;
for(int i=2;i<=n;i++){
sum = (pre + cur)%1000000007;
pre = cur;
cur = sum;
}
return sum;
}
}
第二种方法：递归法
- 虽然我觉得上面的方法足够简便，并且时间和空间都挺好，但是我还是要说这种递归算法，可能性能不如上面的，但是思想还是要学习一下
- 先看下图，斐波那契数列给划分下来，就类似于树结构
- 所以我们递归也很简单就是下面的代码，将结果分散下去：
class Solution {
public int fib(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
return fib(n-1) + fib(n-2);
}
}
- 但是这个代码还是有点不够好，因为我们做了很多的重复性操作，就如下图花了红圈的地方，我们可以用一个数组来保存，然后节省时间。
class Solution {
public static int[] cache = new int[101];
public int fib(int n){
if (0 == n || 1 == n)
return n;
if (0 != cache[n])
return cache[n];
cache[n] = (fib(n - 1) + fib(n - 2)) % 1000000007;
return cache[n];
}
}
总结
总体来说我还是更喜欢双指针的那种解法，因为更加简便，但是递归还是必学的，思想永远不会嫌多的。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/13210.html
