leetcode 第 382 场算法比赛

零、背景

这次比赛最后一题其实不难，但很有迷惑性。

A: 循环判断相邻字母变化次数。
B: 枚举最大值，判断最大答案。
C: 奇偶数个数。
D: 从高位到低位贪心。

一、按键变更的次数

题意：给一个字符串，问相邻字母值变化的次数。

思路：按题意循环判断即可。

二、子集中元素的最大数量

题意：给一个数组，求构造一个最长的数组，前一半相邻是平方关系，后一半是开方的关系。

思路：枚举起始位置或者中间位置即可。

枚举起始位置时，可能不存在答案，需要分情况判断。

枚举中间位置，由于对称性，只需要不断向两边扩展即可。

注意事项：1 比较有特殊，单独判断。

三、Alice 和 Bob 玩鲜花游戏

题意：两个数字，两个人轮流挑一个数字减一，减一后两个数字都是 0 时胜利。
告诉你两个数组的最大值，问第一个人胜利的数字对个数。

思路：数字和为奇数时胜利，枚举一个数字，统计另一个数字和的个数。

优化：矩阵和的奇偶性是对称的，所以每行奇数和偶数的个数确定的，可以直接分奇偶性找规律推导出公式直接计算答案。

四、给定操作次数内使剩余元素的或值最小

题意：给一个数组，每次操作可以选择相邻数字进行与运算，合并为一个数字，求 k 次操作后，剩余数字的或运算的最小值。

思路：贪心。

答案是剩余数字的或运算，显然优先处理高位，最后处理低位。

假设一个高位出现 x 个数字，则最少需要操作 x-1 次才能消除这一位，最多需要 x 次才能消除这一位。

问题：对于连续若干个数字高位都是 1，直接对连续区间合并，是否是最优的。

证明如下：
连续区间先进行合并，如果没有剩余，答案为x-1。
还有剩余，之后两边随便选择一个数字进行合并，答案为 x。

如果不对连续区间合并，则是区间一分为两半，左边的区间与左边的边界数字合并，右边的区间与右边的边界数字合并，答案为 x。

由此可以证明，连续区间合并，答案是最优的。

PS：比赛的时候我证明错了，证明的是贪心有反例，就放弃这道题了。

根据上面的贪心策略，从最高位开始，依次枚举，尝试消除这一位，看 k 次操作是否可行。

五、最后

这次比赛最后一题其实不难，只要想到连续区间可以直接合并，从高位枚举即可。

《完》

-EOF-

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