leetcode 第 372 场算法比赛

零、背景

这次比赛家里有事，没参加，现在有空了，补做下比赛。

这次比赛最后一题很有意思，求区间内大于等于的第一个数字，好题目

比赛代码:
https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、使三个字符串相等

题意：给三个字符串，可以删除任意长度的后缀，问如何操作才能使三个字符串相等。

思路：找到最长公共前缀，其余的都需要删除。

二、区分黑球与白球

题意：给一个数组，不是黑球就是白球，每次异动可以交换相邻的球。
现在需要将所有的黑球移动到右边，所有的白球移动到左边，求最小移动次数。

思路：假设白球左边有连续 k 个黑球，则至少移动 k 次才能使得白球到达左边。
所以可以从左到右统计连续的黑球个数 k，遇到白球，就交换 k 次把白球移动到左边。
复杂度：O(n)

三、最大异或乘积

题意：给三个数字 a、b、n，求一个x，满足0 <= x < 2^n，使得(a XOR x) * (b XOR x)的值最大。

思路： 很有意思的一道题，需要根据比特位的值分情况处理。

定义 a[i] 代表 a 的第 i 位的值。

1 位比特位情况

则 a 和 b 的各位关系分 4 中情况：

-）a[i]=1 & b[i]=1,此时 x[i]需要位 0 答案才会更大。
-）a[i]=0 & b[i]=0,此时 x[i]需要位 1 答案才会更大。
-）a[i]=1 & b[i]=0,分情况讨论。
-）a[i]=0 & b[i]=1,分情况讨论。

根据上面的四种情况，如果 a 和 b 比特位相等时，x 的比特位也是很明确的。
如果 a 和 b 比特位不同，则 x 的取值会影响答案的大小。

假设其他位的值是 A 和 B，且 A 大于 B。
我们可以把第 i 位加到 A 上，也可以加到 B上，大小如下。

(A+i)*B = AB+Bi
A*(B+i) = AB+Ai

可以得出结论：第 i 位应该加到较小的那一个数字上。

多位比特位情况

1 位比特位情况得出的结论是谁小，比特位加到谁身上。

那有多位比特位时，会不会导致原先较小的数字变大呢？

如果处理比特位时，没有固定顺序，确实会这样。
但比特位从高到低处理时，一个数字加了高位的值，低位所有位加起来也不会超过高位。
即2^i>sum(2^j)。

由此我们可以得出结论：相同比特位两个数字值相等，最高不同位给一个数字，其他不同位都给另外一个数字即可。

特殊情况

x 有一个限制 [0,2^n)，这意味着 x 的位数只能是 [0, n)。
对于大于等于 n 位的比特位，我们不能进行异或修改。

如果存在这种情况，则一开始两个数字的值是不同的。

由此可以得出结论：所有不同位都给较小的那个数字。

复杂度：O(n)

四、找到 Alice 和 Bob 可以相遇的建筑

题意：给一个数组，每个位置可以移动到右边大于当前值的位置。
有若干询问，问两个位置向右移动，可以首次在哪个位置相遇。

思路：抽象一下是问后缀中，第一个大于指定值的位置。

典型的做法是线段树求区间最大值，然后二分线段树，找到第一个满足要求的位置。
复杂度：O(q log(n)^2)

其实这道题还可以使用单调栈来做。

分析一个后缀，如果一个位置大于后面的位置，则后面的位置肯定不会是答案。
所以这个后缀可以预处理为单调递增序列。
计算答案时，在单调递增序列上二分查找即可。

多个询问如何维护单调栈呢？
离线预处理询问，边维护单调栈边查询答案即可。

具体是查询按右区间排序，右区间从大到小查询即可。
复杂度：O(q log(n))

五、最后

这次比赛第三题和第四题都有一定的难度。
第三题需要画出公式，计算出比特位不同时，需要加到较小的那个数字。
第四题则是区间第一个满足要求的题型，通用模版是二分线段树，优化方法是二分单调栈。

《完》

-EOF-

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