本文涉及知识点
离线查询
C++前缀树(字典树)
位运算、状态压缩、枚举子集汇总
LeetCode1707. 与数组中元素的最大异或值
给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
示例 1：
输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
- 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
- 1 XOR 2 = 3.
- 5 XOR 2 = 7.
示例 2：
输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]
提示：
1 <= nums.length, queries.length <= 105
queries[i].length == 2
0 <= nums[j], xi, mi <= 109
离线查询、字典树
indexs 记录 queries的下标。queries[index[i]][1] 升序。
for( i: indexs){
将小于等于mi的nums元素加到字典树。
y = 查询字典树和xi的最大异或值。
vRet[i] = y;
}
离线查询、字典树代码
核心代码
class C2BNumTrieNode
{
public:
C2BNumTrieNode()
{
m_childs[0] = m_childs[1] = nullptr;
}
bool GetNot0Child(bool bFirstRight)
{
auto ptr = m_childs[bFirstRight];
if (ptr && (ptr->m_iNum > 0))
{
return bFirstRight;
}
return !bFirstRight;
}
int m_iNum = 0;
C2BNumTrieNode* m_childs[2];
};
template<class T = int, int iLeveCount = 31>
class C2BNumTrie
{
public:
C2BNumTrie()
{
m_pRoot = new C2BNumTrieNode();
}
void Add(T iNum)
{
m_setHas.emplace(iNum);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveCount - 1; i >= 0; i--)
{
p->m_iNum++;
bool bRight = iNum & ((T)1 << i);
if (nullptr == p->m_childs[bRight])
{
p->m_childs[bRight] = new C2BNumTrieNode();
}
p = p->m_childs[bRight];
}
p->m_iNum++;
}
void Del(T iNum)
{
auto it = m_setHas.find(iNum);
if (m_setHas.end() == it)
{
return;
}
m_setHas.erase(it);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveCount - 1; i >= 0; i--)
{
p->m_iNum--;
bool bRight = iNum & ((T)1 << i);
p = p->m_childs[bRight];
}
p->m_iNum--;
}
T MaxXor(T iNum)
{
C2BNumTrieNode* p = m_pRoot;
T iRet = 0;
for (int i = iLeveCount - 1; i >= 0; i--)
{
bool bRight = !(iNum & ((T)1 << i));
bool bSel = p->GetNot0Child(bRight);
p = p->m_childs[bSel];
if (bSel == bRight)
{
iRet |= ((T)1 << i);
}
}
return iRet;
}
void Swap(C2BNumTrie<T, iLeveCount>& o) {
swap(m_pRoot, o.m_pRoot);
swap(m_setHas, o.m_setHas);
}
C2BNumTrieNode* m_pRoot;
std::unordered_multiset<T> m_setHas;
};
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
const int n = nums.size();
vector<int> indexs(queries.size());
iota(indexs.begin(), indexs.end(), 0);
sort(indexs.begin(), indexs.end(), [&](int i1, int i2) {return queries[i1][1] < queries[i2][1]; });
sort(nums.begin(), nums.end(),std::greater<int>());
C2BNumTrie trie;
vector<int> ret(queries.size());
for (int i : indexs) {
while ((nums.size())&&(nums.back() <= queries[i][1])) {
trie.Add(nums.back());
nums.pop_back();
}
ret[i] = (nums.size()==n ) ? -1 : trie.MaxXor(queries[i][0]);
}
return ret;
}
};
测试用例
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector<int> nums;
vector<vector<int>> queries;
{
Solution slu;
nums = { 3 }, queries = { {2,2} };
auto res = slu.maximizeXor(nums, queries);
Assert({ -1 }, res);
}
{
Solution slu;
nums = { 2 }, queries = { {2,2} };
auto res = slu.maximizeXor(nums, queries);
Assert({ 0 }, res);
}
{
Solution slu;
nums = { 0,1,2,3,4 }, queries = { {3,1},{1,3},{5,6} };
auto res = slu.maximizeXor(nums, queries);
Assert({ 3,3,7 }, res);
}
{
Solution slu;
nums = { 5,2,4,6,6,3 }, queries = { {12,4},{8,1},{6,3} };
auto res = slu.maximizeXor(nums, queries);
Assert({ 15,-1,5 }, res);
}
}
2023年4月版
class C2BNumTrieNode
{
public:
C2BNumTrieNode()
{
m_childs[0] = m_childs[1] = nullptr;
}
bool GetNot0Child(bool bFirstRight)
{
auto ptr = m_childs[bFirstRight];
if (ptr && ( ptr->m_iNum >0 ))
{
return bFirstRight;
}
return !bFirstRight;
}
int m_iNum = 0;
C2BNumTrieNode* m_childs[2] ;
};
template
class C2BNumTrie
{
public:
C2BNumTrie()
{
m_pRoot = new C2BNumTrieNode();
}
void Add(int iNum)
{
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveNum - 1; i >= 0; i–)
{
p->m_iNum++;
bool bRight = iNum & (1 << i);
if (nullptr == p->m_childs[bRight])
{
p->m_childs[bRight] = new C2BNumTrieNode();
}
p = p->m_childs[bRight];
}
p->m_iNum++;
}
C2BNumTrieNode* m_pRoot;
};
class Solution {
public:
vector maximizeXor(vector& nums, vector<vector>& queries) {
const int iBitNum =30;
std::sort(nums.begin(), nums.end());
vector indexs;
for (int i = 0; i < queries.size(); i++)
{
indexs.emplace_back(i);
}
std::sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2)
{
return queries[i1][1] < queries[i2][1];
});
//std::priority_queue<int,vector,greater> queNums(nums.begin(), nums.end());
int iDoNums =0;
C2BNumTrie trie;
vector vRet(indexs.size());
for (int i = 0; i < indexs.size(); i++)
{
const int index = indexs[i];
const int iCur = queries[index][0];
const int iRev = iCur ^ ((1 << iBitNum)- 1);
const int iMax = queries[index][1];
while ((iDoNums < nums.size()) && (nums[iDoNums] <= iMax))
{
trie.Add(nums[iDoNums]);
iDoNums++;
}
if (0 == trie.m_pRoot->m_iNum)
{
vRet[index] = -1;
continue;
}
auto p = trie.m_pRoot;
int iSel = 0;
for (int i = iBitNum - 1; i >= 0; i--)
{
bool bRight = iRev & (1 << i);
bool bSel = p->GetNot0Child(bRight);
p = p->m_childs[bSel];
if (bSel)
{
iSel |= (1 << i);
}
}
vRet[index] = iSel^iCur;
}
return vRet;
}
};
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
