title:(网站建设),深圳网站制作哪家负责,万网搜官网,网站建设 总结LeetCode 剑指 Offer 10- I. 斐波那契数列
题目描述
写一个函数#xff0c;输入 n #xff0c;求斐波那契#xff08;Fibonacci#xff09;数列的第 n 项#xff08;即 F(N)#xff09;。斐波那契数列的定义如下#xff1a;
F(0) 0, F(1) 1 F(N) F(N - 1) F(N - …LeetCode 剑指 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 开始之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。
这道题是再正常的斐波那契数列的基础上加上取模1e97 其实就是很容易进入盲区我求出最后的结果在去取模就可以了当基数不是很大的时候这样想没错基数很大的时候按照上面的公式计算中间过程数量就会超过类型最大长度所以正确的做法是在处理过程中就取模这样就不会造成超时错误了 题解
c
class Solution {
public:int fib(int n) {if(n 0)return 0;vectorint ans(n 1);ans[0] 0;ans[1] 1;for (int i 2; i n; i) {ans[i] (ans[i - 1] ans[i - 2]) % 1000000007;}return ans[n];}
};Go
func fib(n int) int {const mod int 1e9 7if n 2 {return n}p, q, r : 0, 0, 1for i : 2; i n; i {p qq rr (p q) % mod}return r
}
