程序员面试宝典.pdf

一、算法思想71.1排序7算法笔试模拟题精解之“数组变换”7算法笔试模拟题精解之“打怪兽”91.2贪心11算法笔试模拟题精解之“最大边权和”11算法笔试模拟题精解之“最强的团队”13算法笔试模拟题精解之“Tom 爱吃巧克力”15算法笔试模拟题精解之“吃奶酪”17算法笔试模拟题精解之“一的个数”19算法笔试模拟题精解之“Bob 的花束”21算法笔试模拟题精解之“钱庄”23算法笔试模拟题精解之“移动射击”26算法笔试模拟题精解之“相似数组”29算法笔试模拟题精解之“过吊桥”32算法笔试模拟题精解之“完美排列”35算法笔试模拟题精解之“采摘圣诞果”37算法比赛模拟题精解之“TairitsuandDynamicObjects”39算法笔试模拟题精解之“Codancer 的炸弹引爆”41算法笔试模拟题精解之“学习小组”43算法笔试模拟题精解之“恢复字符串”451.3DP/动态规划47算法笔试模拟题精解之“矩阵最小路径和”47目录4目录算法笔试模拟题精解之“寻找等比数列”49算法笔试模拟题精解之“字符配对”52算法笔试模拟题精解之“数组染色”54算法笔试模拟题精解之“连绵的群山”57算法笔试模拟题精解之“难住 Tom 的问题”60算法笔试模拟题精解之“变化的字符”63算法笔试模拟题精解之“跳房子”65算法笔试模拟题精解之“寒假活动”67算法笔试模拟题精解之“最短路”70算法笔试模拟题精解之“codancer 上楼”72算法笔试模拟题精解之“木棒拼接”74算法笔试模拟题精解之“Codancer 的数组封印”77算法笔试模拟题精解之“Jerry 的异或运算”80算法笔试模拟题精解之“小明的数学作业”82算法笔试模拟题精解之“奇偶数列”841.4剪枝88算法笔试模拟题精解之“斐波那契字符数”881.5尺取法92算法笔试模拟题精解之“超级区间”92算法笔试模拟题精解之“调整数组”95算法笔试模拟题精解之“最优分组”98算法笔试模拟题精解之“破译密码”100二、数据结构1032.1图103算法笔试模拟题精解之“变换的密钥”103目录目录算法笔试模拟题精解之“正三角塔”160算法笔试模拟题精解之“组队难题”163算法笔试模拟题精解之“2n 合体”165算法笔试模拟题精解之“平行线”167算法笔试模拟题精解之“叠叠高”169算法笔试模拟题精解之“公平”173算法笔试模拟题精解之“Tom 的手工课”175算法笔试模拟题精解之“填数问题”177算法笔试模拟题精解之“Jerry 的考验”179算法笔试模拟题精解之“超车”181算法笔试模拟题精解之“坏掉的时钟”185算法笔试模拟题精解之“期末考试”187算法笔试模拟题精解之“滑雪比赛”189一、算法思想1.1排序算法笔试模拟题精解之“数组变换”贡献者|猿圈简介：本题要分情况讨论，根据不同的情况变换不同的解决方式。题目描述等级：中等知识点：排序、贪心查看题目：数组变换给出一个长度为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 次。解题方法：首先判断无解的情况，可以发现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 之后的元素，也是类似的。我们假设 i 之后的所有项和为 val，假设我们要将它们变为 r，则消耗即为 val，但是我们只需要将其变为 ai，因此需要减去(n-i)*ai。看完之后是不是有了答题思路了呢，快来练练手吧：数组变换算法笔试模拟题精解之“打怪兽”9算法笔试模拟题精解之“打怪兽”贡献者|郭达彬简介：根据题意，本题可使用贪心算法完成，策略是每次打怪兽都选择代价最小的一只。题目描述题目等级：容易知识点：排序、贪心查看题目：打怪兽现在有 3 只怪兽，他们的都有自己的血量 a,b,c(1=a,b,c算法笔试模拟题精解之“打怪兽”输出：6解题思路：贪心根据题意，本题使用贪心算法完成，策略是每次打怪兽都选择代价最小的一只。由于第一次打怪兽的花费为 0，所以第一次可以打血量最小的（最大的也可以），接下来每次选择怪兽的时候就可以选择花费代价最小的。由于每次打怪兽的代价都是：当前怪兽的血量和上一个怪兽的血量的差的绝对值。于是可以得出结论，最小代价为所有怪兽血量的最大值减最小值。时间复杂度：O(1)空间复杂度：O(1)趁热打铁，题目直达链接：打怪兽算法笔试模拟题精解之“最大边权和”111.2贪心算法笔试模拟题精解之“最大边权和”贡献者|郭达彬简介：根据题意，最终需要将 n 个点连通并达到最大边权，而边权为两个点的点权之和的一半，所以一个点加入连通图的最大边权就是和点权最大的点连通。题目描述题目等级：容易知识点：贪心查看题目：最大边权和现在有 n 个点(1=n=1000)，每个点都有一个值称为点权 ai(ai 为偶数，1=ai算法笔试模拟题精解之“最大边权和”2,4,6,8,10输出：30解题思路：贪心根据题意，最终需要将 n 个点连通并达到最大边权，而边权为两个点的点权之和的一半，所以一个点加入连通图的最大边权就是和点权最大的点连通。因此想要得到最大边权和，只要所有点都与点权最大的点相连即可。实现过程中，首先求出最大的点权，然后计算出其他点与这个权值最大的点的边权之和即可。时间复杂度：O(n)空间复杂度：O(1)看完之后是不是有了想法了呢，快来练练手吧 查看题目：最大边权和算法笔试模拟题精解之“最强的团队”13算法笔试模拟题精解之“最强的团队”贡献者|郭达彬简介：根据题意，最强团队即团队中每个小队的能力值都是最高的。即解决这道题需要找出数组中连续最大值的个数，若有多个连续最大值，选择个数最多的。题目描述题目等级：简单知识点：贪心查看题目：最强的团队有一个阵营，里面有 n 个小队(1=n=100)，每个小队都有他们的能力值ai(0算法笔试模拟题精解之“最强的团队”1,2,3,3,2,1输出：2解题方法根据题意，最强团队即团队中每个小队的能力值都是最高的。即解决这道题需要找出数组中连续最大值的个数，若有多个连续最大值，选择个数最多的。具体实现时，可以先找出数组中最大的能力值是多少，然后设置一个标记 tag。接着遍历数组，比较每个数组元素和最大值，数组元素等于最大的值的时候，将 tag标记为 1，数组元素不等于最大值时，将 tag 置为 0。在 tag 等于 1 时统计连续最大值的数量，若统计到多个最大值，则记录最大的那个。时间复杂度：O(n2)空间复杂度：O(1)看完之后是不是有了想法了呢，快来练练手吧 查看题目：最强的团队算法笔试模拟题精解之“Tom 爱吃巧克力”15算法笔试模拟题精解之“Tom 爱吃巧克力”贡献者|郭达彬简介：根据题意，可以得知这道题可以运用贪心算法，策略是每次都去买最便宜的巧克力。题目描述题目等级：容易知识点：贪心查看题目：Tom 爱吃巧克力Tom 非常喜欢巧克力，他上次买的巧克力吃完了，所以他打算再去买 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解题思路：贪心根据题意，可以得知这道题可以运用贪心算法，策略是每次都去买最便宜的巧克力。由于题目给的二维数组是乱序的，可以根据巧克力的价格对二维数组从小到大进行排序，便于Tom选择最便宜的巧克力。Arrays类中只提供了一维数组的排序，如果要用 Arrays 对二维数组排序，需要重写 Comparator 里的 compare 方法。排序完成后，接下来操作就比较简单了。遍历数组，优先买便宜的巧克力，直到达到限购块数，再去下一家巧克力店。最终买到k块巧克力时Tom花的钱最少。时间复杂度：O(n)空间复杂度：O(1)看完之后是不是有了想法了呢，快来练练手吧 查看题目：Tom 爱吃巧克力算法笔试模拟题精解之“吃奶酪”17算法笔试模拟题精解之“吃奶酪”贡献者|郭达彬简介：根据题意，如果要花费最少时间，则每个奶酪都让离奶酪最近的人去拿，因此，坐标=50001 的奶酪让 Jerry 去拿。题目描述题目等级：容易知识点：贪心、枚举查看题目：吃奶酪Tom 和 Jerry 都很喜欢吃奶酪，现在有 n 块奶酪散落在坐标轴上(1=n=100000)，他们分别在 a1,a2,a3.an(1=ai算法笔试模拟题精解之“吃奶酪”输出：20000解题方法根据题意，如果要花费最少时间，则每个奶酪都让离奶酪最近的人去拿，因此，坐标=50001 的奶酪让 Jerry 去拿。具体实现时，可以设置一个 time 值，然后遍历数组。判断每一块奶酪的坐标范围，根据坐标判断应该让谁拿，再计算拿到这个奶酪需要多长时间，如果时间大于time，则用这个值替换掉 time 的值。用这种方法，遍历整个数组后的 time 值即为Tom和Jerry拿到所有奶酪所用的最短时间。时间复杂度：O(n)空间复杂度：O(1)看完之后是不是有了想法了呢，快来练练手吧 查看题目：吃奶酪算法笔试模拟题精解之“一的个数”19算法笔试模拟题精解之“一的个数”贡献者|郭达彬简介：根据题意，本题的所有数字应从二进制角度考虑。题目描述题目等级：容易知识点：位运算、贪心查看题目：一的个数给你两个数字 l、r，问在区间 l,r 内的所有数中，二进制表示下“1”的个数最多的一个数是多少，如果有多个相同的，输出所有符合条件的数中最小的一个数。输入一个整数 l,和一个整数 r。(1=l=r算法笔试模拟题精解之“一的个数”解题思路：二进制根据题意，本题的所有数字应从二进制角度考虑。所求数字可分为两部分，高位部分和低位部分，高位部分的值等于 l,r 高位相等的部分，在区间 l,r 中的所有数的高位部分都应该与其相等，即high=r&(-1低位的部分计算过程如下：如果r-high的值的二进制全为 1，则低位部分为r-high。如果不是全为 1，则低位部分为(1 查看题目：一的个数算法笔试模拟题精解之“Bob 的花束”21算法笔试模拟题精解之“Bob 的花束”贡献者|洪浩原简介：本题充分理解题意后，直接模拟这个“选取最大值”的过程就可以得到结果了。题目描述等级：中等知识点：贪心查看题目：Bob 的花束Bob 和 Alice 是青梅竹马。今天，Bob 终于要鼓起勇气向 Alice 表白了！说到表白，自然是少不了买花了。Bob 来到了花店，花店一共提供了 9 种花，每一种花都有对应的价钱。但是 Bob 的零花钱有限，不能把所有的花都买下来送给 Alice。为了方便挑选，Bob 给这 9 种花分别标号 1-9，Bob 希望买到的花按照编号可以排出尽可能大数字，请问 Bob 能够排出的最大的数字是多少？输入一个正整数 value，代表 Bob 拥有的零花钱。(0=value=106)和有 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这样的方案。这样相当于根据输入，输出的位数可以用很小的时间代价来确定：“用可用钱数，除以最便宜的花的价格，并向下取整”。假设这里的位数为 m。其次，在位数确定的情况下，高位数字越大，结果也就越大，比如同样是 8 元钱，只能购买价格为 5 的 5 号花，和价格为 3 的 3 号花时，购买 35 就是最差的方案，而 53 才是正确答案。而且因为每个花的数量是无限的，所以可以模拟这个“从高位开始，逐个选取能买得起的最大的数字；同时每选完一位后，要确保剩下的钱，依旧可以买到 m 位数字的组合方案。”提示：根据上面逻辑写出的答案，在充分理解优化后，至少可以达到 2 遍扫描数组得到结果。时间复杂度：O(9n)看完是不是有了新思路了呢，快来试一下吧：查看题目：Bob 的花束算法笔试模拟题精解之“钱庄”23算法笔试模拟题精解之“钱庄”贡献者|张鹏飞简介：可以先分析示例是如何实现的，以此为突破点。题目描述等级：中等知识点：贪心查看题目：钱庄钱庄每天能够收到很多散钱，第 i 个散钱的值 2wi。为了便于管理，钱庄每天都会向中央银行申请兑换钱币，假设钱庄有一些散钱使得 2k1+2k2+.+2km=2x（x 为非负整数），那么就可以将这些散钱兑换成一个大钱币，问在钱庄收到的这些散钱最终最少能变成几个钱币？输入一个整数 n，表示一共有 n 个钱币(1=n=106)；再输入 n 个整数 wi，表示有价值 2wi(0=wi算法笔试模拟题精解之“钱庄”输出：1注意21+21+22+23=24，因此兑换后最少为一个钱币解题思路一大致思路：对于 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 数组中保存出现的次数）;再次遍历 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遍历结束后,对剩下的钱币个数做统计(而上述操作保证了所有钱币均不可兑换);复杂度分析空间复杂度开辟了 100000 大小的 map 数组(因为价值 wi 取值为:0=wi 查看题目：钱庄26算法笔试模拟题精解之“移动射击”算法笔试模拟题精解之“移动射击”贡献者|张鹏飞简介：首先理解题意，题目说的“发动之后只能改变一次方向”是干扰你的，因为即使你在中间过程中左右摆，但宏观上还是最多改变了一次方向。题目描述题目等级：中等知识点：DP查看题目：移动射击你正在数轴上跟小精灵对战。你拥有一个十分强力的技能称为移动射击，但是这个技能有一个缺点是在你发动之后只能改变一次方向。你可以认为你的位置在数字 0 的位置上，在数轴的正方向上有 n 只精灵，负方向上有 m 只精灵。移动射击可以造成 w 点伤害。每个精灵都有自己的血量，当血量降为 0 时死亡。在最开始时你可以选择向正方向或负方向释放移动射击，并且可以在任意时刻改变技能的方向。请问你最多可以击杀多少只小精灵?(n，m，w 以及精灵的血量均在1,100000 范围内)输入内容为五个，前三个为三个数字：正方向上的精灵个数 n、负方向上的精灵个数 m,移动射击可以造成的伤害 w；第四个是一个长度为n的数组a，表示正方向上的 n 个精灵的血量；第五个是一个长度为m的数组b，表示负方向上的 m 个精灵的血量。算法笔试模拟题精解之“移动射击”=w 的时候，记住此时的位置 index_a=i，退出循环，退出后加上这句if(i=n|aiw)index_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算法笔试模拟题精解之“相似数组”贡献者|张鹏飞简介：要解出相似数组的最长长度，即要求相似数组中的每个元素尽可能的小，把握这一点，结合下来的算法过程理解一下。题目描述等级：中等知识点：贪心、尺取法查看题目：相似数组现在有两个数组a和b，长度分别为n和m。你可以对两者进行任意次数（包括零次）的下述操作：任选一段连续的区间 l,r，将其替换为这段区间的所有数字的和。比如，对于1,3,4,5,11,9，你可以选择区间 3,5，并将其替换为 4+5+11=20，操作后的数组为 1,3,20,9。你现在需要通过上述操作将两个数组变成相同的数组，相同的定义是：对于两个数组a，b必须长度相同，不妨设为 l，并且对于1=i=l，必有 ai=bi。如果这两个数组可以变成相同的数组，那么我们称这两个数组是相似数组，否则不是相似数组。我们并不在意操作的次数，我们只在意在这两个数组经过操作之后变成相同数组的时候最长的长度是多少，如果它们本来不相似请输出-1。输入内容为四个部分，先两个数字 n、m（1=n,m算法笔试模拟题精解之“相似数组”中1=ai,bi=1000000000。输出一个数字，表示最长的长度。示例 1输入：547,2,5,11,139,16,6,7输出：3解题思路要解出相似数组的最长长度，即要求相似数组中的每个元素尽可能的小，把握这一点，结合下文的算法过程理解一下。设两个指针，分别指向数组 a 和 b 的第一个位置（即 i=0，j=0)，定义两个变量，分别表示数组 a 和 b 的当前区别的和（sum_a=a0,sum_b=b0)，然后遍历数组。如果 sum_a=sum_b：则结果加 1(即 ans+)，然后对两个指针分别加 1(i+,j+)。判断：如果两个指针都等于各自数组的长度(即 i=n&j=m)，则返回结果(returnans）；如果两个指针仅有一个等于数组的长度（即 i=n|j=m)，则返回-1（表示不是相似数组)；算法笔试模拟题精解之“相似数组”sum_b:则数组 b 的指针向前移动（即 j+），判断 j 是否越界(即 j=m 为真表示越界)，如果越界，那么返回-1(表示不是相似数组)，如果没越界，给区别和加上当前元素(即 sum_b+ab)重复以上过程，即可求解。是不是有思路了呢，点击链接立刻答题：相似数组32算法笔试模拟题精解之“过吊桥”算法笔试模拟题精解之“过吊桥”贡献者|郭达彬简介：根据题意，要知道 B 同学还能在桥的一头逗留的时间，需要先求出什么时候有连续的两块木板坏掉，或者第一块或者最后一块木板坏掉。题目描述题目等级：容易知识点：贪心查看题目：过吊桥B 同学在机房敲了半个多月的代码之后终于打算出门玩一玩了。这天他准备去爬山，当爬到了半山腰时，发现了一个吊桥。这个吊桥总共由 n 块标号为 1-n 的木板组成，由于年久失修，这些木板有些已经快要坏掉了，每块木板都有一个值 ai 表示第 i 块木板还有 ai 分钟就要坏掉了，即在第 ai+1 分钟将无法站上这块木板。B 同学过吊桥时一步只能走一块或两块木板，但是他想在吊桥的这边多玩一会。请问他在吊桥这边最多可以玩多长时间？（可以认为 B 同学能在一分钟内通过吊桥）特殊的，如果第一块或者最后一块木板坏掉的话吊桥就直接无法通过了。输入一个整数 n,表示总共有 n 块木板(1=n=105)。再输入一个包含 n 个整数的数组，第 i 个数表示第 i 块木板还有 ai 分钟就要坏掉了(1=ai=109)。算法笔试模拟题精解之“过吊桥”算法笔试模拟题精解之“过吊桥”若符合条件，此时在数组遍历的数即为可以逗留的时间。若不符合条件，则继续遍历数组，重复上述步骤，直到符合条件为止。时间复杂度：O(n)空间复杂度：O(2n)看完之后是不是有了想法了呢，快来练练手吧 查看题目：过吊桥算法笔试模拟题精解之“完美排列”35算法笔试模拟题精解之“完美排列”贡献者|洪浩原简介：本文通过两种解法描述 86 题“完美排列”的解题过程，更有对应的时间和空间复杂度帮助理解。题目描述等级：容易知识点：贪心查看题目：完美排列完美排列的定义为一个长度为 n 的数组，n 个元素各不相同且每个元素均在1,n 的范围内。现在给你长度为 n 的数组，你每次可以进行如下操作：任选数组中的一个元素，将其加一或者减一，问最少需要多少次操作才能够使得该数组为一个完美排列。输入一个整数 n，表示数组的长度(1=n=104)；再输入含有n个数的数组，第 i 个数表示数组中的第 i 个元素为ai（1=ai算法笔试模拟题精解之“完美排列”注意：3-20-1总共需要操作两次。解法探究解法一：正常贪心思路本题是一道典型的贪心算法题，问题可以通过每步的最优策略分治解决。如果将n个大小未知的正整数，通过题目中的规则“填充”到槽1n中，我们不妨从最小的数字槽1开始做起。显然，这n个正整数中最小的数字a（无论这个最小的数字是1或是100），是填充槽1的最佳选择。其它(n-1)个数字和1的“距离”，都必定大于等于a，距离槽1的距离都不如a更优，所以可以将a填充进槽1，并在后续选择中排除掉它。当填充槽2时，依旧用上面的思路就可以了。用剩下的(n-1)个数字中最小的数字去通过加减1进入槽2，必定是填充槽2所有方式中的最佳策略。将上面的思路重复应用，就得到了结果。复杂度上需要扫描n次数组。时间复杂度：O(n2)空间复杂度：O(1)解法二：排序优化上面的反复扫描非常浪费时间，不如提前对数组排序，然后从排序后递增数组的第一项开始，逐个比较与槽1n的距离，最后加到一起，得到答案。时间复杂度：O(logn)空间复杂度：O(1)看完之后是不是有了答题思路了呢，快来练练手吧：查看题目：完美排列算法笔试模拟题精解之“采摘圣诞果”37算法笔试模拟题精解之“采摘圣诞果”贡献者|猿圈简介：我们定义数组 ai 表示第 i 天可以采摘的刚刚结出来的果子，数组 bi 表示第 i 天可以采摘的已经过了一天的果子。根据输入先初始化 a。题目描述等级：中等知识点：贪心查看题目：采摘圣诞果圣诞节马上就要来了，果园里的n棵圣诞树马上就要结果子了，每棵圣诞树会在第 ai 天结出 bi 个果实。果园里有许多圣诞小精灵，它们非常喜欢吃圣诞果，如果在结果后两天内也就是第 ai 天和第 ai+1 天，没有将果实采摘下来，那么将会被小精灵们偷吃掉。你，作为圣诞树的看守者，必须采摘尽可能多的圣诞果，但是你每天最多只能采摘 v 个圣诞果，当然，可以是不同的果树上的。现在你需要判断自己最多可以收获多少圣诞果。输入圣诞树棵树 n、每天最多采摘的圣诞果数量 v 和一个数组 m，其中 mi=ai,bi 表示每棵圣诞树第 ai 天结出 bi 个果实（1=n，ai，bi算法笔试模拟题精解之“采摘圣诞果”31,3,2,5,3,4输出：12注意你可以在第一天在第一棵树上摘三个，第二天在第二棵树上摘三个，第三天在第二棵树上摘两个，然后再在第三颗树上摘一个，第四天在第三棵树上摘三个。解题思路描述我们定义数组 ai 表示第 i 天可以采摘的刚刚结出来的果子，数组 bi 表示第 i天可以采摘的已经过了一天的果子。根据输入先初始化 a。假设我们当前处于第 i 天，那么显然我们应该采摘 bi 中的果实，然后再采摘ai 中的果实，因为如果不采摘 bi 中的果实，则它们会在下一天被偷吃。在更新之后 ai 中剩余的果实会在下一天变成 bi 中的果实。时间复杂度：O(3000)空间复杂度：O(3000)看完之后是不是有了答题思路了呢，快来练练手吧：采摘圣诞果算法比赛模拟题精解之“TairitsuandDynamicObjects”算法比赛模拟题精解之“TairitsuandDynamicObjects”输入一个正整数 n，表示物品个数。再输入两个数组 a 和 b，分别表示 n 个物品的 A 属性和 n 个物品的 B 属性。（保证 1=n=2*1e5,0=ai,bi 查看题目：TairitsuandDynamicObjects算法笔试模拟题精解之“Codancer 的炸弹引爆”41算法笔试模拟题精解之“Codancer 的炸弹引爆”贡献者|猿圈简介：花费 8 电力引爆第 3 枚炸弹，那么第 1 枚就会被自动引爆，那么第 2 枚也会被自动引爆。这种方案的花费是最小的。题目描述等级：困难知识点：贪心、优先队列查看题目：Codancer 的炸弹引爆Codancer 终于抵达了恶龙的城堡。现在他在城堡周围摆放了 n 枚电力炸弹，每个电力炸弹有两种属性 m 和 p，只有已经引爆了 m 枚电力炸弹或者 Codancer 直接花费 p 的电力，第 i 枚炸弹才会被引爆，现在 Codancer 想使用最少的电力引爆所有的炸弹，请计算最少需要多少电力？第一行是一个正整数 n，代表有 n 枚电力炸弹。接下来输入 n 行，每行两个正整数 m 和 p，代表炸弹的属性。(1=n200000,1=p=100,1=m算法笔试模拟题精解之“Codancer 的炸弹引爆”输出：8注意花费 8 电力引爆第 3 枚炸弹，那么第 1 枚就会被自动引爆，那么第 2 枚也会被自动引爆。解题方法：花费 8 电力引爆第 3 枚炸弹，那么第 1 枚就会被自动引爆，那么第 2 枚也会被自动引爆。这种方案的花费是最小的。炸弹的引爆顺序如图所示。本题使用贪心策略，考虑按照所需要的电力从大到小排序，假设从第 i+1 枚到第n 枚炸弹已经用电力引爆的炸弹个数为 cnt，由于在 1,i-1 最多再引爆 i-1 枚炸弹，如果此时 i-1+cntmi，说明就需要再花费电力引爆，但是必须要选择需要的电力最少的，因此可以用优先队列维护，直接取出栈顶即可。时间复杂度：O(n*log（n）)看完之后是不是有了答题思路了呢，快来练练手吧：Codancer 的炸弹引爆算法笔试模拟题精解之“学习小组”43算法笔试模拟题精解之“学习小组”贡献者|猿圈简介：因为题目中说了 ai 是一个非递减的数列，所以我们可以推导出一个式子。题目描述等级：中等知识点：贪心查看题目：学习小组在一个课堂上，有 n 个学生(1=n=3e5)，每个学生都有他们自己的学分ai(1=ai=1e9,ai=ai-1)，现在老师想将他们分为 m 个小组(1=m算法笔试模拟题精解之“学习小组”输出：4解题方法：因为题目中说了 ai 是一个非递减的数列，所以我们可以推导出一个式子。比如我们要将一个数组分成 3 组，那么可以假设为，a1,ai,ai+1,aj,aj+1,an这三组，然后我们所要求的值就是(ai-a1)+(aj-ai+1)+(an-aj+1).那么就可以推导出 an-a1+aj-aj+1-ai-ai+1，所以就是 an-a1 减去最大的 m-1 个相邻的差值，那么 ai-ai+1 这个显然是差分的性质，所以我们对于原数列求一个差分数组出来，然后对差分数组进行排序，贪心的去减去前 m-1 个最大的就好了。看完之后是不是有了答题思路了呢，快来练练手吧：学习小组算法笔试模拟题精解之“恢复字符串”算法笔试模拟题精解之“恢复字符串”示例 1输入：“+-”“-+”输出：10注意样例最优解为“1+1+1-1”，“3-1-1+1”。解题方法：首先可以确定最小值一定为 0。分两种情况讨论。1.两个字符串都没有负号的时候，最优解的所有位置都填 1。最小消耗为2*（n+1）。2.表达式中仅需要有一个负号，表达式的值就可以为任何值。此时两个表达式可以相互调整，因此最小差也是 0。表达式中除了第一位以外每位数字填 1 可以得到最小消耗，因为值加在哪一位都是等效的。不妨假设都加在第一位。计算出 s1,s2 的正负号数量的差，分别为 x 和 y。假设第一位分别为 pa，pb，我们只需要使（pa+x=pb+y）即可。假设最终表达式的值为 final，则 final=max(max(x,y)+1,0)，则 pa=final-x，pb=final-y。看完之后是不是有了答题思路了呢，快来练练手吧：恢复字符串算法笔试模拟题精解之“矩阵最小路径和”算法笔试模拟题精解之“矩阵最小路径和”解题思路：动态规划本题可以用动态规划的方法来解决。计算一个格子到右下角的最小路径需要两个数据，一个是右边格子到右下角的最小路径，一个是下边格子到右下角的最小路径，两个数据的较小值加上当前格子的数值即为最小路径。即dpi,j=min(dpi+1,j,dpi,j+1)+mi,j由于计算当前格子最小路径需要右边和下边格子的最小路径。因此，需要从底向上进行决策。本题用动态规划法的难点之一是从底向上进行决策的顺序。如下图所示，通过观察可以发现，同一对角线上的数字的横纵坐标和是相等的，我们以对角线的方向为顺序，从右下角向左上角计算出每个格子的最小路径。最后可计算得出dp0,0。是不是有思路了呢，点击链接立刻答题：矩阵最小路径和算法笔试模拟题精解之“寻找等比数列”49算法笔试模拟题精解之“寻找等比数列”贡献者|洪浩原简介：最简单的方法，就是遍历数组中所有可能的三元组，逐个检验每组数是否符合公比为 k 的等比数列的性质。对于较长的用例，这么做显然是超时的，不通过。题目描述等级：中等知识点：DP查看题目：寻找等比数列Alice 和 Bob 都是数学高手，有一天 Alice 给了 Bob 一个长度为 n 的数组 a，要求 Bob 在数组中找出 3 个数，要求三个数能够组成一个公比为 k 的等比数列，且不改变三个数在数组 a 中的位置关系。为了降低难度，Alice 只要求 Bob 回答数组 a 中有多少个这样的等比数列。输入一个整数 n 表示数组长度、公比 k(1=n,k=2*105)和包含 n 个数的数组a(-109=ai算法笔试模拟题精解之“寻找等比数列”1,1,2,2,4输出：4题解思路方法 1：逐个遍历（超时）最简单的方法，就是遍历数组中所有可能的三元组，逐个检验每组数是否符合公比为 k 的等比数列的性质。对于较长的用例，这么做显然是超时的，不通过。时间复杂度：O(n3)空间复杂度：O(1)方法 2：动态规划本题充分利用下面两个隐藏规律，就可以使用动态规划：1.“长度为 3 的等比数列”，满足了动态规划的最优子结构性质数列中每个数字只有 4 种可能的状态。其中带*号的状态可以同时存在，且靠后的状态可以由前面的状态转换而来：同时属于一个或多个等比数列的第 1 项同时属于一个或多个等比数列的第 2 项同时属于一个或多个等比数列的第 3 项无法与前后数字组成任何等比数列2.“不允许调换顺序”，满足动态规划的子问题不重叠性和无后效性性质算法笔试模拟题精解之“寻找等比数列”算法笔试模拟题精解之“字符配对”算法笔试模拟题精解之“字符配对”贡献者|张鹏飞简介：本题可以使用动态规划来解决，对于第 i 个字符，有选和不选两种，如果选，则和第 i-1 个字符组合创造权值，如果不选，就单独出来没有权值，取两者中加权最大的选择。题目描述题目等级：中等知识点：DP查看题目：字符配对给你一个字符串，字符串中仅包含 A,B,现在有四种字符串 AA,AB,BA,BB，每种字符串都有他们的权值，问从给出的字符串中能够得到的最大权值为多少(一个字符只能属于一个子字符串)？输入一个字符串 s（1=|s|=106）;再输入一个数组，数组中包含四个数字 a,b,c,d，依次表示字符串 AA,AB,BA,BB 的权值(1=a,b,c,d=100)。输出权值的最大值。示例 1输入：ABA算法笔试模拟题精解之“字符配对”算法笔试模拟题精解之“数组染色”算法笔试模拟题精解之“数组染色”贡献者|张鹏飞简介：可以采用链表的思想，定义一个数组 temp 来存放每个递增的子串，题目需要求出最少的递增子串有多少个，采取的思路是递增的子串越密集越好。题目描述等级：中等知识点：DP、LIS查看题目：数组染色codancer 现在有一个长度为 n 的数组 a,对于每个这个数组的每个数字，我们必须染上颜色，但是 codancer 有一个限制条件:如果 i 输入一个正整数 n 和数组 a。（1=n=100000,0=ai=1000000000）.输出最少需要的颜色种类数。示例 1输入：52,1,4,5,3输出：2算法笔试模拟题精解之“数组染色”tempj,那么我就将 xi 元素链接在 tempj 元素后面，又因为这是个数组，不是链表，而且链接后 tempj 值再也用不上，和链表的最后一个元素比较，因此可以直接覆盖 tempj 元素，即 tempj=xi。我说的链接如下图所示56算法笔试模拟题精解之“数组染色”可以发现，每次比较都是和链表最后一个元素比较，所以前面的元素可以覆盖，如下面的直接覆盖法，也是用数组实现，很简单。而且还可以发现，temp 数组永远是递减的，这样也满足密集子串，因为从上往下走，找到满足的即可停止，不需要继续往下。最终，temp 数组有几个元素，答案就是多少。可以用 ans 一致指向 temp数组的最后一个元素的位置。完全理解本解法需要理解我定义的密集子串和链接法转直接覆盖等概念。好好理解一下，很简单，有什么问题可以在评论区交流。看完之后是不是有了想法了呢，快来练练手吧 查看题目：数组染色算法笔试模拟题精解之“连绵的群山”57算法笔试模拟题精解之“连绵的群山”贡献者|张鹏飞简介：可以将山化分为几个小连续区间，每个区间保证越来越高，并且保证每个区间尽可能的长。除第一个和最后一个区间，中间的其余区间，有移除可能的是每个区间的最小值和最大值，第一个区间有移除可能的是最小值，最后一个区间有移除可能的是最大值。这样才能找出最长的山的区间。题目描述等级：中等知识点：DP查看题目：连绵的群山小森家的北面有一条连绵的山脉，山脉高低起伏。小森很好奇这些山中最多有几座连续的山头是越来越高的，当然这对小森来说太简单了。他又想，假如可以移除其中一座，这个答案最大又会是多少？当然了，他也可以选择不移除任何一座山峰。1=n=100000,1=ai算法笔试模拟题精解之“连绵的群山”5,10,6,7,8输出：4注意可以去掉 10，形成数组 5,6,7,8，长度为3。解题思路：大致思路：可以将山化分为几个小连续区间，每个区间保证越来越高，并且保证每个区间尽可能的长。除第一个和最后一个区间，中间的其余区间，有移除可能的是每个区间的最小值和最大值，第一个区间有