LeetCode-斐波那契数用python解决的方法

1.通项公式法

斐波那契数的通项公式为：

因此：

import math class Solution(object): def fib(self, N): """ :type N: int :rtype: int """ a = math.sqrt(5) b = (1+a)/2 c = (1-a)/2 return (pow(b,N)-pow(c,N))/a

一行

import math class Solution(object): def fib(self, N): """ :type N: int :rtype: int """ return int((pow((1+math.sqrt(5))/2,N)-pow((1-math.sqrt(5))/2,N))/math.sqrt(5))

通项公式法花费24ms时间，不是最快的时间，最快的是4ms。

2.最快的是4ms

class Solution(object): def __init__(self): self.docker = {} def fib(self, N): """ :type N: int :rtype: int 斐波那契数列，使用递归 """ if self.docker.get(N) is not None: return self.docker[N] if (N == 2) or (N == 1): self.docker[1] = 1 self.docker[2] = 1 return 1 if N == 0: return 0 temp = self.fib(N - 1) + self.fib(N - 2) self.docker[N] = temp return temp

分析：

 

3.8ms

class Solution(object): def fib(self, N): """ :type N: int :rtype: int """ if N == 0: return 0 if N <= 2 : return 1 pre =1 ppre =1 for i in range(2,N): tem = pre pre = pre + ppre ppre = tem return pre

 

4.12ms

 

class Solution(object): def fib(self, N): """ :type N: int :rtype: int """ A = [0, 1] for i in range(N - 1): A.append(A[-1] + A[-2]) return A[N]

5.16ms

class Solution(object): def fib(self, N): """ :type N: int :rtype: int """ if N == 0: return 0 if N == 1: return 1 pre1 = 1 pre2 = 0 res = 0 for i in range(N-1): res = pre1 + pre2 pre2 = pre1 pre1 = res return res

 

6.20ms

class Solution(object): def fib(self,N): if N in [0, 1]: return N a, b = 0, 1 while N > 1: a, b = b, a + b N -= 1 return b