本文涉及知识点
离线查询
C++前缀树(字典树)
C++DFS
LeetCode1938. 查询最大基因差
给你一棵 n 个节点的有根树，节点编号从 0 到 n - 1 。每个节点的编号表示这个节点的 独一无二的基因值 （也就是说节点 x 的基因值为 x）。两个基因值的 基因差 是两者的 异或和 。给你整数数组 parents ，其中 parents[i] 是节点 i 的父节点。如果节点 x 是树的 根 ，那么 parents[x] == -1 。
给你查询数组 queries ，其中 queries[i] = [nodei, vali] 。对于查询 i ，请你找到 vali 和 pi 的 最大基因差 ，其中 pi 是节点 nodei 到根之间的任意节点（包含 nodei 和根节点）。更正式的，你想要最大化 vali XOR pi 。
请你返回数组 ans ，其中 ans[i] 是第 i 个查询的答案。
示例 1：
输入：parents = [-1,0,1,1], queries = [[0,2],[3,2],[2,5]]
输出：[2,3,7]
解释：查询数组处理如下：
- [0,2]：最大基因差的对应节点为 0 ，基因差为 2 XOR 0 = 2 。
- [3,2]：最大基因差的对应节点为 1 ，基因差为 2 XOR 1 = 3 。
- [2,5]：最大基因差的对应节点为 2 ，基因差为 5 XOR 2 = 7 。
示例 2：
输入：parents = [3,7,-1,2,0,7,0,2], queries = [[4,6],[1,15],[0,5]]
输出：[6,14,7]
解释：查询数组处理如下：
- [4,6]：最大基因差的对应节点为 0 ，基因差为 6 XOR 0 = 6 。
- [1,15]：最大基因差的对应节点为 1 ，基因差为 15 XOR 1 = 14 。
- [0,5]：最大基因差的对应节点为 2 ，基因差为 5 XOR 2 = 7 。
提示：
2 <= parents.length <= 105
对于每个 不是 根节点的 i ，有 0 <= parents[i] <= parents.length - 1 。
parents[root] == -1
1 <= queries.length <= 3 * 104
0 <= nodei <= parents.length - 1
0 <= vali <= 2 * 105
深度优先
一，将父节点转为邻接点。
二，m_vVal记录各节点对应queries的下标，一个节点可能对应多个下标。
三，深度优先。字典树只记录cur节点及其祖先的基因。DFS开始 把cur加到字典树，DFS结束时，将cur从字典树删除。
深度优先代码
核心代码
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--;
}
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;
};
template<class T = int, int iLeveCount = 31>
class CMaxXor2BTrie : public C2BNumTrie<T, iLeveCount>
{
public:
T MaxXor(T iNum)
{
C2BNumTrieNode* p = C2BNumTrie<T, iLeveCount>::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;
}
};
class Solution {
public:
vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) {
m_c = parents.size();
m_vRet.resize(queries.size());
vector<vector<int>> vNeiBo(m_c);
int root = -1;
for (int i = 0; i < parents.size(); i++) {
if (-1 == parents[i]) { root = i; continue; }
vNeiBo[parents[i]].emplace_back(i);
}
m_vQue.resize(m_c);
for (int i = 0; i < queries.size(); i++) {
m_vQue[queries[i][0]].emplace_back(i);
}
DFS(vNeiBo, root, queries);
return m_vRet;
}
void DFS(vector<vector<int>>& neiBo, int cur, const vector<vector<int>>& queries)
{
m_tree.Add(cur);
for (const auto& i : m_vQue[cur]) {
m_vRet[i] = m_tree.MaxXor(queries[i][1]);
}
for (const auto& next : neiBo[cur])
{
DFS(neiBo, next, queries);
}
m_tree.Del(cur);
}
vector<vector<int>> m_vQue;
vector<int> m_vRet;
int m_c;
CMaxXor2BTrie<> m_tree;
};
测试用例
{
Solution slu;
parents = { -1,0,1,1 }, queries = { {0,2},{3,2},{2,5} };
auto res = slu.maxGeneticDifference(parents, queries);
Assert({ 2,3,7 }, res);
}
{
Solution slu;
parents = { 3,7,-1,2,0,7,0,2 }, queries = { {4,6},{1,15},{0,5} };
auto res = slu.maxGeneticDifference(parents, queries);
Assert({ 6,14,7 }, res);
}
{
Solution slu;
parents ={ -1,0,0,0,3 },queries ={ {4,6},{0,0},{0,3},{1,8},{4,0} };
auto res = slu.maxGeneticDifference(parents, queries);
Assert({ 6,0,3,9,4 }, 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)
{
m_setHas.emplace(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++;
}
void Del(int iNum)
{
auto it = m_setHas.find(iNum);
if (m_setHas.end() == it)
{
return;
}
m_setHas.erase(it);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveNum - 1; i >= 0; i–)
{
p->m_iNum–;
bool bRight = iNum & (1 << i);
p = p->m_childs[bRight];
}
p->m_iNum–;
}
int MaxXor(int iNum)
{
C2BNumTrieNode* p = m_pRoot;
int iRet = 0;
for (int i = iLeveNum - 1; i >= 0; i–)
{
bool bRight = !(iNum & (1 << i));
bool bSel = p->GetNot0Child(bRight);
p = p->m_childs[bSel];
if (bSel == bRight)
{
iRet |= (1 << i);
}
}
return iRet;
}
C2BNumTrieNode* m_pRoot;
std::unordered_multiset m_setHas;
};
class Solution {
public:
vector maxGeneticDifference(vector& parents, vector<vector>& queries) {
m_c = parents.size();
m_vNeiBo.resize(m_c);
m_vIndexQue.resize(m_c);
for (const auto& v : queries)
{
m_vIndexQue[v[0]][v[1]]=0;
}
int iRoot = -1;
for (int i = 0; i < m_c; i++)
{
const int iParent = parents[i];
if (-1 == iParent)
{
iRoot = i;
}
else
{
m_vNeiBo[parents[i]].emplace_back(i);
}
}
dfs(iRoot);
vector vRet;
for (const auto& v : queries)
{
vRet.emplace_back(m_vIndexQue[v[0]][v[1]]);
}
return vRet;
}
void dfs(int iCur)
{
m_nt.Add(iCur);
for (auto& it : m_vIndexQue[iCur])
{
it.second = m_nt.MaxXor(it.first);
}
for (const auto& next : m_vNeiBo[iCur])
{
dfs(next);
}
m_nt.Del(iCur);
}
int m_c;
vector<vector> m_vNeiBo;
vector<std::unordered_map<int,int>> m_vIndexQue;
C2BNumTrie<20> m_nt;
};
