leetcode 第 407 场算法比赛

零、背景

比赛期间，697 个人通过四道题，可见题目不难。

A: 统计二进制1的个数。
B: 必胜博弈。
C: 贪心，前缀统计。
D: 贪心，栈优化。

排名：无
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/407

一、使两个整数相等的位更改次数

题目：给两个数字，一次操作可以将第一个数字值为1的位数由1修改为0，问几次操作可以将第一个数字修改为第二个数字。

思路：如果存在某一位，第二个数字为1，第一个数字为0，则不存在答案。
否则，第二个数字是第一个数字的子集，统计第一个数字比第二个数字多多少个1即可。

小技巧：异或运算可以快速得到不同 1 的个数。

二、字符串元音游戏

题目：给一个字符串，小红和小明轮流按规则操作字符串，最后无法操作的人输掉游戏。
小红：每次删除一个非空子串，子串包含奇数个元音。
小明：每次删除一个非空子串，子串包含偶数个元音。
问两人都采用最优策略，小红是否可以赢得游戏。

思路：博弈题型。

按元音个数分三种情况：

1）如果字符串有奇数个元音，小红删除整个字符串，则小明无法操作，因此小红必胜。
3）如果字符串有偶数个元音，小红删除最大奇数个元音的字符串，剩余的子串只有1个元音，小明无法操作，因此小红必胜。
3）特殊情况：如果输入字符串没有元音，则小红无法操作，因此小红必败。

三、将 1 移动到末尾的最大操作次数

题意：给一个字符串，每次操作可以将一个 1 和右边相邻的 0 不断交换，直到遇到 1 或者字符串结尾。
问如何操作，才能使得操作次数最大。

思路：可以同时思考如何操作答案才能最大与最小。

从右到左遍历移动，则答案最小。
从左到右遍历移动，则答案最大。

因此，按从左到右题意模拟移动即可。
复杂度：O(n^2)

优化：每个0前面连续的一段1，所有 1 的操作次数是相等的，都需要操作1次。
例如 11100, 后面连续有多个 0，前面每个 1 都需要向右操作1次。

因此可以统计前面连续 1 的个数，遇到第一个 0 时，累加操作次数即可。
复杂度：O(n)

四、使数组等于目标数组所需的最少操作次数

题意：给两个数组，每次可以选择一个区间对数组的值同时加一或者减一，问最少多少次操作，可以将第一个数组修改为第二个数组。

思路：第一眼看到题，感觉复杂度好高。

不过分析一下区间加一与区间减一的情况，会发现，同一个位置不可能同时加一又减一。
比如对区间 [1,10]加一，对区间[4,5]减一，则等价与对区间 [1,3]和[6,10]加一，操作次数不变。

如涉及边界时，加一区间和减一区间合并后，答案还会更优。
比如对区间 [1,10]加一，对区间 [4,10]减一，则只需要对区间[1,3]加一即可，操作次数有2次降低为 1次。

有了上面结论，从左到右看目标操作，便可以直接想到一个贪心策略。
如果第一个位置要操作 x 次，则可以往后看，后面是否可以顺便也操作 x 次，可以了便一起操作，不可以便停止向后探测。

第二个位置数显然是大于等于 x 次的，不妨设为 y 次，则从第二个位置开始，需要额外操作 y-x 次。
第三个位置不妨设为 z 次，且大于 x ，不大于 y，则第二个位置有 y-z次停止向后探测，z-x次可以继续向后探测。

看到这里，可以看到一个性质：单调栈。

操作变大的时候，入栈；
操作变小的时候，栈顶与当前差值计算出答案。
复杂度：O(n)

观察对栈的操作，会发现只关心栈顶这个最大值，即可以使用一个变量来标记这个最大值，此时栈都不需要了。

注意事项：需要考虑符号问题，符号变化，需要清空栈

五、最后

这次比赛不难，看最近几个月的比赛，4月21日到7月21日，3个月只有1个赞助商，说明就业环境还是相当不乐观的。

《完》

-EOF-

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