01trie 在面試中的妙用
簡(jiǎn)介
就是把整數(shù)的二進(jìn)制表達(dá)式當(dāng)作字符串，之前寫(xiě)過(guò)一篇字典樹(shù)，按照從高位到低位的順序，掛載在字典樹(shù)上，每個(gè)節(jié)點(diǎn)有兩個(gè)孩子，分別是 ，從而形成一棵二叉樹(shù)，常用來(lái)處理異或問(wèn)題
例如將一個(gè)數(shù)組 掛在 上，便得到如下所示的一棵二叉樹(shù)
性質(zhì)
由于 是一棵二叉樹(shù)，且最大深度取決于掛載值的大小，設(shè)掛載最大值為 ，那么一次查詢前綴的過(guò)程便可以在 時(shí)間完成
例題
力扣 421. 數(shù)組中兩個(gè)數(shù)的最大異或值
給定 個(gè)正整數(shù)的數(shù)組 ，計(jì)算 的最大值
數(shù)據(jù)規(guī)定
題解
將數(shù)組中所有正整數(shù)的二進(jìn)制表示，按照從高位到低位的順序，當(dāng)作字符串掛載在字典樹(shù)上，形成 字典樹(shù)，該字典樹(shù)為一棵二叉樹(shù)
對(duì)于正整數(shù) ，為了尋找數(shù)組中的 ，使得 最大，我們只要每次貪心走與當(dāng)前位相反的路即可
具體來(lái)講，如果當(dāng)前位為 ，我們走 子樹(shù)，反之走 子樹(shù)，當(dāng)然，如果不存在對(duì)應(yīng)的子樹(shù)，我們還是得走存在的子樹(shù)
這樣可以保證異或后的高位盡可能為 ，在二進(jìn)制表示中，高位為 ，即使剩下的全 ，結(jié)果也要比高位為 ，剩下的全 結(jié)果大，直觀的感受，，這便證明了貪心的正確性
時(shí)間復(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ù)組中元素的最大異或值
給定 個(gè)正整數(shù)的數(shù)組 ，給定 個(gè)詢問(wèn)，每個(gè)詢問(wèn)包含兩個(gè)正整數(shù)
對(duì)于每一個(gè)詢問(wèn)，在 中所有不大于 的數(shù)中選一個(gè) ，使得 最大，返回這個(gè)最大值
數(shù)據(jù)規(guī)定
題解
離線查詢，對(duì) 從小到大排序，對(duì) 按照 從小到大排序
根據(jù)單調(diào)性，使用雙指針，將 中符合條件的正整數(shù) 掛載到字典樹(shù)上，進(jìn)行查詢即可
時(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. 查詢最大基因差
給定一棵 個(gè)節(jié)點(diǎn)的樹(shù)，每個(gè)節(jié)點(diǎn)的編號(hào) 即為其權(quán)值
給定 個(gè)查詢，每個(gè)查詢包含樹(shù)上一個(gè)點(diǎn)的編號(hào) 和目標(biāo)值
對(duì)于每一個(gè)查詢，你需要選一個(gè)從根到 的節(jié)點(diǎn) ，要求使得 值最大，返回這個(gè)最大值
數(shù)據(jù)規(guī)定
題解
離線查詢，維護(hù)每個(gè)節(jié)點(diǎn)的所有查詢
我們需要維護(hù)一個(gè)從根到當(dāng)前節(jié)點(diǎn)的路徑，因此考慮 dfs
具體來(lái)講，深搜到當(dāng)前點(diǎn) 時(shí)，將 掛載在 01 trie 上，同時(shí)進(jìn)行一次查詢，計(jì)算出最大的異或值，繼續(xù)向下深搜，等到回溯的時(shí)候，將當(dāng)前節(jié)點(diǎn)的權(quán)值從字典樹(shù)上刪除
計(jì)算最大異或值時(shí)，每次貪心選擇與當(dāng)前位相反的節(jié)點(diǎn)即可
時(shí)間復(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;
????}
};