算法练习——斐波那契数

2021年1月4日LeetCode每日一题是509. 斐波那契数,这一题非常适合入门练习递归,题目所提供的实例很明显的就能看出递归形式,只需要思考在什么时候退出递归即可。附上第一次提交代码:

1
2
3
4
5
6
class Solution {
public int fib(int n) {
if(n < 2) return n; // n == 1也可以
return fib(n - 1) + fib(n - 2);
}
}

短短2行就完成这个算法,但是执行时间消耗太长了,因此想起用昨天那题看到的记忆递归来优化,也就是用一个大数组记住第n项的值,每次检查这个数组的第n项值是否大于0,大于0说明这个值已经求出来过,我们就不需要重新递归求一次了,消耗多一点内存就让他的时间复杂度大大降低了许多。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
static int[] mem = new int[100000];
static {
mem[0] = 0;
mem[1] = 1;
mem[2] = 1;
}
public int fib(int n) {
if(n < 2 || mem[n] != 0) return mem[n];
else mem[n] = fib(n - 1) +fib(n - 2);
return mem[n];
}
}

下面附上最后一次提交,使用长度为2的数组来完成这题:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int[] temp = new int[2];
temp[1] = 1;
int i = 2;
for(; i <= n; i++) {
temp[i % 2] = temp[0] + temp[1];
}
return temp[n % 2];
}
}

这样的题目非常简单,做法也好几种,对于没有形成递归思维的人来说,这题特别适合用作练习,然后更加深入的话就是记忆递归以及动态规划了,算法的思维不是天生的,勤以练习,终有一天能够看到自己努力的回报。