（新）程序员进阶之算法练习
前言
金三银四，求职黄金月做算法面试题，热热身子。
正文
1.Beautiful Divisors
题目大意：
如果数字x的二进制表示，是由k+1个连续的1 与 k个连续的0组成，那么数字x是beautiful Number；
例如1和6就是beautiful Number：
1(2) = 1(10);
110(2) = 6(10);
给出数字n，求数字n最大的约数，并且这个约数是beautiful Number.
(1≤n≤105)
输入数据：
Examples
input
3
output
1
input
992
output
496
题目解析：
可以直接遍历<=n的所有数字，先判断约数，再判断是否为beautiful Number；
为了代码更简单，先枚举出来所有的beautiful Number，再从中选择一个最大且是n的约数的beautiful Number。
2.Pizza Separation
题目大意：
有三个人A,B,C玩剪刀石头布的游戏，但是每次只能两个人参与，于是他们三个人制定规则：
A和B先玩，C旁观；
游戏的胜者和旁观者继续游戏，败者旁观；
游戏按照这样的规则，重复继续。
他们把每次的胜负写在纸上，总共有n行；(1<=n<=100)
每行有一个数字a[i]; (1<=a[i]<=3，a[i]=1表示A胜，a[i]=2表示B胜，a[i]=3表示C胜）
现在根据这个胜负记录，判断游戏过程中是否存在错误记录的情况；（比如第一行是3 表示C胜，但是C没有参与游戏）
如果是正常的记录，输出YES;
如果是错误的记录，输出NO；
输入数据：
Examples
input
3
1
1
2
output
YES
input
2
1
2
output
NO
题目解析：
题目的逻辑非常清晰，记录每场游戏的参与者和胜者，按照规则判断是否存在不合理情况。
这里有一个优雅的实现，只记录旁观者，对于每一次胜利者，判断 是否为旁观者；
至于如何快速求出每次游戏的败者，我们记录的旁观者加入是t,每次输入的胜利者是x，那么有每次的败者s=6-t-x; （因为有x+t+s=6）
3.Mammoth's Genome Decoding
题目大意：
给出一个长度为n的字符串，分别由'A', 'C', 'G', 'T' and '?' 组成，?的字符可以变成ACGT中的任意一个字符。
现在需要把字符变成全部由ACGT组成，并且四个字符的数量相等。
如果有解，输出字符串；
如果无解，输出====。
n (4≤n≤255)
输入数据：
Examples
input
4
AGCT
output
AGCT
input
6
????G?
output
===
题目解析：
题目的思考点在于遇到 '?'之后，如何决策该变成哪个字符。
由贪心的思想可以知道，有一种决策是每次变为数量最少的字符。
最后只要满足最少的那个字符数量为n/4，且n%4等于0即可。
4. Servers
题目大意：
n个服务器，序号从1到n，有q个任务；
每个任务在t[i]秒的时间到，需要k[i]台服务器，每台占用d[i]秒的时间；
询问：当每个任务到达时，是否有足够的机器完成任务；
如果可以完成，则选择序号最小的机器，输出机器的序号和；
如果不能完成，输出-1；
输入数据：
n and q (1≤n≤100, 1≤q≤1e5)
t[i], k[i] and d[i] (1≤t[i]≤1e6, 1≤k[i]≤n, 1≤d[i]≤1000)
Examples
input
4 3
1 3 2
2 2 1
3 4 3
output
6
-1
10
样例解释：
第一个任务在第1秒到达，所有机器空闲，选择1、2、3号机器，所以输出6；
第二个任务在第2秒到达，这时空闲的机器只有机器4，任务无法完成，输出-1；
第三个任务在第3秒到达，所有机器都空闲，选择1、2、3、4号机器，输出10；
题目解析：
题目的描述很直接，按照规则选择一种调度的代码实现方式，输出结果即可。
有一种简单的实现：
用一个数组存储机器的空闲时间（数组下标就是序号），每次从机器中选择空闲的机器（按照序号从小到大），如果不能满足则输出-1；如果可以则输出序号和，然后更新数组的机器空闲时间（当前空闲时间+任务时间）。
5.Winter Is Coming
题目大意：
小明要过冬，冬天持续n天，每天有一个天气温度，用a[i]表示；
小明有两件衣服，分别是summer和winter的，每天只能选择穿一件衣服；
summer只能在温度>=0的时候穿，winter的衣服可以在任何温度穿；
summer的衣服可以一直穿，但是winter的衣服只能穿k天；
每天早上，小明可以选择换一次衣服，一开始的时候小明是穿summer 的衣服；
问最少需要换多少次衣服，小明才能过冬？如果不能，就输出-1.
输入数据：
n and k (1≤n≤2·1e5, 0≤k≤n)
(-20≤t[i]≤20)
Examples
input
4 3
-5 20 -3 0
output
2
input
4 2
-5 20 -3 0
output
4
题目解析：
询问的是最小的改变次数，先考虑动态规划。
需要记录的状态有当前已改变的次数，每次的抉择是换或者不换；
但是因为最大的改变次数可能为n，状态数过多，动态规划不可取。
从另外一个角度来思考，能不能过冬，取决于零度以下的天数。
那么先假设所有的冬天都穿winter的衣服，这样可以得到能否过冬。
此时穿衣的规则是遇到零度以下就穿winter，遇到零度及以上就穿summer，如果今天穿衣服和昨天不一样，那么改变次数加1；
这样得到最多的改变次数，但是保证能过冬天（如果winter的衣服够穿）
剩下的天数，再尽可能分配到winter与winter之间，减少改变次数。
假如有数据：
n = 8，k = 4
t[i] ={0 0 -1 0 0 -1 0 0}
分别第3、4、6、7天换衣服，winter的衣服用了2天，可以过冬。
剩下的2天可以分配到[1, 2], [4, 5], [7, 8]这三个区间，得到的最小的改变次数分别是4，2，3次。
可以看得出来，把天数分配前第一个winter前面是不划算的，分配给最后一个winter只能减少一次，分配给winter之间的能减少两次。
于是算法就变成：
统计winter的数量，以及winter之间天数，再统计最后一个winter到最后天数；
减去winter的天数，剩下的衣服耐久度，从间隔最小开始分配给winter之间的天数，每分配减少2次；最后看剩下的天数够不够最后一个winter到末尾的天数，够的话再减一。
思考：
为了方便实现，可在前面和最后加0。
总结
过去两年的三月都在求职，今年终于不用再面试，长吐一口气...
不安于现状的人，总有动力去学习和进步。如今虽然安稳，也要继续保持前进。学如逆水行舟----不进则退。
作者：落影loyinglin
链接：https://www.jianshu.com/p/100938c928f1
正文到此结束
热门推荐
相关文章
近期评论
-
你这基本没有更新呀，最近文章显示还是2019年的文章。不符合要求哈
-
关键词：慕云博客 链接：https://www.lilun.me 描述：分享原创文字的个人博客
-
-
-
可以提供一下源码吗
-
不是商业站，鸡娃学习笔记
-
-
-
-
听他们说很厉害的样子
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
