程序员进阶之算法练习（二十六）
前言
金三银四，求职黄金月做算法面试题，热热身子。
正文
1.Chess For Three
题目链接 题目大意： 有三个人A,B,C玩剪刀石头布的游戏，但是每次只能两个人参与，于是他们三个人制定规则： 1、A和B先玩，C旁观； 2、游戏的胜者和旁观者继续游戏，败者旁观； 游戏按照这样的规则，重复继续。 他们把每次的胜负写在纸上，总共有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）
2.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。
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之间的能减少两次。
于是算法就变成： 1、统计winter的数量，以及winter之间天数，再统计最后一个winter到最后天数； 2、减去winter的天数，剩下的衣服耐久度，从间隔最小开始分配给winter之间的天数，每分配减少2次；最后看剩下的天数够不够最后一个winter到末尾的天数，够的话再减一。
思考?： 为了方便实现，可在前面和最后加0。
总结
过去两年的三月都在求职，今年终于不用再面试，长吐一口气... 不安于现状的人，总有动力去学习和进步。如今虽然安稳，也要继续保持前进。学如逆水行舟----不进则退。