今日题目(剑指Offer系列)
剑指 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
解题思路:
>本题就是简单的循环 >可以最简单就是用递归去做,但是那样的话复杂度太高 >用循环相对于递归快很多
Python解法:
class Solution: def fib(self, n: int) -> int: if n<=1: return n else: first=0 second=1 for i in range(n-1): temp=first first=second second=(second+temp)%(1e9+7) return int(second)
Java解法:
class Solution { public int fib(int n) { if(n<=1) { return n; } else { double first=0; double second=1; for(int i=0;i<n-1;i++) { double temp=first; first=second; second=(second+temp)%(1e9+7); } return (int)second; } } }