解法一
题中要求的是 空间复杂度 O(1) ,很明显使用递归是行不通的,我们先改成非递归的看一下(这种复杂度也是不行的,我们先看一下代码)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int[] dp = new int[num + 1];
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= num; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
System.out.println(dp[num]);
}
}
通过上面代码我们可以看到当前值只和数组的前两个值有关,在往前面的就无关了,所以我们没必要申请一个数组,直接使用两个变量即可,这样空间复杂度就满足要求了
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int first = 1;
int second = 1;
int temp;
for (int i = 3; i <= num; i++) {
temp = second;//先把变量second保存起来
second = first + second;
first = temp;
}
System.out.println(second);
}
解法二
斐波那契数列又称黄金分割数列,他有很多的特性,比如跳台阶,兔子的繁殖等,他的通项公式如下,我们还可以通过公式来计算
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//这里要注意斐波那契数列的前两项,有的是0,1开头,有的是1,1开头,还有的是1,2开头,根据
//前两项不同而作调整
int num = in.nextInt() - 1;
double sqrt5 = Math.sqrt(5);
double fib = Math.pow((1 + sqrt5) / 2, num + 1) - Math.pow((1 - sqrt5) / 2, num + 1);
System.out.println((int) Math.round(fib / sqrt5));
}
}
解法三
因为题中说了n
的最大值是40
,我们可以把它都列出来
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int[] fib = {1,
1,
2,
3,
5,
8,
13,
21,
34,
55,
89,
144,
233,
377,
610,
987,
1597,
2584,
4181,
6765,
10946,
17711,
28657,
46368,
75025,
121393,
196418,
317811,
514229,
832040,
1346269,
2178309,
3524578,
5702887,
9227465,
14930352,
24157817,
39088169,
63245986,
102334155};
System.out.println(fib[num - 1]);
}
}
看一下运行结果
我把部分算法题整理成了PDF
文档,截止目前总共有1000多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ 提取码:6666