Leetcode 2935. Maximum Strong Pair XOR II

• Leetcode 2935. Maximum Strong Pair XOR II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2935. Maximum Strong Pair XOR II

1. 解题思路

这一题又是一个限制条件下找“最大值”的问题，不过这里的最大值是XOR之后的最大值。

而要求XOR之后结果的最大值，事实上我们只要找到这个数的位反结果即可，因此，我们通过一个trie树事实上很快就能找到这个数。而关于trie树的内容，我们之前已经写过了一个博客（经典算法：Trie树结构简介）对其进行介绍过了，如果有不了解的同学可以直接跳转去快速了解一下，这里就不展开赘述了。

剩下的问题就是如何来处理这个限制条件，题中的限制条件要求：

$$|x-y|\le \min (x,y)$$

不妨设$x\le y$，那么限制条件就是$y\le 2x$。

因此，我们对原数组去重排序之后，就可以通过一个滑动窗口来确保每一次query过程中，trie树当中所有的数字均可满足上述限制条件。

只不过，这里我们需要特殊一点实现一个trie树的元素删除操作。

2. 代码实现

给出python代码实现如下：

class Trie:def __init__(self):self.trie = {}def add(self, num):trie = self.triefor digit in num:trie = trie.setdefault(digit, {})trie["eos"] = numdef find(self, num):trie = self.triefor digit in word:if digit not in trie:return Falsetrie = trie[digit]return "eos" in triedef find_closest(self, num):trie = self.triefor digit in num:if digit not in trie:digit = "1" if digit == "0" else "0"trie = trie[digit]return trie["eos"]def remove(self, num):tries = []trie = self.triefor digit in num:tries.insert(0, (digit, trie))trie = trie[digit]for digit, trie in tries:trie.pop(digit)if len(trie) > 0:breakreturnclass Solution:def maximumStrongPairXor(self, nums: List[int]) -> int:def num2digit(num):ans = bin(num)[2:]return ans.rjust(20, "0")def digit2num(digits):ans = 0for digit in digits:ans = ans * 2 + int(digit)return ansdef reverse(digits):return "".join(str(1-int(d)) for d in digits)trie = Trie()nums = sorted(set(nums))r, n = 0, len(nums)ans = 0for num in nums:while r < n and nums[r] <= 2 * num:digits = num2digit(nums[r])trie.add(digits)r += 1digits = num2digit(num)tgt = reverse(digits)ret = trie.find_closest(tgt)ret = digit2num(ret)ans = max(ans, ret^num)trie.remove(digits)return ans

提交代码评测得到：耗时4674ms，占用内存79.6MB。