lintcode 949. 斐波那契数列 II

1.题目2.解题思路及lintcode python代码3.进一步改进

1.题目

希望这是关于斐波那契数列终极一博。

2.解题思路及lintcode python代码

通过矩阵相乘来实现，如果按顺序两两相乘，会占据大量内存空间，同时执行效率很低。这里要借鉴分治的思想，n个相同矩阵相乘=n/2矩阵*n/2矩阵=n/4…分——治——综合。

python实现代码如下：

class Solution: """ @param n: an integer @return: return an int """ def time(self,arr): a,b,c=arr[0][0],arr[0][1],arr[1][1] p,q,r=a**2,b**2,c**2 m=b*(a+c) return [[p+q,m],[m,q+r]] def d_c(self,k): A=[[1,1],[1,0]] if k==1:return A # if k==2:return self.time(A,A) if k%2==0: return self.time(self.d_c(k//2)) else: B=self.time(self.d_c((k-1)//2)) return [ [B[0][0]+B[1][0],B[0][1]+B[1][1]], [B[0][0], B[0][1] ]] def lastFourDigitsOfFn(self, n): # write your code here if n==0:return 0 elif n==1:return 1 elif n==2: return 1 res=self.d_c(n) return int(str(res[0][1])[-4:])

看起来是不是很简明~ 为了提高执行效率， 根据矩阵A[0,1]和A[1,0]位置元素相同，time(self,arr)进行了适当的优化，但即使是这样，最终结果依然是我们不太希望的： Time Limit Exceeded

3.进一步改进

考虑到本题只是让我们求出后四位，而对于高于低四位的元素，对于前四位的整数“+”或者“X”运算是不影响的。 因此在time()子函数中，下列程序只保留了数字的低四位。

class Solution: """ @param n: an integer @return: return an int """ def time(self,arr): a,b,c=int(str(arr[0][0])[-4:]),int(str(arr[0][1])[-4:]),int(str(arr[1][1])[-4:]) p,q,r=a**2,b**2,c**2 m=b*(a+c) return [[p+q,m],[m,q+r]] def d_c(self,k): A=[[1,1],[1,0]] if k==1:return A # if k==2:return self.time(A,A) if k%2==0: return self.time(self.d_c(k//2)) else: B=self.time(self.d_c((k-1)//2)) return [ [B[0][0]+B[1][0],B[0][1]+B[1][1]], [B[0][0], B[0][1] ]] def lastFourDigitsOfFn(self, n): # write your code here if n==0:return 0 elif n==1:return 1 elif n==2: return 1 res=self.d_c(n-1) return int(str(res[0][0])[-4:])

运行速度就嗖嗖的上来了，成功通过，并有幸暂居榜首。 路过的小伙伴，若对您有所帮助，请不吝点赞~