leetcode 周赛 489

零、背景

这次比赛在农历腊月二十八，第二天就是除夕，家里有事，因此我没有参加比赛。
后来抽时间补做了四道题。
其中最后一题信息量很大，需要把滑动窗口、单调队列、前缀异或和字典树串起来。

本场题型概览如下。
A 题：统计。
B 题：统计。
C 题：枚举 + 动态规划。
D 题：滑动窗口 + 单调队列 + 前缀异或 + 字典树。

最终排名：未参赛。
代码仓库：详见 https://github.com/tiankonguse/leetcode-solutions。

一、切换灯泡开关

题意：给一个数组，数组中的值表示需要操作的开关编号。
初始时所有开关都是关闭状态。
每次操作会把对应开关的状态翻转（开 ↔ 关）。
最终按升序输出所有处于打开状态的开关编号。

思路：统计。
按题意统计每个开关被操作的次数。
操作次数为奇数的开关最终为打开状态。
把这些编号收集并排序即可。

二、频率唯一的第一个元素

题意：给一个数组，返回数组中“频率唯一”的第一个元素。
这里的“频率唯一”指该元素的出现次数在所有出现次数中只出现一次。
如果不存在，返回 -1。

思路：两次计数。
先统计每个元素出现的频次。
再统计每个频次出现的次数。
最后遍历原数组，检查当前元素的频次对应的“频次计数”是否为 1。
若为 1，则该元素就是答案。

三、最长的准回文子字符串

题意：给一个字符串，求一个最长子串，使得恰好删除其中一个字符后，剩余字符串是回文串。

思路：枚举中心 + 动态规划预处理扩展信息。

回文可以按中心分成奇数长度与偶数长度两类，因此中心需要分别枚举。
对每个中心，用双指针向两侧扩展。
当遇到第一对不相等字符 (l, r) 时，必须删除其中一个字符才能继续保持回文结构。
因此只需要分两种情况继续计算：删除左侧字符，或删除右侧字符。

为了让“删除后还能继续向外扩展多少”可以快速得到，我用一个二维 DP 预处理“从一对边界开始还能连续匹配多少”。
状态定义：dp[l][r] 表示从下标对 (l, r) 开始，向两侧继续扩展时还能连续匹配的字符对数量。
状态转移：若 s[l] == s[r]，则 dp[l][r] = dp[l - 1][r + 1] + 1，否则 dp[l][r] = 0。
有了 dp 之后，当中心扩展遇到不匹配时，就能在“删左/删右”两种分支里快速补上剩余可扩展的长度。

边界需要额外注意两类情况。
如果从中心向外扩展一直匹配到边界，则不会命中“不匹配”分支。
如果某一侧边界还有剩余字符，则答案可以加一，否则需要回滚一对匹配，来进行删除，即答案需要减一。

对于偶数的情况，与奇数类似。
唯一需要注意的是，可以删除中心两点中间的字符。

复杂度：O(n^2)。

四、最大子数组异或值

题意：给一个数组与整数 k。
在所有满足“子数组最大值与最小值之差不超过 k”的子数组中，求子数组元素异或值的最大值。

思路：按思考过程记录三种做法。

方法 1：暴力枚举。
复杂度：O(n^2)。
通过的测试用例：1010 / 1015。

方法 2：剪枝（比赛时的提速尝试）。
策略：连续相同的元素超过 2 个时，保留 2 个即可。
得分：100 分。
耗时：2331ms。

方法 3：滑动窗口 + 单调队列 + 前缀异或 + 字典树。
这题和上次双周赛的第三题很像，核心都是维护满足“最值之差”的区间。
因此可以固定右端点，用滑动窗口配合单调队列维护窗口内的最大值与最小值，并得到当前右端点对应的最远左端点。

deque<pair<int, int>> maxVal, minVal;
const int v = nums[i - 1];
while (!maxVal.empty() && maxVal.back().first <= v) {
  maxVal.pop_back();
}
maxVal.push_back({v, i});
while (!minVal.empty() && minVal.back().first >= v) {
  minVal.pop_back();
}
minVal.push_back({v, i});

接下来需要在满足约束的左边界范围内，找到一个左端点，使得区间异或值最大。
用前缀异或可以把区间异或转成两个前缀的异或：区间 [l, r] 的异或值等于 preXor[r] ^ preXor[l - 1]。
所以当右端点固定为 r 时，本质是在允许的前缀集合里找一个 preXor[x]，使得 preXor[x] ^ preXor[r] 最大。
这个“最大异或配对”问题可以用二进制字典树（Trie）高效求解。

Trie 的查询规则是贪心的。
从高位到低位遍历，若当前位为 v，则优先走 1 - v 的分支以获得更大的异或贡献。
若该分支不存在（或计数为 0），则只能走 v 分支。

int Search(const int& word) {
  int root = 0;
  for (int i = MaxBit - 1; i >= 0; i--) {
    int v = (word >> i) & 1;
    v = 1 - v;  // 优先选择相反的 bit
    if (nodes[root].next[v] == -1 || Count(nodes[root].next[v]) == 0) {
      root = nodes[root].next[1 - v];
    } else {
      root = nodes[root].next[v];
    }
  }
  return nodes[root].endFlag ^ word;
}

最后的问题是：窗口左端点在移动，Trie 里需要维护的是“当前合法左端点范围对应的前缀异或值集合”。
做法是给 Trie 的每个节点维护计数，支持插入与删除。
当单调队列推动左边界右移时，把落在窗口之外的前缀值从 Trie 中删除。
随后把当前右端点对应的前缀值插入 Trie，并查询一次最大值即可。

while (maxVal.front().first - minVal.front().first > k) {
  int offset;
  if (maxVal.front().second < minVal.front().second) {
    offset = maxVal.front().second;
    maxVal.pop_front();
  } else {
    offset = minVal.front().second;
    minVal.pop_front();
  }
  // [leftOffset, offset) 的前缀和都需要删除
  while (leftOffset < offset) {
    trie.Erase(preSum[leftOffset]);
    leftOffset++;
  }
}

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

五、最后

这次比赛的最后一题确实比较难。
把单调队列（维护区间最值）、滑动窗口（动态维护合法区间）、前缀异或（区间转两前缀）和 Trie（最大异或查询）拼在一起，才得到最终解法。

《完》。

-EOF-

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