上一篇：合辑 | 七道典型笔试算法模拟题精解系列（一）
阿里云开发者社区 在线编程 产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。技术人进阶学习必备工具！点击链接开始体验：https://developer.aliyun.com/coding
本文为大家集合了其中部分题目的解析，助你冲榜！！
1、2的幂次方数
题目概述：Tom是一个十分喜欢数学的人，尤其喜欢2的幂次方的数字。现有n（1<=n<=150000）个数字，对于其中的每一个数字ai(1<=i输入数字个数n和n个数字；
输出一个数字，表示最终需要删除的数字的个数。
题解简述：对于本题，因为要从数组中删除数字。删除分为两步，一是定位（查找），二是删除（将出现次数减1）。所以首先需要考虑的难题是，如何快速定位要查找的数字，并记录下数字出现的次数？for循环的线性查找，递归的二分查找（对有序数组），建立哈希表，都是可选的方式。既然追求最佳解法，你不妨先试试将题目提供的数据结构转为哈希表？
之后的第二个难点，就是如何得出“与某个数相加为2的幂次方数”的数字了。我们知道，用二进制表示时，一个2的幂次方的正整数，譬如2，4，8，16...，只有最高位为1，其余位都是0，譬如b1，b10，b100，b1000...所以，对每个数字，只要用位元算找到它的最高位1的位置，就可以确定比它大的2的幂次方数中最小的数字了...本题还有一个陷阱，点击链接查看详情：笔试算法模拟题精解之“2的幂次方数”
2、神奇数字在哪里
题目概述：
请计算出1-n(1<=n<=1000000000)中有多少个数字中，只存在'1','2','3'这三个数字，且这三个数字至少都要出现1次。
输入一个数n。
输出1-n中符合要求的数字的个数。
题解简述：
注意读题，本题要求的数字中“只”含有1，2，3三个数字。
方法 1：暴力搜索
对本题，最简单的想法是针对每个数字，转为字符串，然后判断数字中是否只同时包含1，2，3三个字符。
鉴于本题输入是int，n最大可以达到2^31-1≈2*10^9，一个这么长的for循环，时间复杂度还是比较高的，为O(n)，当然这并不是最优解法。
可以使用深度优先搜索的思维去想，极大的降低时间复杂度，点击链接了解详情...笔试算法模拟题精解之“神奇数字在哪里”
3、神奇的棋子
题目概述：
Tom有一天在玩棋子，这些棋子都不是普通的棋子。现在有n个棋子排成一排(2<=n<=18)，每个棋子都有它们自己的权值ai(0<=ai<=1e9)，现在Tom每次选择连续的三枚棋子，然后中间的那枚棋子会消失，而它左右两边的棋子会分别加上它的权值，问最后只剩下两枚棋子的时候，这两枚棋子的权值的最小的和为多少？
输入棋子个数n和一个数组a，a[i]表示每个棋子的权值。
输出一个数，表示最终剩下的两枚棋子的权值的最小的和。
题解简述：
因为我们每选择一次，消失的数对左右都有影响，而且也会被挑选的顺序影响，所以需要去考虑每个棋子的贡献。
枚举一段区间最后选的棋子，然后将其分为两段区间，设该段区间的左端点最终的贡献为x，右端点最终的贡献为y，那么在只剩最后选的数，左端点，右端点三个点时，我们选择最后的那个点，那么最后那个数最终的贡献就是x+y次了，然后根据这个思路已知分治下取就好了...笔试算法模拟题精解之“神奇的棋子”
4、Jerry的考验
题目概述：
有一天Jerry给Tom出了一道题来考验他。Jerry给了Tom一个长度为2*n的只包含小写字母的字符串，让Tom将这个字符串任意挑选字符，将其分成两个等长的字符串a和b(对于一个si不能同时被选到a和b中)，然后a要和reverse(b)相同(a和反转后的b相同)，问这样的方案数有多少？Tom有些为难，所以请你来帮帮他吧。
输入一个正整数n，和一个长度为2*n的字符串
输出方案数。
题解简述：
首先我们来看样例abba，如果我们选择ab，剩下ba，如果我们选择ba，剩下ab，这两种情况都是符合题意的，而且这两种情况都各有两种选取方式，所以一共有4种。
对于这种选和不选的情况，很容易可以想到二进制枚举的方法。但是如果直接用二进制枚举的话时间复杂度是2^36的，肯定要超时，所以我们需要对其进行优化...笔试算法模拟题精解之“Jerry的考验”
5、采摘圣诞果
题目概述：
圣诞节马上就要来了，果园里的 n 棵圣诞树马上就要结果子了，每棵圣诞树会在第a[i]天结出b[i]个果实。果园里有许多圣诞小精灵，它们非常喜欢吃圣诞果，如果在结果后两天内也就是第a[i]天和第a[i]+1天，没有将果实采摘下来，那么将会被小精灵们偷吃掉。
你，作为圣诞树的看守者，必须采摘尽可能多的圣诞果，但是你每天最多只能采摘v个圣诞果，当然，可以是不同的果树上的。现在你需要判断自己最多可以收获多少圣诞果？
题解简述：
我们定义数组a[i]表示第i天可以采摘的刚刚结出来的果子，数组b[i]表示第i天可以采摘的已经过了一天的果子。根据输入先初始化a[]...笔试算法模拟题精解之“采摘圣诞果”
6、数组变换
题目概述：
给出一个长度为 n 的数组，和一个正整数 d。
你每次可以选择其中任意一个元素 a[i] 将其变为 a[i] + d 或 a[i] - d，这算作一次操作。你需要将所有的元素全部变成相等元素，如果有解，请输出最小操作次数，如果无解请输出-1。
输入数字n、数字d，和一个长度为n的数组a。1 <= n <= 100000，1 <= d <= 100, 1 <= a[i] <= 100000。
输出一个数字，表示最小的操作次数，如果无解输出-1。
题解简述：
首先判断无解的情况，可以发现 a[i]，a[i]+d, a[i]-d 在 模d情况下的余数不会发生改变，因此如果原数组中的存在任意两个数字它们对d取余结果不同，那么此时无解。
设余数为r。判断完无解之后，需要求出最小值。
先将数组a[i]排序，然后除以d，得到从r变成a[i]需要的步数。
枚举元素a[i]，将所有元素全部变成a[i]需要考虑两部分，i之前和i之后:对于i之前的元素，假设都是r，那么需要 (i-1)*a[i]，但是因为并不都是0，所有我们可以用一个变量val存放前i-1项的和，然后我们在减去val就是前i-1个元素真正需要操作的步数...笔试算法模拟题精解之“数组变换”
7、恢复字符串
题目概述：
给出两个仅包含“+”、“-”两种字符且长度相同字符串s1、 s2，你需要通过填充数字将这两个字符串恢复成一个合法的表达式。并且只能填入正整数，恢复后的表达式的值必须非负。
例如对于字符串“+-”，你可以将其变成“1+1-2”，但是不可以变成“1+1-3”，也不可以变成“1+0-1”。定义你的消耗为你填充的所有正整数的和。比如“1+1-2”的消耗为 1 + 1 + 2 = 4。你需要将这两个字符串都恢复成合法表达式，并且尽量的使它们的差值最小，于此同时你还需要使你的消耗最小。
相信你通过思考已经发现最小差值总是0，因此你只需要求出差值为0时的最小消耗即可。字符串长度都小于100000。
输入两个字符串s1和s2。
输出一个数字，表示最小消耗。
题解简述：
首先可以确定最小值一定为0。分两种情况讨论。
两个字符串都没有负号的时候，最优解的所有位置都填1。最小消耗为 2*（n+1）。
表达式中仅需要有一个负号，表达式的值就可以为任何值。此时两个表达式可以相互调整，因此最小差也是0。
表达式中除了第一位以外每位数字填1可以得到最小消耗，因为值加在哪一位都是等效的...笔试算法模拟题精解之“恢复字符串”
8、填数问题
题目概述：
有m个格子，编号为1,2…m，每个格子可以填1,2...n中的任意一个数。定义这m个格子上的数都是“好的”，仅当对于任意一个编号为i的格子，编号大于i的格子上的数都大于等于i号格子上的数。求有多少个填数方案，满足这m个格子中填的数是“好的”，答案对P取模。
三行分别输入三个整数，m、n、P，分别表示有m个格子、填入的最大数字n和模P。（保证1<=n,m<=1e18,2<=P<=1e5且P是质数）
输出一个整数表示答案对P取模的结果。
题解简述：
“对于任意一个编号为i的格子，编号大于i的格子上的数都大于等于i号格子上的数”可以转化为m个格子上的数是单调不减的。令cnt_i表示i这个数在m个格子中的出现次数，可以发现一组∑cnti = m(i∈[1,n])唯一对应着一个单调不减的填数方案。
由插板法可知...笔试算法模拟题精解之“填数问题”
9、学习小组
题目概述：
在一个课堂上，有n个学生(1<=n<=3e5)，每个学生都有他们自己的学分ai(1<=ai<=1e9,ai<=ai-1)，现在老师想将他们分为m个小组(1<=m<=n)，为了方便交流，所有的小组都是由相邻的学生组成(abc相邻,不存在ac一个小组b在另一个小组的情况)，现在老师想让每个小组的学分差值尽量小(最大值减去最小值)，请你帮助老师来分一下组，输出最后的每个小组的最小的差值的总和。
第一行和第二行输入两个数n、m表示有n个学生要分成m个小组，再输入n个数，表示每个学生的学分。
输出一个数字，表示最后分出的m个小组的最小的差值的总和。
题解简述：
因为题目中说了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个最大的就好了...笔试算法模拟题精解之“学习小组”
10、Tom的手工课
题目概述：
一天Tom在上手工课，老师给他们每个人发了一个白色的纸条，上面有n个方格(2<=n<=1e6)。
然后又给他们每个人发了n-1个彩带，一个彩带可以粘到两个相邻的方格上。现在老师让他们把n个方格都粘上彩带(可以不用完n-1个彩带，一个方格上可以重复粘彩带)。
Tom是一个热爱数学的人，他想知道所有的方案中，一共用了多少次彩带(所有的方案所用的彩带的总和)。（答案对1e9+7取模）
输入一个数n表示方格的个数。
输出一个数表示最终方案数，答案对1e9+7取模。
题解简述：
对于每个方案来说，最少需要n/2个彩带，最多要n-1个彩带，然后我们分别对其进行计算贡献。
操作最多 i 次的方案数是 f[i]，恰好 i 次的方案就是 f[i]−f[i−1]，而 f[i]=C(n-1-I, i-1)。
具体含义:可以看作是每次可以选择 +1,+2 ,求构成 n−2 的方案数,我们先默认都 +1,剩下就是选择 +0,+1 了,只要总共的 i−1 次操作中有 n−1−i 个选择了 +1,就一定可以达到目标了...笔试算法模拟题精解之“Tom的手工课”
持续更新中。。。更多内容请关注算法编程技术圈！
另有在线编程周赛、月赛火热进行中！点击链接了解详情：在线编程3月份比赛正式开启！机械键盘等你拿！
