剑指 Offer 10- I. 斐波那契数列
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
输入:n = 2
输出:1
示例 2:
输入:n = 5
输出:5
解题思路
- 用数组记录 f(n) 的值,循环 n 次,最后取 nums[n]
- 用数组记录 f(n) 的值,递归计算 f(n) = f(n - 1) + f(n - 2)
- 定义三个变量,分别存储 f(n + 1) f(n) f(n - 1),循环 n 次,每次循环中 sum = f(n) + f(n - 1),再交换 f(n - 1) = f(n) f(n) = sum。其中循环从 0 开始并直接 return a 就不用判断 0 和 1。
tip:要取余
代码
解法一
class Solution {
public int fib(int n) {
if (n < 2) return n;
int nums[] = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
for (int i = 2; i <= n; i++) {
nums[i] = (nums[i - 1] + nums[i - 2]) % 1000000007;
}
return nums[n];
}
}
解法二
class Solution {
int[] nums;
public int fib(int n) {
if (n == 0 || n == 1) return n;
nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
return recuv(n);
}
public int recuv(int n) {
if (n < 2) return n;
recuv(n - 1);
return nums[n] = (nums[n - 1] + nums[n - 2]) % 1000000007;
}
}
解法三
class Solution {
public int fib(int n) {
int a = 0;
int b = 1;
int sum = 0;
for (int i = 0; i < n; i++) {
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return a;
}
}
本文由 Meridian 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Feb 11,2022