leetcode 周赛 484 - 位运算

零、背景

这次比赛比较简单，速度再快一点点应该可以进入前 50 名。

A 题：集合统计
B 题：暴力枚举
C 题：贪心+前缀和
D 题：两重位运算二分

最终排名：68
代码仓库：https://github.com/tiankonguse/leetcode-solutions

一、统计残差前缀

题意：给一个字符串，问所有前缀中，前缀不同字符的个数等于前缀长度对 3 取模的值的前缀有多少个。

思路：前缀统计。

按照题意，统计每个前缀中不同字符的个数，然后判断是否等于前缀长度对 3 取模的值即可。

剪枝：不同字符个数大于 3 时，可以提前结束。

二、中心子数组的数量

题意：给一个数组，问有多少个子数组，满足子数组和等于子数组中某个元素的值。

思路：暴力枚举。

暴力枚举子数组时，动态维护前缀和与前缀元素集合，从而判断前缀和是否在前缀元素集合中。
复杂度：O(n^2)

三、统计凯撒加密对的数量

题意：给一个字符串数组，每次操作可以将一个字符串的所有字符值循环右移 1 位，问有多少个字符串二元组，满足操作后两个字符串相等。

思路：贪心。

字符串二元组的数量级是 n^2。
所以，复杂度上不允许先枚举二元组再判断是否相等。

发现每个字符串可以独立进行操作，很容易想到，先把每个字符串通过若干次操作对齐到同一个基准形态，然后再判断哪些字符串相等即可。

一种思路是对齐到第一个字符，然后通过哈希集合统计二元组个数。
这时候可以发现，计算偏移量时会出现负数，有点麻烦。

另一个更自然的思路是对齐到最后一个字符，这样就不存在负数了。

小技巧：遍历字符串集合超时的话，可以使用字符串 hash 值来代替字符串。

四、增加操作后最大按位与的结果

题意：给一个数组，每次可以选择一个元素加 1，问最多加 K 次时，选择一个大小为 m 的子集，求按位与的最大值。

思路：二分。

对于两个集合，如果集合 A 的最高位是第 a 位，集合 B 的最高位是第 b 位，且 a > b。
则显然，集合 A 的答案一定比集合 B 的答案大。

由此可以找到一个二分策略：从最高位开始枚举，假设这一位是 1，判断在给定操作次数限制下是否可行。

ll ans = 0;
for (int b = 30; b >= 0; b--) {
  ans |= (1LL << b);
  if (Cost(ans) > k) {
    ans ^= (1LL << b);
  }
}
return ans;

假设当前枚举到第 k 位了，该如何判断是否存在可行解呢？
显然，需要计算每一个数组元素在当前枚举值下满足条件的代价，判断最小的 m 个代价之和是否不大于 K。

这里需要求 m 个最小值，可以使用优先队列。

max_queue<ll> que;  
ll cost = 0;
for (ll v : nums) {
  ll x = Solver(v, ans);
  cost += x;
  que.push(x);
  if (que.size() > m) {
    cost -= que.top();
    que.pop();
  }
}

这时候，问题就转化为了，对于一个数字，怎么计算它满足枚举值的代价。

假设数 v 小于枚举值 ans，则显然，代价就是 ans - v。

当 v 大于 ans 时，最常见的情况是 v 的最高位大于 ans 的最高位。
显然，这时候 v 的最高位没有意义，需要忽略。

更普遍的情况是，v 和 ans 有一个公共的最高位，接下来的某一位上，v 是 1，ans 是 0。
这时候，v 的这一位也是没有意义的，需要忽略。

由此，可以得到一个计算代价的函数：从高位到低位枚举，把 ans 中为 1 的某一位当作分界点，只保留这一位及其以下的二进制位，使得截断后的 v2 不大于 ans2，从而保证 v2 ≤ ans2，再计算二者的差值作为代价。

ll Solver(ll v, ll ans) {
  if (v <= ans) {
    return ans - v;
  }
  for (int b = 31; b >= 0; b--) {
    if ((ans & (1LL << b)) == 0) {
      continue;
    }
    ll mask = (1LL << (b + 1)) - 1;
    ll v2 = v & mask;
    ll ans2 = ans & mask;
    if (ans2 >= v2) {
      return ans2 - v2;
    }
  }
  return 0;
}

复杂度：O(n log(n) log(n))

五、最后

这次比赛最后一题说难，其实也不算特别难，但细节还是有点绕。
总之只要想到从最高位开始处理，整体思路就简单了，接下来主要就是一些实现细节了。

《完》

-EOF-

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