class Solution {
public:
int maximumStrongPairXor(vector<int>& nums) {
}
};
2932. 找出强数对的最大异或值 I
给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：
|x - y| <= min(x, y)你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。
返回数组 nums 所有可能的强数对中的 最大 异或值。
注意，你可以选择同一个整数两次来形成一个强数对。
示例 1：
输入：nums = [1,2,3,4,5]
输出：7
解释：数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。
示例 2：
输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。
示例 3：
输入：nums = [5,6,25,30]
输出：7
解释：数组 nums 中有 6 个强数对：(5, 5), (5, 6), (6, 6), (25, 25), (25, 30) 和 (30, 30) 。
这些强数对中的最大异或值是 25 XOR 30 = 7 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 5 XOR 6 = 3 。
提示：
1 <= nums.length <= 501 <= nums[i] <= 100原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 42.2 MB, 提交时间: 2023-11-13 20:40:34
class Node {
Node[] children = new Node[2];
int cnt; // 子树大小
}
class Trie {
private static final int HIGH_BIT = 6;
private Node root = new Node();
// 添加 val
public void insert(int val) {
Node cur = root;
for (int i = HIGH_BIT; i >= 0; i--) {
int bit = (val >> i) & 1;
if (cur.children[bit] == null) {
cur.children[bit] = new Node();
}
cur = cur.children[bit];
cur.cnt++; // 维护子树大小
}
}
//（懒惰）删除 val
// 要求 val 必须在 t 中
public void remove(int val) {
Node cur = root;
for (int i = HIGH_BIT; i >= 0; i--) {
cur = cur.children[(val >> i) & 1];
cur.cnt--; // 维护子树大小
}
}
// 返回 val 与 t 中一个元素的最大异或和
// 要求 t 不能为空
public int maxXor(int val) {
Node cur = root;
int ans = 0;
for (int i = HIGH_BIT; i >= 0; i--) {
int bit = (val >> i) & 1;
// 如果 cur.children[bit^1].cnt == 0，视作空节点
if (cur.children[bit ^ 1] != null && cur.children[bit ^ 1].cnt > 0) {
ans |= 1 << i;
bit ^= 1;
}
cur = cur.children[bit];
}
return ans;
}
}
public class Solution {
public int maximumStrongPairXor(int[] nums) {
Arrays.sort(nums);
Trie t = new Trie();
int ans = 0, left = 0;
for (int y : nums) {
t.insert(y);
while (nums[left] * 2 < y) {
t.remove(nums[left++]);
}
ans = Math.max(ans, t.maxXor(y));
}
return ans;
}
}
cpp 解法, 执行用时: 16 ms, 内存消耗: 25.8 MB, 提交时间: 2023-11-13 20:40:18
class Node {
public:
array<Node*, 2> children{};
int cnt = 0; // 子树大小
};
class Trie {
static const int HIGH_BIT = 6;
public:
Node *root = new Node();
// 添加 val
void insert(int val) {
Node *cur = root;
for (int i = HIGH_BIT; i >= 0; i--) {
int bit = (val >> i) & 1;
if (cur->children[bit] == nullptr) {
cur->children[bit] = new Node();
}
cur = cur->children[bit];
cur->cnt++; // 维护子树大小
}
}
//（懒惰）删除 val
// 要求 val 必须在 t 中
void remove(int val) {
Node *cur = root;
for (int i = HIGH_BIT; i >= 0; i--) {
cur = cur->children[(val >> i) & 1];
cur->cnt--; // 维护子树大小
}
}
// 返回 val 与 t 中一个元素的最大异或和
// 要求 t 不能为空
int max_xor(int val) {
Node *cur = root;
int ans = 0;
for (int i = HIGH_BIT; i >= 0; i--) {
int bit = (val >> i) & 1;
// 如果 cur.children[bit^1].cnt == 0，视作空节点
if (cur->children[bit ^ 1] && cur->children[bit ^ 1]->cnt) {
ans |= 1 << i;
bit ^= 1;
}
cur = cur->children[bit];
}
return ans;
}
};
class Solution {
public:
int maximumStrongPairXor(vector<int> &nums) {
sort(nums.begin(), nums.end());
Trie t;
int ans = 0, left = 0;
for (int y: nums) {
t.insert(y);
while (nums[left] * 2 < y) {
t.remove(nums[left++]);
}
ans = max(ans, t.max_xor(y));
}
return ans;
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2023-11-13 20:39:56
const highBit = 6
type node struct {
children [2]*node
cnt int // 子树大小
}
type trie struct{ root *node }
// 添加 val
func (t trie) insert(val int) *node {
cur := t.root
for i := highBit; i >= 0; i-- {
bit := val >> i & 1
if cur.children[bit] == nil {
cur.children[bit] = &node{}
}
cur = cur.children[bit]
cur.cnt++ // 维护子树大小
}
return cur
}
//（懒惰）删除 val
// 要求 val 必须在 t 中
func (t trie) remove(val int) *node {
cur := t.root
for i := highBit; i >= 0; i-- {
cur = cur.children[val>>i&1]
cur.cnt-- // 维护子树大小
}
return cur
}
// 返回 val 与 t 中一个元素的最大异或和
// 要求 t 不能为空
func (t trie) maxXor(val int) (ans int) {
cur := t.root
for i := highBit; i >= 0; i-- {
bit := val >> i & 1
// 如果 cur.children[bit^1].cnt == 0，视作空节点
if cur.children[bit^1] != nil && cur.children[bit^1].cnt > 0 {
ans |= 1 << i
bit ^= 1
}
cur = cur.children[bit]
}
return
}
func maximumStrongPairXor(nums []int) (ans int) {
slices.Sort(nums)
t := trie{&node{}}
left := 0
for _, y := range nums {
t.insert(y)
for nums[left]*2 < y {
t.remove(nums[left])
left++
}
ans = max(ans, t.maxXor(y))
}
return
}
python3 解法, 执行用时: 104 ms, 内存消耗: 15.9 MB, 提交时间: 2023-11-13 20:39:31
class Node:
__slots__ = 'children', 'cnt'
def __init__(self):
self.children = [None, None]
self.cnt = 0 # 子树大小
class Trie:
HIGH_BIT = 6
def __init__(self):
self.root = Node()
# 添加 val
def insert(self, val: int) -> None:
cur = self.root
for i in range(Trie.HIGH_BIT, -1, -1):
bit = (val >> i) & 1
if cur.children[bit] is None:
cur.children[bit] = Node()
cur = cur.children[bit]
cur.cnt += 1 # 维护子树大小
return cur
# （懒惰）删除 val
# 要求 val 必须在 trie 中
def remove(self, val: int) -> None:
cur = self.root
for i in range(Trie.HIGH_BIT, -1, -1):
cur = cur.children[(val >> i) & 1]
cur.cnt -= 1 # 维护子树大小
return cur
# 返回 val 与 trie 中一个元素的最大异或和
# 要求 trie 中至少有一个元素
def max_xor(self, val: int) -> int:
cur = self.root
ans = 0
for i in range(Trie.HIGH_BIT, -1, -1):
bit = (val >> i) & 1
# 如果 cur.children[bit^1].cnt == 0，视作空节点
if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:
ans |= 1 << i
bit ^= 1
cur = cur.children[bit]
return ans
class Solution:
def maximumStrongPairXor(self, nums: List[int]) -> int:
nums.sort()
t = Trie()
ans = left = 0
for y in nums:
t.insert(y)
while nums[left] * 2 < y:
t.remove(nums[left])
left += 1
ans = max(ans, t.max_xor(y))
return ans