笔试算法模拟题精解之”斐波那契字符数”-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

笔试算法模拟题精解之”斐波那契字符数”

简介: 本题应充分利用斐波那契数列的性质,自顶向下对问题逐步剪枝,定位需要判断的数字位置。
+关注继续查看

【在线编程产品介绍】

阿里云开发者社区在线编程:

免费刷题大神器,助你拿到好offer

周赛月赛不停歇,做题还能领奖品

大赛笔试全真题,常做常新有惊喜

点击链接开始产品体验:https://developer.aliyun.com/coding

本文为大家介绍的是“55.斐波那契字符数”的解法探究。先来看一下题目内容:

题目详情:

等级:中等
知识点:递归、剪枝

查看题目:斐波那契字符数

Tom发现了一种神奇的字符串-斐波那契字符串,定义f[1]=0,f[2]=1,对于所有的i>2都有f[i]=f[i-2]+f[i-1],其中“+”代表拼接,比如01+10=0110,现在对于字符串f[n],请判断f[n]的第k项是0,还是1。
输入两个数字n和k(n<=300,k<=1000000000)。
输出f[n]的第k位,如果k大于f[n]的位数,则输出-1。

本题在答题过程中很多小伙伴反应会出现超内存的现象,导致JVM崩溃。但其实这道题目是不可以暴力解题的,首先来看一下一般思路解法。

方法1:直接法(超时并超出内存限制)


这是一道找规律的题目,最简单的想法可以是自底向上地构建出从第一个字符串f[1]直到最后的f[n],然后查看f[n]的第k项是0还是1。

由于斐波那契数递增速度非常快,当n较大时,这种暴力拼接法无法完成。

下面介绍一种优化的算法。

方法2:找规律(提交通过)


本题应充分利用斐波那契数列的性质,自顶向下对问题逐步剪枝,定位需要判断的数字位置。

比如,对输入n=19, k=98:

  1. 先算出n=19对应的字符串长度len,也就是斐波那契数列的第19项。考虑到k是int类型,故可以先算出n=1~47对应的斐波那契数组成的数组(n=47时,斐波那契数大于2^31-1,无需再提前计算更多的斐波那契数),然后直接在计算好的斐波那契数组中取出第19项。
  2. 找到n-2=17,n-1=18对应的斐波那契字符串长度(也就是第17/18个斐波那契数)len1,len2。同样也是在提前计算好的斐波那契数组中找到。
  3. 对于k=98,如果k>len1,说明要找的数字在n=18对应的斐波那契字符串中,也就是n=19对应的斐波那契字符串的后半部分;如果k<=len1,说明要找的数字在n=17对应的斐波那契字符串中,也就是n=19对应的斐波那契字符串的前半部分。
  4. 根据判断结果,将n赋值为n-2或n-1,同时将k赋值为k或(k-len1),完成剪枝。回到第1步,递归向下搜索。直到n=1或者2,这时k也变为1,定位完成,结束递归,直接返回结果。

进一步优化:

当输入的n > 47时,斐波那契字符串的长度超出了int型变量k的表示范围。需要提前进行推断剪枝。你能根据k的int表示范围(小于等于2^31-1)这一特性,对n较大的那些用例进行优化么?

方法3:递归

这个问题可以使用递归的方法来求解。
题目中给出了字符串拼接的规律:f[i]=f[i-2]+f[i-1]。可以看出对于第i个字符串,它的前半部分属于第i-2个字符串,后半部分属于第i-1个字符串。

这样,当给定具体的n和k时,我们可以首先判断k位于第n个字符串的前半部分还是后半部分,然后递归的把k传递给第n-2或n-1个字符串。

计算过程:

  1. 为了判断属于前半部分还是后半部分,需要计算每一个字符串的长度。
    一个len数组。每个位置为对应字符串的长度。

len[1] = len[2] = 1;
len[i] = len[i-2]+len[i-1];

  1. 如果k > len[n],则输出-1。
  2. 设置递归函数 int find(int i, int k);这个函数返回第i个字符串中k个位置的字符
  3. 判断k在前半部分还是后半部分。
    a) K <= len[i-2] 前半部分,调用find(i-2, k)

b) K > len[i-2] 后半部分,调用find(i-1, k-len[i-2])

上面的计算在第一步时会遇到问题,当n大于几十的时候,len就会超出int的范围。
对这个问题的解决基于对递归过程的观察,第4步a)中k始终是不变的,i的奇偶性也保持不变。所以在计算第1步len时可以提前停止,当发现len[i]>=k且i与n的奇偶性相同时。第4步中的递归起始也可以使用第i个字符串开始,而不是第n个。
时间复杂度O(2*n)
空间复杂度O(n)

是不是感觉有思路了,立刻点击这里开启答题!

算法题目的解法并不唯一,这里介绍部分解题思路给大家,希望可以给大家启发~

在线编程周赛、月赛火热进行中,更有限时答题活动,社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情:在线编程内测中,抢先周赛赢好礼!面试考试前,快来刷刷题!

APPbanner784-312.png

下一篇:笔试算法模拟题精解之“坏掉的时钟”

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
948 0
进化算法可以不再需要计算集群,开普敦大学的新方法用一块GPU也能刷新MNIST记录
他们实验中只使用了一块GTX1070 GPU,训练时间6到24小时,就可以取得这样的成果,他们觉得非常满意。他们的研究也首次尝试了把神经进化用在一维卷积网络的创造中,用来解决情感分析、包括嵌入层的优化问题。
1297 0
算法:字符串消除问题的数学证明
问题: 给定一个字符串,仅由A、B、C3个字母组成。当出现连续两个不同的字母时,你可以用另外一个字母替换它,如有AB或BA连续出现,你把它们替换为字母C;有AC或CA连续出现时,你可以把它们替换为字母B;有BC或CB连续出现时,你可以把它们替换为字母A。
470 0
《数字视频和高清:算法和接口》一第2章 图像的采样和显示
本节书摘来华章计算机《数字视频和高清:算法和接口》一书中的第2章 , [加]查尔斯·波因顿(Charles Poynton)著 刘开华 褚晶辉 马永涛 吕卫 宫霄霖 等译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。
688 0
算法导论第十九章 斐波那契堆
  《算法导论》第二版中在讨论斐波那契堆之前还讨论了二项堆,但是第三版中已经把这块的内容放到思考题中,究极原因我想大概是二项堆只是个引子,目的是为了引出斐波那契堆,便于理解,而且许多经典的算法实现都是基于斐波那契堆,譬如计算最小生成树问题和寻找单源最短路径问题等,此时再把二项堆单独作为一章来讲显然没有必要。
868 0
《数字视频和高清:算法和接口》一2.5面向消费者的视频获取
本节书摘来华章计算机《数字视频和高清:算法和接口》一书中的第2章 ,第2.5节, [加]查尔斯·波因顿(Charles Poynton)著 刘开华 褚晶辉 马永涛 吕卫 宫霄霖 等译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。
769 0
算法题——投篮比赛获胜概率问题
问题描述: 甲乙两人比赛投篮。约定甲先投篮,每人投篮投进一球,则继续投球,若投失一球,则换人投球。初始积分为1分,甲每投进一球,积分加1分;乙每投进1球,积分减1分。若积分达到N分(N>1),甲获胜;若积分减至0分,乙获胜。
733 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载