01trie 在面試中的妙用
簡介
就是把整數(shù)的二進制表達式當(dāng)作字符串，之前寫過一篇字典樹，按照從高位到低位的順序，掛載在字典樹上，每個節(jié)點有兩個孩子，分別是 ，從而形成一棵二叉樹，常用來處理異或問題
例如將一個數(shù)組 掛在 上，便得到如下所示的一棵二叉樹
性質(zhì)
由于 是一棵二叉樹，且最大深度取決于掛載值的大小，設(shè)掛載最大值為 ，那么一次查詢前綴的過程便可以在 時間完成
例題
力扣 421. 數(shù)組中兩個數(shù)的最大異或值
給定 個正整數(shù)的數(shù)組 ，計算 的最大值
數(shù)據(jù)規(guī)定
題解
將數(shù)組中所有正整數(shù)的二進制表示，按照從高位到低位的順序，當(dāng)作字符串掛載在字典樹上，形成 字典樹，該字典樹為一棵二叉樹
對于正整數(shù) ，為了尋找數(shù)組中的 ，使得 最大，我們只要每次貪心走與當(dāng)前位相反的路即可
具體來講，如果當(dāng)前位為 ，我們走 子樹，反之走 子樹，當(dāng)然，如果不存在對應(yīng)的子樹，我們還是得走存在的子樹
這樣可以保證異或后的高位盡可能為 ，在二進制表示中，高位為 ，即使剩下的全 ，結(jié)果也要比高位為 ，剩下的全 結(jié)果大，直觀的感受，，這便證明了貪心的正確性
時間復(fù)雜度為 ，其中
//?cpp
const?int?N?=?2e4;
const?int?M?=?31;
class?Solution?{
public:
????int?node[N?*?M][2],?cnt?=?0;
????void?insert(int?x)
????{
????????int?p?=?0;
????????for?(int?i?=?M;?i?>=?0;?--i)?{
????????????int?idx?=?1?&?(x?>>?i);
????????????if?(!node[p][idx])?node[p][idx]?=?++cnt;
????????????p?=?node[p][idx];
????????}
????}
????int?query(int?x)
????{
????????int?p?=?0;
????????int?ans?=?0;
????????for?(int?i?=?M;?i?>=?0;?--i)?{
????????????int?idx?=?1?&?(x?>>?i);
????????????if?(node[p][idx?^?1])?{
????????????????ans?*=?2,?ans?+=?1;
????????????????p?=?node[p][idx?^?1];
????????????}
????????????else?{
????????????????ans?*=?2,?ans?+=?0;
????????????????p?=?node[p][idx];
????????????}
????????}
????????return?ans;
????}
????int?findMaximumXOR(vector<int>&?nums)?{
????????for?(auto?&i:?nums)?insert(i);
????????int?ans?=?0;
????????for?(auto?&i:?nums)?ans?=?max(ans,?query(i));
????????return?ans;
????}
};
力扣 1707. 與數(shù)組中元素的最大異或值
給定 個正整數(shù)的數(shù)組 ，給定 個詢問，每個詢問包含兩個正整數(shù)
對于每一個詢問，在 中所有不大于 的數(shù)中選一個 ，使得 最大，返回這個最大值
數(shù)據(jù)規(guī)定
題解
離線查詢，對 從小到大排序，對 按照 從小到大排序
根據(jù)單調(diào)性，使用雙指針，將 中符合條件的正整數(shù) 掛載到字典樹上，進行查詢即可
時間復(fù)雜度為 ，其中
//?cpp
#define?pb?push_back
const?int?N?=?1e5;
const?int?M?=?30;
class?Solution?{
public:
????int?node[N?*?M][2],?cnt?=?0;
????void?insert(int?x)
????{
????????int?p?=?0;
????????for?(int?i?=?M;?i?>=?0;?--i)?{
????????????int?idx?=?1?&?(x?>>?i);
????????????if?(!node[p][idx])?node[p][idx]?=?++cnt;
????????????p?=?node[p][idx];
????????}
????}
????int?query(int?x)
????{
????????int?p?=?0;
????????int?ans?=?0;
????????for?(int?i?=?M;?i?>=?0;?--i)?{
????????????int?idx?=?1?&?(x?>>?i);
????????????if?(node[p][idx?^?1])?{
????????????????ans?*=?2,?ans?+=?1;
????????????????p?=?node[p][idx?^?1];
????????????}
????????????else?{
????????????????ans?*=?2,?ans?+=?0;
????????????????p?=?node[p][idx];
????????????}
????????}
????????return?ans;
????}
????vector<int>?maximizeXor(vector<int>&?nums,?vector<vector<int>>&?q)?{
????????int?idx?=?0;
????????for?(auto?&i:?q)?i.pb(idx++);
????????sort(q.begin(),?q.end(),?[&](const?vector<int>?&x,?const?vector<int>?&y){
????????????return?x[1]?<?y[1];
????????});
????????sort(nums.begin(),?nums.end());
????????int?n?=?q.size();
????????vector<int>?ans(n);
????????for?(int?i?=?0,?j?=?0;?i?<?n;?++i)?{
????????????while?(j?<?nums.size()?&&?nums[j]?<=?q[i][1])
????????????????insert(nums[j++]);
????????????if?(!j)?ans[q[i][2]]?=?-1;
????????????else?ans[q[i][2]]?=?query(q[i][0]);
????????}
????????return?ans;
????}
};
力扣 1938. 查詢最大基因差
給定一棵 個節(jié)點的樹，每個節(jié)點的編號 即為其權(quán)值
給定 個查詢，每個查詢包含樹上一個點的編號 和目標值
對于每一個查詢，你需要選一個從根到 的節(jié)點 ，要求使得 值最大，返回這個最大值
數(shù)據(jù)規(guī)定
題解
離線查詢，維護每個節(jié)點的所有查詢
我們需要維護一個從根到當(dāng)前節(jié)點的路徑，因此考慮 dfs
具體來講，深搜到當(dāng)前點 時，將 掛載在 01 trie 上，同時進行一次查詢，計算出最大的異或值，繼續(xù)向下深搜，等到回溯的時候，將當(dāng)前節(jié)點的權(quán)值從字典樹上刪除
計算最大異或值時，每次貪心選擇與當(dāng)前位相反的節(jié)點即可
時間復(fù)雜度為 ，其中
//?cpp
#define?pii?pair<?int,?int?>
#define?fi?first
#define?se?second
#define?pb?push_back
const?int?N?=?2e5;
const?int?M?=?18;
int?node[N?*?M][2],?bucket[N?*?M][2],?cnt?=?0;
void?insert(int?x)
{
????int?p?=?0;
????for?(int?i?=?M;?i?>=?0;?--i)?{
????????int?idx?=?1?&?(x?>>?i);
????????if?(!node[p][idx])?node[p][idx]?=?++cnt;
????????bucket[p][idx]++;
????????p?=?node[p][idx];
????}
}
void?del(int?x)
{
????int?p?=?0;
????for?(int?i?=?M;?i?>=?0;?--i)?{
????????int?idx?=?1?&?(x?>>?i);
????????int?next?=?node[p][idx];
????????if?(bucket[p][idx]?==?1)?node[p][idx]?=?0;
????????bucket[p][idx]--;
????????p?=?next;
????}
}
int?query(int?x)
{
????int?p?=?0;
????int?ans?=?0;
????for?(int?i?=?M;?i?>=?0;?--i)?{
????????int?idx?=?1?&?(x?>>?i);
????????if?(node[p][idx?^?1])?{
????????????ans?*=?2,?ans?+=?1;
????????????p?=?node[p][idx?^?1];
????????}
????????else?{
????????????ans?*=?2,?ans?+=?0;
????????????p?=?node[p][idx];
????????}
????}
????return?ans;
}
class?Solution?{
public:
????unordered_map<?int,?vector<?pii?>?>?mp;
????vector<?int?>?son[N];
????void?dfs(int?u,?vector<?int?>?&ans)
????{
????????insert(u);
????????for?(auto?&i?:?mp[u])?ans[i.se]?=?query(i.fi);
????????for?(auto?&i?:?son[u])?dfs(i,?ans);
????????del(u);
????}
????vector<?int?>?maxGeneticDifference(vector<?int?>?&p,?vector<?vector<?int?>?>?&q)
????{
????????int?root?=?0;
????????for?(int?i?=?0;?i?<?p.size();?++i)?{
????????????if?(p[i]?!=?-1)
????????????????son[p[i]].push_back(i);
????????????else
????????????????root?=?i;
????????}
????????int?n?=?q.size();
????????for?(int?i?=?0;?i?<?n;?++i)?{
????????????q[i].pb(i);
????????????mp[q[i][0]].pb({?q[i][1],?q[i][2]?});
????????}
????????vector<?int?>?ans(n);
????????dfs(root,?ans);
????????return?ans;
????}
};