超全算法笔试-面试宝典.pdf
《超全算法笔试-面试宝典.pdf》由会员分享,可在线阅读,更多相关《超全算法笔试-面试宝典.pdf(193页珍藏版)》请在文库网上搜索。
1、免费刷题神器海量题目等你来挑战阿里云开发者“藏经阁”海量免费电子书下载一、算法思想71.1排序7算法笔试模拟题精解之“数组变换”7算法笔试模拟题精解之“打怪兽”91.2贪心11算法笔试模拟题精解之“最大边权和”11算法笔试模拟题精解之“最强的团队”13算法笔试模拟题精解之“Tom 爱吃巧克力”15算法笔试模拟题精解之“吃奶酪”17算法笔试模拟题精解之“一的个数”19算法笔试模拟题精解之“Bob 的花束”21算法笔试模拟题精解之“钱庄”23算法笔试模拟题精解之“移动射击”26算法笔试模拟题精解之“相似数组”29算法笔试模拟题精解之“过吊桥”32算法笔试模拟题精解之“完美排列”35算法笔试模拟题精
2、解之“采摘圣诞果”37算法比赛模拟题精解之“TairitsuandDynamicObjects”39算法笔试模拟题精解之“Codancer 的炸弹引爆”41算法笔试模拟题精解之“学习小组”43算法笔试模拟题精解之“恢复字符串”451.3DP/动态规划47算法笔试模拟题精解之“矩阵最小路径和”47目录4目录算法笔试模拟题精解之“寻找等比数列”49算法笔试模拟题精解之“字符配对”52算法笔试模拟题精解之“数组染色”54算法笔试模拟题精解之“连绵的群山”57算法笔试模拟题精解之“难住 Tom 的问题”60算法笔试模拟题精解之“变化的字符”63算法笔试模拟题精解之“跳房子”65算法笔试模拟题精解之“寒
3、假活动”67算法笔试模拟题精解之“最短路”70算法笔试模拟题精解之“codancer 上楼”72算法笔试模拟题精解之“木棒拼接”74算法笔试模拟题精解之“Codancer 的数组封印”77算法笔试模拟题精解之“Jerry 的异或运算”80算法笔试模拟题精解之“小明的数学作业”82算法笔试模拟题精解之“奇偶数列”841.4剪枝88算法笔试模拟题精解之“斐波那契字符数”881.5尺取法92算法笔试模拟题精解之“超级区间”92算法笔试模拟题精解之“调整数组”95算法笔试模拟题精解之“最优分组”98算法笔试模拟题精解之“破译密码”100二、数据结构1032.1图103算法笔试模拟题精解之“变换的密钥”
4、103目录目录算法笔试模拟题精解之“正三角塔”160算法笔试模拟题精解之“组队难题”163算法笔试模拟题精解之“2n 合体”165算法笔试模拟题精解之“平行线”167算法笔试模拟题精解之“叠叠高”169算法笔试模拟题精解之“公平”173算法笔试模拟题精解之“Tom 的手工课”175算法笔试模拟题精解之“填数问题”177算法笔试模拟题精解之“Jerry 的考验”179算法笔试模拟题精解之“超车”181算法笔试模拟题精解之“坏掉的时钟”185算法笔试模拟题精解之“期末考试”187算法笔试模拟题精解之“滑雪比赛”189一、算法思想1.1排序算法笔试模拟题精解之“数组变换”贡献者|猿圈简介:本题要分情
5、况讨论,根据不同的情况变换不同的解决方式。题目描述等级:中等知识点:排序、贪心查看题目:数组变换给出一个长度为n的数组,和一个正整数d。你每次可以选择其中任意一个元素ai将其变为ai+d或ai-d,这算作一次操作。你需要将所有的元素全部变成相等元素,如果有解,请输出最小操作次数,如果无解请输出-1。输入数字 n、数字 d,和一个长度为 n 的数组 a。1=n=100000,1=d=100,1=ai算法笔试模拟题精解之“数组变换”输出一个数字,表示最小的操作次数,如果无解输出-1。示例 1输入:523,5,7,1,9输出:6注意最优解为全部变为 5,共 1+0+1+2+2=6 次。解题方法:首先
6、判断无解的情况,可以发现ai,ai+d,ai-d在模 d 情况下的余数不会发生改变,因此如果原数组中的存在任意两个数字它们对 d 取余结果不同,那么此时无解。设余数为 r。判断完无解之后,需要求出最小值。先将数组 ai 排序,然后除以 d,得到从 r 变成 ai 需要的步数。枚举元素 ai,将所有元素全部变成 ai 需要考虑两部分,i 之前和 i 之后:对于 i之前的元素,假设都是 r,那么需要(i-1)*ai,但是因为并不都是 0,所有我们可以用一个变量 val 存放前 i-1 项的和,然后我们在减去 val 就是前 i-1 个元素真正需要操作的步数。对于 i 之后的元素,也是类似的。我们假
7、设 i 之后的所有项和为 val,假设我们要将它们变为 r,则消耗即为 val,但是我们只需要将其变为 ai,因此需要减去(n-i)*ai。看完之后是不是有了答题思路了呢,快来练练手吧:数组变换算法笔试模拟题精解之“打怪兽”9算法笔试模拟题精解之“打怪兽”贡献者|郭达彬简介:根据题意,本题可使用贪心算法完成,策略是每次打怪兽都选择代价最小的一只。题目描述题目等级:容易知识点:排序、贪心查看题目:打怪兽现在有 3 只怪兽,他们的都有自己的血量 a,b,c(1=a,b,c算法笔试模拟题精解之“打怪兽”输出:6解题思路:贪心根据题意,本题使用贪心算法完成,策略是每次打怪兽都选择代价最小的一只。由于第
8、一次打怪兽的花费为 0,所以第一次可以打血量最小的(最大的也可以),接下来每次选择怪兽的时候就可以选择花费代价最小的。由于每次打怪兽的代价都是:当前怪兽的血量和上一个怪兽的血量的差的绝对值。于是可以得出结论,最小代价为所有怪兽血量的最大值减最小值。时间复杂度:O(1)空间复杂度:O(1)趁热打铁,题目直达链接:打怪兽算法笔试模拟题精解之“最大边权和”111.2贪心算法笔试模拟题精解之“最大边权和”贡献者|郭达彬简介:根据题意,最终需要将 n 个点连通并达到最大边权,而边权为两个点的点权之和的一半,所以一个点加入连通图的最大边权就是和点权最大的点连通。题目描述题目等级:容易知识点:贪心查看题目:
9、最大边权和现在有 n 个点(1=n=1000),每个点都有一个值称为点权 ai(ai 为偶数,1=ai算法笔试模拟题精解之“最大边权和”2,4,6,8,10输出:30解题思路:贪心根据题意,最终需要将 n 个点连通并达到最大边权,而边权为两个点的点权之和的一半,所以一个点加入连通图的最大边权就是和点权最大的点连通。因此想要得到最大边权和,只要所有点都与点权最大的点相连即可。实现过程中,首先求出最大的点权,然后计算出其他点与这个权值最大的点的边权之和即可。时间复杂度:O(n)空间复杂度:O(1)看完之后是不是有了想法了呢,快来练练手吧 查看题目:最大边权和算法笔试模拟题精解之“最强的团队”13算
10、法笔试模拟题精解之“最强的团队”贡献者|郭达彬简介:根据题意,最强团队即团队中每个小队的能力值都是最高的。即解决这道题需要找出数组中连续最大值的个数,若有多个连续最大值,选择个数最多的。题目描述题目等级:简单知识点:贪心查看题目:最强的团队有一个阵营,里面有 n 个小队(1=n=100),每个小队都有他们的能力值ai(0算法笔试模拟题精解之“最强的团队”1,2,3,3,2,1输出:2解题方法根据题意,最强团队即团队中每个小队的能力值都是最高的。即解决这道题需要找出数组中连续最大值的个数,若有多个连续最大值,选择个数最多的。具体实现时,可以先找出数组中最大的能力值是多少,然后设置一个标记 tag
11、。接着遍历数组,比较每个数组元素和最大值,数组元素等于最大的值的时候,将 tag标记为 1,数组元素不等于最大值时,将 tag 置为 0。在 tag 等于 1 时统计连续最大值的数量,若统计到多个最大值,则记录最大的那个。时间复杂度:O(n2)空间复杂度:O(1)看完之后是不是有了想法了呢,快来练练手吧 查看题目:最强的团队算法笔试模拟题精解之“Tom 爱吃巧克力”15算法笔试模拟题精解之“Tom 爱吃巧克力”贡献者|郭达彬简介:根据题意,可以得知这道题可以运用贪心算法,策略是每次都去买最便宜的巧克力。题目描述题目等级:容易知识点:贪心查看题目:Tom 爱吃巧克力Tom 非常喜欢巧克力,他上次
12、买的巧克力吃完了,所以他打算再去买 k 块巧克力回来(1=k=1e5),他又是一个非常节俭的一个人,所以他想花最少的钱去买巧克力。现在有 n 家卖巧克力的店(1=n=1e5),每个店的巧克力都限购 bi 块(最多只能买 bi 块,1=bi=1e5),每块的价格是 ai(1=ai=1e9),请问 Tom 买 k 块巧克力最少要花多少钱?题目保证 n 个 bi 的总和大于等于 k。输 入 卖 巧 克 力 的 店 的 个 数 n(1=n=1e5);打 算 去 买 的 巧 克 力 块 数k(1=k算法笔试模拟题精解之“Tom 爱吃巧克力”示例 1输入:254,5,2,4输出:12解题思路:贪心根据题意
13、,可以得知这道题可以运用贪心算法,策略是每次都去买最便宜的巧克力。由于题目给的二维数组是乱序的,可以根据巧克力的价格对二维数组从小到大进行排序,便于Tom选择最便宜的巧克力。Arrays类中只提供了一维数组的排序,如果要用 Arrays 对二维数组排序,需要重写 Comparator 里的 compare 方法。排序完成后,接下来操作就比较简单了。遍历数组,优先买便宜的巧克力,直到达到限购块数,再去下一家巧克力店。最终买到k块巧克力时Tom花的钱最少。时间复杂度:O(n)空间复杂度:O(1)看完之后是不是有了想法了呢,快来练练手吧 查看题目:Tom 爱吃巧克力算法笔试模拟题精解之“吃奶酪”17
14、算法笔试模拟题精解之“吃奶酪”贡献者|郭达彬简介:根据题意,如果要花费最少时间,则每个奶酪都让离奶酪最近的人去拿,因此,坐标=50001 的奶酪让 Jerry 去拿。题目描述题目等级:容易知识点:贪心、枚举查看题目:吃奶酪Tom 和 Jerry 都很喜欢吃奶酪,现在有 n 块奶酪散落在坐标轴上(1=n=100000),他们分别在 a1,a2,a3.an(1=ai算法笔试模拟题精解之“吃奶酪”输出:20000解题方法根据题意,如果要花费最少时间,则每个奶酪都让离奶酪最近的人去拿,因此,坐标=50001 的奶酪让 Jerry 去拿。具体实现时,可以设置一个 time 值,然后遍历数组。判断每一块奶
15、酪的坐标范围,根据坐标判断应该让谁拿,再计算拿到这个奶酪需要多长时间,如果时间大于time,则用这个值替换掉 time 的值。用这种方法,遍历整个数组后的 time 值即为Tom和Jerry拿到所有奶酪所用的最短时间。时间复杂度:O(n)空间复杂度:O(1)看完之后是不是有了想法了呢,快来练练手吧 查看题目:吃奶酪算法笔试模拟题精解之“一的个数”19算法笔试模拟题精解之“一的个数”贡献者|郭达彬简介:根据题意,本题的所有数字应从二进制角度考虑。题目描述题目等级:容易知识点:位运算、贪心查看题目:一的个数给你两个数字 l、r,问在区间 l,r 内的所有数中,二进制表示下“1”的个数最多的一个数是
16、多少,如果有多个相同的,输出所有符合条件的数中最小的一个数。输入一个整数 l,和一个整数 r。(1=l=r算法笔试模拟题精解之“一的个数”解题思路:二进制根据题意,本题的所有数字应从二进制角度考虑。所求数字可分为两部分,高位部分和低位部分,高位部分的值等于 l,r 高位相等的部分,在区间 l,r 中的所有数的高位部分都应该与其相等,即high=r&(-1低位的部分计算过程如下:如果r-high的值的二进制全为 1,则低位部分为r-high。如果不是全为 1,则低位部分为(1 查看题目:一的个数算法笔试模拟题精解之“Bob 的花束”21算法笔试模拟题精解之“Bob 的花束”贡献者|洪浩原简介:本
17、题充分理解题意后,直接模拟这个“选取最大值”的过程就可以得到结果了。题目描述等级:中等知识点:贪心查看题目:Bob 的花束Bob 和 Alice 是青梅竹马。今天,Bob 终于要鼓起勇气向 Alice 表白了!说到表白,自然是少不了买花了。Bob 来到了花店,花店一共提供了 9 种花,每一种花都有对应的价钱。但是 Bob 的零花钱有限,不能把所有的花都买下来送给 Alice。为了方便挑选,Bob 给这 9 种花分别标号 1-9,Bob 希望买到的花按照编号可以排出尽可能大数字,请问 Bob 能够排出的最大的数字是多少?输入一个正整数 value,代表 Bob 拥有的零花钱。(0=value=1
18、06)和有 9 个数字的数组 a,ai 代表第 i 种花的价格。(1=ai=105,1=i算法笔试模拟题精解之“Bob 的花束”示例 1输入:29,11,1,12,5,8,9,10,6输出:33注意:花店的每一种花都可以视为无限多。解题方法:模拟选花过程本题充分理解题意后,直接模拟这个“选取最大值”的过程就可以得到结果了。首先,选取最大值,意味着首先这个结果的“位数”要足够多,比如假设所有的花价格都是 1 元钱,则 11111111 是花 9 块钱能买到的最大值,而不是 333 或者 9这样的方案。这样相当于根据输入,输出的位数可以用很小的时间代价来确定:“用可用钱数,除以最便宜的花的价格,并
19、向下取整”。假设这里的位数为 m。其次,在位数确定的情况下,高位数字越大,结果也就越大,比如同样是 8 元钱,只能购买价格为 5 的 5 号花,和价格为 3 的 3 号花时,购买 35 就是最差的方案,而 53 才是正确答案。而且因为每个花的数量是无限的,所以可以模拟这个“从高位开始,逐个选取能买得起的最大的数字;同时每选完一位后,要确保剩下的钱,依旧可以买到 m 位数字的组合方案。”提示:根据上面逻辑写出的答案,在充分理解优化后,至少可以达到 2 遍扫描数组得到结果。时间复杂度:O(9n)看完是不是有了新思路了呢,快来试一下吧:查看题目:Bob 的花束算法笔试模拟题精解之“钱庄”23算法笔试
20、模拟题精解之“钱庄”贡献者|张鹏飞简介:可以先分析示例是如何实现的,以此为突破点。题目描述等级:中等知识点:贪心查看题目:钱庄钱庄每天能够收到很多散钱,第 i 个散钱的值 2wi。为了便于管理,钱庄每天都会向中央银行申请兑换钱币,假设钱庄有一些散钱使得 2k1+2k2+.+2km=2x(x 为非负整数),那么就可以将这些散钱兑换成一个大钱币,问在钱庄收到的这些散钱最终最少能变成几个钱币?输入一个整数 n,表示一共有 n 个钱币(1=n=106);再输入 n 个整数 wi,表示有价值 2wi(0=wi算法笔试模拟题精解之“钱庄”输出:1注意21+21+22+23=24,因此兑换后最少为一个钱币解
21、题思路一大致思路:对于 1,1,2,3 样例,答案 1 是怎么算出来的?按照题目的思路,应该这样算:21+21+22+23=24,因此为 1,但是如果这样做,肯定会超时,我是这样算的:对于底数为 2 幂数相同的两个数想加,是不是底数不变,幂加 1,因此两个 1 组成一个 2,此时共有两个 2,这两个 2 组成一个 3,此时共有两个 3,两个三组成一个 4,最后只剩一个 4,因此答案为 1.具体过程:遍历一遍 m 找出 m 中的最大数 max,定义一个数组 arrmax+2,用于统计出 m 数组中,每个数字出现的次数,即 arrmi+(m 中的元素为下标,arr 数组中保存出现的次数);再次遍历
22、 arr 数组(0=i=max),如果当前元素 arri=0,那就下一个,如果不为 0,arri+1+=arri/2;(每两个 arri 就能凑一个 arri+1)如果 arri 为奇数,那说明剩余一个 arri,这最后也就剩下了,所以 ans+;遍历完后 if(arrmax+1!=0)ans+;然后 returnans;注意:加粗部分一定要理解解题思路二:贪心遍历钱币数组 m,只要数组中的当前元素 x 可以兑换一个大金币(有两个以上相同的钱币)就自底向上兑换,直到无法兑换;算法笔试模拟题精解之“钱庄”25遍历结束后,对剩下的钱币个数做统计(而上述操作保证了所有钱币均不可兑换);复杂度分析空间
23、复杂度开辟了 100000 大小的 map 数组(因为价值 wi 取值为:0=wi 查看题目:钱庄26算法笔试模拟题精解之“移动射击”算法笔试模拟题精解之“移动射击”贡献者|张鹏飞简介:首先理解题意,题目说的“发动之后只能改变一次方向”是干扰你的,因为即使你在中间过程中左右摆,但宏观上还是最多改变了一次方向。题目描述题目等级:中等知识点:DP查看题目:移动射击你正在数轴上跟小精灵对战。你拥有一个十分强力的技能称为移动射击,但是这个技能有一个缺点是在你发动之后只能改变一次方向。你可以认为你的位置在数字 0 的位置上,在数轴的正方向上有 n 只精灵,负方向上有 m 只精灵。移动射击可以造成 w 点
24、伤害。每个精灵都有自己的血量,当血量降为 0 时死亡。在最开始时你可以选择向正方向或负方向释放移动射击,并且可以在任意时刻改变技能的方向。请问你最多可以击杀多少只小精灵?(n,m,w 以及精灵的血量均在1,100000 范围内)输入内容为五个,前三个为三个数字:正方向上的精灵个数 n、负方向上的精灵个数 m,移动射击可以造成的伤害 w;第四个是一个长度为n的数组a,表示正方向上的 n 个精灵的血量;第五个是一个长度为m的数组b,表示负方向上的 m 个精灵的血量。算法笔试模拟题精解之“移动射击”=w 的时候,记住此时的位置 index_a=i,退出循环,退出后加上这句if(i=n|aiw)ind
25、ex_a-;因为 index_a 指向的是刚好不超过 w 的位置,而且不能越界。对 b 数组也是如此,然后开始从 index_a 往后一步一步走;走一步,看看 b 数组的情况,k 为 b 数组的下标,初始 k=0;28算法笔试模拟题精解之“移动射击”while(km&ai+bk=w)k+;然后和当前最长的长度比较ans=Math.max(ans,i+k+1);当 index_a 一直走到底,可返回 ans.看完之后是不是有了想法了呢,题目直达链接:查看题目:移动射击算法笔试模拟题精解之“相似数组”29算法笔试模拟题精解之“相似数组”贡献者|张鹏飞简介:要解出相似数组的最长长度,即要求相似数组中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 笔试 面试 宝典