首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

Fibonacci II

949. Fibonacci II

描述

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:0,1,1,2,3,5,8,13,21,34,…

An alternative formula for the Fibonacci sequence is:

Given an integer n, your goal is to compute the last 4 digits of Fn

1.0 ≤ n ≤ 1,000,000,000

2.If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros(print Fn mod 10000)

样例

Given: n =

Return:

思路:数组保存每个数字的4位尾数,叠加计算到数组末尾。

ifn==:

return

ifn==1:

return1

numbers = [forxinrange(n+1)]

numbers[]=

numbers[1]=1

forxinrange(2,n+1):

numbers[x]=(numbers[x-1]%10000+numbers[x-2]%10000)%10000

运行结果:

超过了空间限制,5531354,数字挺大的..要考虑是否有循环的可能了。

以100000为限进行一下测试,查找连续2个1存在的位置:

发现4位尾数以15000为单位进行循环。头一次知道Fibonacci数列里有循环...

那就把n对15000求余。

ifn==:

return

ifn==1:

return1

ifn>=15000:

n = n%15000

numbers = [forxinrange(n+1)]

numbers[]=

numbers[1]=1

forxinrange(2,n+1):

numbers[x]=(numbers[x-1]%10000+numbers[x-2]%10000)%10000

returnstr(numbers[n])

运行结果:

在该题Python语言排行榜中,第一名的运行时间是50ms,后面都要500多ms了,不明白是怎么做到的。

我直接把前15000个数放进数组直接查询,运行结果也要540ms左右......

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180427G0NA3I00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券