剑指Offer-斐波那契数列-Python
斐波那契数列
题目描述:
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39
思路1:
最普通的递归解法,虽然简洁,但是效率很低。因为里面有大量的重复运算,不实用。
实现:
def Fibonacci(self, n):
# write code here
if n <= 0:
return 0
elif n == 1:
return 1
else:
return self.Fibonacci(n-1) + self.Fibonacci(n-2)
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。——如何解决???
思路2:
实现2:
class Solution:
def Fibonacci(self, n):
# write code here
num1 = 0
num2 = 1
if n == 0:
return 0
elif n == 1:
return 1
for i in range(2, n+1):
temp = num1 + num2
num1 = num2
num2 = temp
return temp
分析:这样实现,占用内存很小。只有三个整型变量
实现2:
class Solution:
def Fibonacci(self,n):
# write code here
arr = [0,1]
while len(arr) <= n:
arr.append( arr[-1]+arr[-2] )
return arr[n]
分析:这样实现,简洁,占用一个数组的内存,需要保存每一个数字。