leetcode 第183算法比赛

零、背景

这次比赛的题都可以用来当做面试题，其中第二题和第四题面试中既有可能会遇到，建议学习一下。

一、最短的序列

题意：给一个数组，求一个子序列，使得子序列所有元素之和大于不在子序列元素的和。
如果存在多个这样的子序列，求最短的子序列。
如果依旧存在多个，求和最大的那个。

说明：题意有点绕，我们换一下思路。
给一个集合，将集合分为A和B两个没有交集的子集，我们需要返回子集A，但是需要满足几个条件。

1、子集A的元素之和大于子集B的元素之和。
2、子集A的个数应该尽量少。
3、满足条件2的情况下，子集A的和应该尽量大。

思路：排序从大到小取元素即可。

二、二进制变成1的步长

题意：给一个二进制字符串，通过下面的规则将二进制变成1。

1、如果二进制是偶数，除以2。
2、如果二进制是奇数，加1。

思路：如果是整数的话，直接模拟即可。

但是这里是字符串，也可以模拟，但是需要注意加1的时候需要进位。

进位分两种。
一种是中间有0，最高位不需要进位，循环进位即可。
一种是全是1，最高位需要进位，处理比较麻烦，字符串需要整体后移。

不过考虑到全是1的时候，答案是固定的，即加1然后不断的除0。
所以我们可以判断是不是全是1，是了直接根据长度计算出答案即可。

这样需要分四种状态来处理。

1、只剩下一位，结束。
2、最后一位是0，直接除2。
3、所有位数是1，此时答案固定，字符串长度加1。
4、最后一位是1，中间有0，加1进位，进入状态2。

这样代码只需要循环判断出于哪种状态即可。

当然，我分析了一下这几种状态，发现存在一个规律。

不考虑后缀0，如果中间有0，每加一次1，就会消去一个0。
这样中间0全部消去之后，就变成前缀全是1和后缀全是0的状态了。

1的个数当然也是大于1个的。
比如状态111000。
这种状态的答案是固定的，即字符串长度加1。

所以我们只需要统计中间0的个数以及是不是有多个1即可。

三、最长快乐字符串

题意：告诉我们abc三个字母的个数，我们使用这个三个字母构造一个最长的字符串。

条件：字符串中不能包含子串aaa、bbb、ccc。

思路：肯定可以构造出一个答案，关键在于怎么用上尽量多的字母来构造重构出尽量长的答案。

那什么时候没有答案呢？
可以想象，对于ccaccbcc字符串，c 再多一个肯定是用不上的。

所以最大的哪个数字必须满足三角不等式：c <= 2 * (a + b + 1)。
满足了，就肯定答案。

假设知道答案的长度了，怎么构造出这个答案呢？

我比赛的时候是排序，严格保证三个数字的大小关系，分四种情况构造出了答案。

赛后看其他人的代码，发现可以直接贪心，哪个数字大就放哪个字母。
想了想确实可以。
但是严格的证明推理我没能描述出来，大家自己想想吧。

四、石子游戏 III

题意：给一个数组，代表每堆石头的分数。
两个人依次选择，只能顺序选择1或2或3堆，问最终的最大分数。

思路：这个题是经典的博弈题，记忆化搜索即可。
当然，也可以成为动态规划题。

大概方法就是依次假设当前位置开始选择1个、2个、3个。
看哪个最优就选择哪个。

由于第三题我做了一个小时，这道题开始做的时候只剩5分钟了，虽然代码敲完了，但是被超时卡住了。
赛后把 unorder_map 或 map 修改成 vector 才过，也就是复杂度必须严格为O(n)，均摊O(n)也不行。

PS：原先使用的dfs递归，后来怕爆栈，改成了递推。

五、最后

这次比赛的题都不错，除了第三题其他的都可以当做面试题来考查大家。

为啥第三题不适合当面试题呢，因为是贪心题。
贪心题很容易变成知道了就知道，不知道就不知道，然而不能考查一个人的综合素质了。

现在想想，比赛的时候我犯了一个错误。
第三题我已经意识到比较复杂，但是又感觉能做出来。
就这样浪费了一个小时才通过，导致后面的题没时间做。

这里分享给大家一个可以借鉴的做题时间规划。

遇到一道题，题意5分钟读不懂，先跳过。
题意读懂后，思考10分钟还不确定算法的正确性，果断跳过这道题。
算法正确性确定后，20分钟敲不出代码，也要先跳过这道题。

毕竟后面的题可能更简单，这样后面的做完了，再回来慢慢研究前面的题。
做题的时间这样规划才是最优的。

当然，上面的策略没考虑榜单。
中间随时可以看下榜单，哪道题过的人多了做那道题一般没问题的。

当然，我这个方式是针对个人比赛的。
如果是团队比赛，那安排一个人先把所有题看一遍就行了。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code