千问 LeetCode 2935. 找出强数对的最大异或值 II JavaScript实现

这是一道经典的“字典树Trie 滑动窗口”的算法题。在开始写代码前我们先来梳理一下解题的核心思路 核心思路1. 转化强数对条件题目给出的条件是 |x - y| min(x, y)。为了方便处理我们可以先对数组进行升序排序。假设排序后 x y那么 min(x, y) 就是 x绝对值 |x - y| 就是 y - x。原条件转化为y - x x即 y 2 * x。也就是说对于数组中任意两个数只要满足 x y 2 * x它们就是一对强数对。2. 滑动窗口维护有效区间我们遍历排序后的数组将当前遍历到的数作为较大的数 y。我们需要在前面已经遍历过的数中找到一个满足 y 2 * x即 x y / 2的最小的 x从而确定一个合法的滑动窗口 [left, right]。窗口内的所有数都可以作为 x 与当前的 y 组成强数对。3. 字典树Trie求最大异或值为了让异或值 x XOR y 最大我们需要让二进制的高位尽可能不同即 0 配 11 配 0。我们可以将滑动窗口内的所有 x 存入一棵 01 字典树中。对于当前的 y我们在字典树中从高位到低位贪心地寻找与 y 当前位相反的路径从而得到当前窗口内与 y 异或结果最大的值。 JavaScript 代码实现// 字典树节点类class TrieNode {constructor() {this.children [null, null]; // 0 和 1 两个子节点this.cnt 0; // 记录经过该节点的数字个数用于删除操作}}var maximumStrongPairXor function(nums) {// 1. 排序数组方便使用滑动窗口和转化条件nums.sort((a, b) a - b);const root new TrieNode();let left 0; // 滑动窗口的左边界let max_xor 0;// 辅助函数向字典树中插入或删除一个数字// delta 1 表示插入delta -1 表示删除const updateTrie (val, delta) {let node root;// 题目提示 nums[i] 2^20所以从第 19 位开始遍历即可for (let i 19; i 0; i--) {const bit (val i) 1;if (!node.children[bit]) {node.children[bit] new TrieNode();}node node.children[bit];node.cnt delta;}};// 辅助函数在字典树中查找与 val 异或最大的值const findMaxXor (val) {let node root;let xor_val 0;for (let i 19; i 0; i--) {const bit (val i) 1;// 贪心策略优先走与当前位相反的路径bit ^ 1// 且该路径对应的节点必须存在且计数大于 0if (node.children[bit ^ 1] node.children[bit ^ 1].cnt 0) {xor_val | (1 i); // 该位异或结果为 1node node.children[bit ^ 1];} else {// 否则只能走相同的路径node node.children[bit];}}return xor_val;};// 2. 遍历数组将当前数字作为强数对中较大的数 yfor (let right 0; right nums.length; right) {const y nums[right];// 先将当前的 y 加入字典树它既可以是 y也可以作为后面更大数的 xupdateTrie(y, 1);// 3. 维护滑动窗口如果窗口最左边的 x 不满足 y 2 * x则将其移出窗口while (nums[left] * 2 y) {updateTrie(nums[left], -1);left;}// 4. 在当前的合法窗口中查找与 y 异或最大的值并更新全局最大值max_xor Math.max(max_xor, findMaxXor(y));}return max_xor;}; 复杂度分析* 时间复杂度O(N log N N log C)。其中 N 是数组长度log N 来自排序log C 来自字典树的插入、删除和查询操作C 是数字的最大值这里约为 2^20。* 空间复杂度O(N log C)。字典树在最坏情况下需要存储所有数字的二进制位。