題目

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

題解

自己沒(méi)有思路，看了答案之后自己寫(xiě)的。

參考：Python3 巧妙利用前綴樹(shù)剪枝，復(fù)雜度 O(N)

class Trie {Trie[] children;public Trie() {children = new Trie[2];} }class Solution {public int findMaximumXOR(int[] nums) {Trie root = new Trie();int max = Integer.MIN_VALUE;for (int n : nums) {int curMax = 0;Trie buildNode = root; // node for build TrieTrie xorNode = root; // node for calculate XORfor (int j = 31; j >= 0; j--) {int b = 1 & (n >>> j);// 構(gòu)造Trieif (buildNode.children[b] == null)buildNode.children[b] = new Trie();buildNode = buildNode.children[b];// 選擇XOR的操作數(shù)curMax = curMax << 1;if (xorNode.children[1 - b] != null) { // 有相異的位curMax += 1;xorNode = xorNode.children[1 - b];} else { // else不會(huì)是null，因?yàn)槿魏我粋€(gè)分支的高度均為32curMax += 0;xorNode = xorNode.children[b];}}max = Math.max(curMax, max);}return max;} }

超強(qiáng)干貨來(lái)襲 云風(fēng)專(zhuān)訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的leetcode 421. Maximum XOR of Two Numbers in an Array | 421. 数组中两个数的最大异或值（位运算，Trie前缀树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。