合辑 | 七道典型笔试算法模拟题精解-阿里云开发者社区

开发者社区> 算法编程> 正文

合辑 | 七道典型笔试算法模拟题精解

简介: 阿里云开发者社区在线编程频道部分题目解析合辑,涉及“模拟”、“贪心”、“排序”等算法知识。

阿里云开发者社区在线编程,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器

题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,技术人刷题进阶必备工具!

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

本文为大家集合了其中的七道典型笔试算法模拟题精解,进阶就在此刻!

1.斐波那契字符数
题目概述: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?
题解简述:这是一道找规律的题目,最简单的想法可以是自底向上地构建出从第一个字符串f[1]直到最后的f[n],然后查看f[n]的第k项是0还是1。

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

下面介绍一种优化的算法:本题应充分利用斐波那契数列的性质,自顶向下对问题逐步剪枝,定位需要判断的数字位置...点击链接查看详细解法:笔试算法模拟题精解之”斐波那契字符数”

2.完美排列
题目概述:完美排列的定义为一个长度为n的数组,n个元素各不相同且每个元素均在[1,n]的范围内。
现在给你长度为n的数组,你每次可以进行如下操作:任选数组中的一个元素,将其加一或者减一,问最少需要多少次操作才能够使得该数组为一个完美排列?
题解简述:本题是一道典型的贪心算法题,问题可以通过每步的最优策略分治解决。如果将 n 个大小未知的正整数,通过题目中的规则“填充”到槽 1~n 中,我们不妨从最小的数字槽 1 开始做起。

显然,这 n 个正整数中最小的数字 a(无论这个最小的数字是 1 或是 100),是填充槽 1 的最佳选择。其它(n-1)个数字和 1 的“距离”,都必定大于等于 a,距离槽 1 的距离都不如 a 更优,所以可以将 a 填充进槽 1,并在后续选择中排除掉它。

当填充槽 2 时,依旧用上面的思路就可以了。用剩下的(n-1)个数字中最小的数字去通过加减 1 进入槽 2,必定是填充槽 2 所有方式中的最佳策略。

将上面的思路重复应用,就得到了结果。复杂度上需要扫描 n 次数组。
但是上面的反复扫描非常浪费时间,文章还为大家提供了一种更加优化的思考方法,快来一探究竟吧!笔试算法模拟题精解之“完美排列”

3.坏掉的时钟
题目概述:B同学有一个时钟,能够显示1-d,初始值为1。这个时钟每天显示的数字加一,特殊的,当某天显示的值为d时,第二天就会显示1。
但是每个月的时间并不总是d天,因此B同学就要通过手动调整使得显示的时间正确,每次手调都可以使显示数字加一。
现在给你n个月每月的天数,请你计算一下若是让时钟每天显示的数字都是正确的,他这n个月一共需要调多少次时钟?
题解简述:本题关键在于理解题意:题干的含义是,在除去最后一个月后,其余每个月的最后一天的24点时,时钟上的逻辑时间会超过那个月的最大天数,同时实际时间变为下一个月的第1天。此时逻辑时间和实际时间有差别,需要调整时钟,让逻辑时间重新回到1,使其符合实际时间。
那么具体是怎么解题的呢,点进链接查看详情:笔试算法模拟题精解之“坏掉的时钟”

4.Bob的花束
题目概述:Bob和Alice是青梅竹马。今天,Bob终于要鼓起勇气向Alice表白了!说到表白,自然是少不了买花了。Bob来到了花店,花店一共提供了9种花,每一种花都有对应的价钱。但是Bob的零花钱有限,不能把所有的花都买下来送给Alice。
为了方便挑选,Bob给这9种花分别标号1-9,Bob希望买到的花按照编号可以排出尽可能大数字,请问Bob能够排出的最大的数字是多少?
题解简述:本本题充分理解题意后,直接模拟这个“选取最大值”的过程就可以得到结果了。

首先,选取最大值,意味着首先这个结果的“位数”要足够多,比如假设所有的花价格都是1元钱,则11111111是花9块钱能买到的最大值,而不是333或者9这样的方案。这样相当于根据输入,输出的位数可以用很小的时间代价来确定:“用可用钱数,除以最便宜的花的价格,并向下取整”。假设这里的位数为m。

其次,在位数确定的情况下,高位数字越大,结果也就越大,比如同样是8元钱,只能购买价格为5的5号花,和价格为3的3号花时,购买35就是最差的方案,而53才是正确答案。而且因为每个花的数量是无限的,所以可以模拟这个 “从高位开始,逐个选取能买得起的最大的数字;同时每选完一位后,要确保剩下的钱,依旧可以买到m位数字的组合方案。”根据上面逻辑再进行优化就可以写出答案啦,快来一探究竟吧:笔试算法模拟题精解之“Bob的花束”

5.最优分组
题目概述:给出一个长度为 n 的数组和一个数字 k ,你需要在数组中选出一些数字,这些数字两两之间的差值不能超过k。你需要判断最多能够挑出的数字个数。(n在[1, 100000]之间,k和数组中的数字在[1,1000000000]之间)?
题解简述:一组数字,在不改变顺序的情况下,每相邻两个数字之间的差值是确定的。在这个思路的引导下,先对数字进行排序,对排序后的新序列进行遍历即可解答出本题目啦,戳链接查看思路详情吧:笔试算法模拟题精解之“ 最优分组”

6.超车
题目概述:一天某地在举行公路自行车比赛,一共有n名选手参加(2<=n<=100000),在比赛的过程中,有一段路程观众是看不见的,现在给你了选手进入这段路程的顺序编号,又给了选手出这段路程的顺序编号(顺序按照先进先出的原则,编号为1-n),请你计算一下,有多少名选手在这段公路上完成了超车(出路段后超过了进路段前在自己前面的选手)?
题解简述:根据题意,超车意味着对于入洞前序列中的每辆车x及x前面的车集合{a,b,c,d...},如果在出洞序列中,发现x前面的某车,出洞时不在{a,b,c,d...}集合中,就说明x超过了这辆不在{a,b,c,d...}集合中的车。而且这个超车行为与其他车无关,也就是说,即使上面个的清空中x的排名后撤了,被其它车超过了,它也依然被视为发生了超车。“只要超过了一辆车,就算发生了超车”。

根据上面思路,首先需要遍历入洞序列,对每辆车x遍历,同时用一个列表记录下入洞序列中x前面的车。对这样的x和列表,再去出洞序列中从尾部开始遍历,直到发现x停止。如果遍历出洞序列的过程中,发现某车存在于列表中,说明这辆车入洞前在x的前面且出洞后在x的后面,发生了超车,此时令结果加1。

如果简单应用这种代码,不加优化,会有嵌套循环,时间复杂度很高,不能通过。

上面的思路中,耗时最多的部分,就是内循环的判断,按照此思路批量判断超车,就将大大地提高内循环的效率...点击查看优化算法笔试算法模拟题精解之“超车”的两种解法

7.Alice的01串
题目概述:Alice给了Bob一个字符串s,Alice想让Bob找出这个字符串中有多少个恰好包含了k个1的子串。请你帮助Bob计算出这些子串的个数是多少?
题解简述:根据题意,本题可以直接用双层循环扫描数组,找到所有的连续子串,查看每个组合是否拥有指定数量的1。点击链接查看详细题解:笔试算法模拟题精解之“Alice的01串”

持续更新中。。。更多内容请关注算法编程技术圈


另有在线编程周赛、月赛火热进行中!社区定制卫衣、双肩背包等你来拿~点击了解周赛详情:在线编程内测中,抢先周赛赢好礼!面试考试前,快来刷刷题!
b462f1d86b44481ca24c0ad63fe55948.png

【在线编程产品介绍】

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

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

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

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

点击查看:合辑 | 笔试算法模拟题精解系列(二)

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
官网链接