弄个盈利网站做什么,公司网公司网页设计制作,做视频投稿赚钱的网站,wordpress 版面Leetcode 2935. Maximum Strong Pair XOR II 1. 解题思路2. 代码实现 题目链接#xff1a;2935. Maximum Strong Pair XOR II
1. 解题思路
这一题又是一个限制条件下找“最大值”的问题#xff0c;不过这里的最大值是XOR之后的最大值。
而要求XOR之后结果的最大值#x…Leetcode 2935. Maximum Strong Pair XOR II 1. 解题思路2. 代码实现 题目链接2935. Maximum Strong Pair XOR II
1. 解题思路
这一题又是一个限制条件下找“最大值”的问题不过这里的最大值是XOR之后的最大值。
而要求XOR之后结果的最大值事实上我们只要找到这个数的位反结果即可因此我们通过一个trie树事实上很快就能找到这个数。而关于trie树的内容我们之前已经写过了一个博客经典算法Trie树结构简介对其进行介绍过了如果有不了解的同学可以直接跳转去快速了解一下这里就不展开赘述了。
剩下的问题就是如何来处理这个限制条件题中的限制条件要求 ∣ x − y ∣ ≤ m i n ( x , y ) |x-y| \leq \mathop{min}(x, y) ∣x−y∣≤min(x,y)
不妨设 x ≤ y x \leq y x≤y那么限制条件就是 y ≤ 2 x y \leq 2x y≤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 0trie 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。
