MaximumXORofTwoNumbersInAnArray [source code]

public class MaximumXORofTwoNumbersInAnArray {
static
/******************************************************************************/
class Solution {
    public int findMaximumXOR(int[] nums) {
        int n = nums.length;
        char[][] binArs = new char[n][];
        int maxLen = 0;
        List<Integer> maxLenIndices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            binArs[i] = Integer.toBinaryString(nums[i]).toCharArray();
            int len = binArs[i].length;
            if (len > maxLen) {
                maxLen = len;
                maxLenIndices.clear();
                maxLenIndices.add(i);
            } else if (len == maxLen) {
                maxLenIndices.add(i);
            }
        }
        TreeNode root = new TreeNode(1);
        for (char[] bin : binArs) {
            insert(root, bin, maxLen);
        }
        int max = 0;
        for (int idx : maxLenIndices) {
            max = Math.max(max, lookup(root, binArs[idx], 0, 0));
        }
        return max;
    }

    public void insert(TreeNode root, char[] chs, int depth) {
        if (depth == 0) {
            root.val = 1;
            return;
        }        
        if (depth > chs.length) {
            if (root.left == null)
                root.left = new TreeNode(depth);
            insert(root.left, chs, depth - 1);
            return;
        }
        int index = chs.length - depth; //calibrate with example
        if (chs[index] == '1') {
            if (root.right == null)
                root.right = new TreeNode(depth);
            insert(root.right, chs, depth - 1);
        } else {
            if (root.left == null)
                root.left = new TreeNode(depth);
            insert(root.left, chs, depth - 1);
        }
    }

    public int lookup(TreeNode root, char[] chs, int start, int accum) {
        if (start >= chs.length)
            return accum;
        if (chs[start] == '1') {
            if (root.left != null)
                return lookup(root.left, chs, start + 1, (accum << 1) + 1);
            else
                return lookup(root.right, chs, start + 1, accum << 1);
        } else {
            if (root.right != null)
                return lookup(root.right, chs, start + 1, (accum << 1) + 1);
            else
                return lookup(root.left, chs, start + 1, accum << 1);
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MaximumXORofTwoNumbersInAnArray.Solution tester = new MaximumXORofTwoNumbersInAnArray.Solution();
        int[][] inputs = {
            {3, 10, 5, 25, 2, 8}, {28},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            int ans = inputs[1 + 2 * i][0];
            System.out.println(Printer.separator());
            int output = tester.findMaximumXOR(nums);
            System.out.println(
                Printer.wrapColor(Printer.array(nums), "magenta") +
                " -> " + output +
                Printer.wrapColor(", expected: " + ans, output == ans ? "green" : "red")
                );
        }
    }

    public static int dfs(int[] a, int start, int b) {
        if (start >= a.length)
            return b;
        return dfs(a, start + 1, b + a[start]);
    }
}

首先, 0 ≤ ai < 2^31, 这种写法的条件, 当时脑子里的第一反应就是告诉了你位数, 这个要很熟悉了, 之前刚刚碰到过一次;

笨办法肯定是N^2的做法比较; 但是人家要求N的做法;

这个问题有一个特点, 就是我们如果对N^2跟pair挨个都xor一次, 那么最后其实是有一定的重复操作的? 比如知道了a xor b, b xor c, 其实a xor c你也知道了? 感觉这个问题的考点也就在这里了;

另外, 加速到O(N)这个话题以前也总结过, 很多技巧, 这个题你认为是用纯粹的bit来做, 还是要掺和一点历史信息流进去? 毕竟上面这个分析的意思感觉就是有点历史信息流存取技巧的意思;

这个题目刚开始确实是没有什么思路的, 不过大概搞个白板, 把题目画一画还是理解的;

首先, 我们以前碰到过的bit的题目, 一个常见的思路, 就是上来直接所有的数字全都bit化, 摆在一起, 这样容易看规律, 比如这样的:

      1 1 : 3  
  1 0 1 0 : 10  
    1 0 1 : 5   ⬅︎  
1 1 0 0 1 : 25  ⬅︎  
      1 0 : 2  
  1 0 0 0 : 8

注意对位, 这样容易看出来区别;

当然, 其他bit题目我们还常见的另外一个技巧, 有一个类似hashing的操作: 对应每一个bit位置, collect或者collectively analyze当前位置上的所有的bit; 在这一题里面, 我们没有必要collect, 但是按位分析这个后面还是要用到的;

again, 对于任何题目, 一个很好的思路就是想想这个给我们的例子(有时候不给你例子, 你自己也可以举一个浅显的例子, 有input, 有output), 我们能不能总结背后的computation; 比如这里这个例子, 告诉我们最后选的是5和25. 你光看5 xor 25可能看不出来规律; 反过来, 用陪衬的目光来看: 为什么不是5和2呢? 5和25之间到底有什么特殊之处?

这个理解了之后, 这个题目大概的意思也就理解了; 另外这个题目也是一个最值搜索的题目, 而我们这里采用的思路是deterministic, specifically, greedy(算greedy吗? 反正大概是这个意思);

我们每一个bit位其实都知道要找的目标应该是什么, 所以算法本身还是不难写的. 为了加速, 一个好的办法就是用trie来组织一下这些binary, 这个也是为什么tag里面有trie的原因;

另外要思考一下, 这个trie的方向是从左到右还是从右到左? 因为对位的问题, 从左到右没有从右到左方便, 但是好像这题最好还是用从左到右的方式来做? 至于padding, 要想办法解决一下就行了;

另外, 这一题的domain是binary的, 你就要想这个trie要怎么实现? 里面要放一个array吗? 还是直接两个变量? 我认为好像是变量好一点; 因为array是有overhead的; 另外, 既然是一个两个变量的trie, 直接用BST就算了; 但是有一个问题没有去思考: 虽然我们用的是BST, 但是实际上, 我们这里每一个index上的这个数字, 跟你一个BST里面的数字的作用是不一样的! 这个也是trie和tree一个很subtle但是也很重要的区别. 我们在思考tree类的问题的操作, 尤其是思考参数表和变量的更新的方式的时候, 一个常见的思考方式就是站在某一个node上, 然后思考我给这个node pass进来的参数应该是什么; 这个想法是没有问题的, 但是你有没有想过你这里array上面每一个entry应该怎么用? 要注意, 这里我们这个array(string)的每一个entry不是val! 而是key! 我们用它是来找到child的index的, 而不是用来放到当前node的val里面还是干什么的; 这一点有点像正宗的BST;

在这一题里面, 单纯的思考站在一个node上, 我们要什么参数, 还不够, 我们要深层理解这个参数对应的是什么: 也就是站在这个node上, 我们用来跟这个node比较的key是什么(虽然没有真正的比较, 但是你如果愿意, 完全可以用一个BST的compare的算法来决定下一步child的走向);

想到这里, 我感觉这个题目还是挺难, 也是很好的一个题目; 虽然是bit题, 但是其他的知识点也考察到了, 而且题目对于idea和实现的考察都很重视;

另外这个padding其实不好实现; 这里这个trie比较难搞的地方主要是我们插入的时候要做到一个右对齐, 但是查找的时候要做到一个左对齐; 而传统的trie, 都是插入和查找的时候都是左对齐; 这种trie还是没有锻炼过;

这个算法, 因为要实现这样的trie, 最后写起来就有点麻烦, 尤其是各种参数和变量的边界效应; 一个比较好的做法是, 刚开始写个大概就行了, 不要对+1, -1这些太纠结. 这个block写完之后, 可以改一下(因为面试的时候, 你一边在写, 面试官就一边在看了);

另外尤其是recursion的设计, 很多时候你刚开始是不知道完整的参数表是什么样的, 很多时候也都是一边写一边改的;

所以我拿着一个array, insert的时候从上向下走, 最后我这个array的每一个entry最后就存储在什么位置了呢? 事实上, 在trie当中, 你最后insert之后, 每一个entry(key)对应的就是每一个edge down a path, which corresponds to an array; 当然, edge本身可以直接在其上端点进行判断, 这个是很自然的了;

subtle bug: char and int comparison

我在写这个程序的时候出现了一个typo造成的bug, 但是却花了很多时间才调出来; 这个bug就是比如chs[index], 本来应该跟'1'比较, 但是我写成了和1比较; 这个bug很隐蔽, 因为compiler发现不了: char和int的比较本身并没有违反语法; 以后要对这个隐蔽的bug留意;

bit运算符优先级极低

另外一个调了老半天的bug:

return lookup(root.left, chs, start + 1, (accum << 1) + 1);

注意这里最后accum更新的部分; 一开始我的写法是accum << 1 + 1, 觉得这样没问题啊, 结果哪知道这样优先级有问题, 这么写最后其实等于accum << 2. 位运算和三目的优先级奇低, 这个以前好像说过的;

这两个很难改的bug改掉之后, 直接就AC了, 速度是36ms (95%), 算是最优解了;

另外, 关于边界case的问题, 其实我这个问题到后面, 边界更新的处理, 完全就是先自己大概写一个(+1, -1也不知道对不对的), 然后直接题目给的这个例子给insert进去, 画出来这个trie(因为是BST, 所以中途debug的时候还用BFS打印了一下看看insert之后大概的情况是否正常); 然后就是lookup, 也是大概跑几个;

首先, 我希望你还是掌握这种做法, 毕竟真正面试的时候, 有时候是无法避免地要get ugly的; 不行老子就画trace, 所谓变凉更新这些的东西, 没有这样无法解决的; 另外, 只要你保证每一个node对应的变量之间有正确的更新关系(相对关系), 那么绝对对应关系一般就算平移了几个, 多数情况下也问题不大; 要么就是无伤大雅, 要么就是用trace可以调试出来;

当然, 什么样的才是最理想的做法呢? 当然就是我们直接能够在写recursion的时候, 脑子里能够告诉自己我现在写的这个node, 我预期的这个参数的值是多少, 而且为什么应该是这个(对应于某一个例子, 而且要对应于合理的main call给的初始参数); 这个题目我刚开始写的时候还是有点太畏手畏脚了; 比如这里我其实是用了一个dummy root的, 刚开始我连这个dummy是不是可以用都很不自信; 这个一方面还是说明不够熟练;

另外Google的题目也真的不是盖的, 这个题目的idea其实我十多分钟就想出来了, 结果实现想了这么久; 对自己还是有点失望的, 虽然我最后写的这个算法很长, 但是其实是非常常规的代码和算法, 如果真正熟练, 这个代码完全可以十分钟之内敲完, 这样这个题目半小时也就做完了; 结果考虑边界效应和bug搞了这么久;

另外这个算法是做到了O(N)的: WorstCase, 所有的数字都有32bit, 那么最后我们每一个bit要完成的cost其实也就是一个32步的insert和一个32步的lookup, 这个还是在O(1)级别的;

这个是discussion的最优解, 也是O(N), 虽然比我的速度要稍微慢一点(73ms):

public class Solution {  
    public int findMaximumXOR(int[] nums) {  
        int max = 0, mask = 0;  
        for(int i = 31; i >= 0; i--){  
            mask = mask | (1 << i);  
            Set<Integer> set = new HashSet<>();  
            for(int num : nums){  
                set.add(num & mask);  
            }  
            int tmp = max | (1 << i);  
            for(int prefix : set){  
                if(set.contains(tmp ^ prefix)) {  
                    max = tmp;  
                    break;  
                }  
            }  
        }  
        return max;  
    }  
}

这个代码刚开始完全看不懂; 后来看了一点别人的解释, 还是看不懂, 最后还是自己画trace, 大概看懂了;

首先是一个大体思路的解释:

@newtt said in Java O(n) solution using bit manipulation and HashMap:

This algorithm's idea is:
to iteratively determine what would be each bit of the final result from left to right. And it narrows down the candidate group iteration by iteration. e.g. assume input are a,b,c,d,...z, 26 integers in total. In first iteration, if you found that a, d, e, h, u differs on the MSB(most significant bit), so you are sure your final result's MSB is set. Now in second iteration, you try to see if among a, d, e, h, u there are at least two numbers make the 2nd MSB differs, if yes, then definitely, the 2nd MSB will be set in the final result. And maybe at this point the candidate group shinks from a,d,e,h,u to a, e, h. Implicitly, every iteration, you are narrowing down the candidate group, but you don't need to track how the group is shrinking, you only cares about the final result.

这个其实讲的不是特别好, 不过大概意思你是知道的;

这个是一个人给的例子:

example: Given [14, 11, 7, 2], which in binary are [1110, 1011, 0111, 0010].
Since the MSB is 3, I'll start from i = 3 to make it simplify.

1. i = 3, set = {1000, 0000}, max = 1000
2. i = 2, set = {1100, 1000, 0100, 0000}, max = 1100
3. i = 1, set = {1110, 1010, 0110, 0010}, max = 1100
4. i = 0, set = {1110, 1011, 0111, 0010}, max = 1100

首先, 看人家代码, 这个mask的应用; 一开始我还真没理解这个东西是干什么的, 不过后面看了一下人家的用法, 还是理解了, 可以看到, 这个人对于这个mask的使用其实是已经非常驾轻就熟了;

• mask的更新, 是一个每一次在上一个mask的基础上, 再多mask一位的做法; 多加这一位的具体操作是lor操作;
• mask的功能值是1而不是0;
• apply mask的过程就是直接一个land操作; 所有已经被设置了功能值(1)的bit, 都会被filter通过, 而所有没有被set的, 全部都被filter out; 当然, 根据具体问题, 这个逻辑是可以改变的; 反正知道land和lor中的敏感值是多少就行了: lor当中, 1敏感, 用1来覆盖; land当中, 0敏感, 用0来覆盖;

所以最后set里面得到的就是所有unique的prefix, 截止到当前的i bit为止;

比较难理解是后面max的更新部分:

• tmp的作用, 就是: 假设当前的i对应的bit可以被set(in max), 那么max会变成多少; 更具体的, 也就是有数字在当前bit differ;
  • 其实上面这个描述有点问题, 也就是在当前bit differ这一部分, 不过先不管这个, 先讲这里的代码到底是什么意思;
    • 我们set做出来之后, 其实是装了所有的prefix; 然后我们tmp的作用其实是一个伸脚变量; 这个变量其实不神秘, 其实就是一个判断目标;
    • 这个第二个循环实际上想要判断的目标是什么呢? 其实是exists两个num, 使得它们截止到当前bit为止的prefix整个全都differ; 这个其实也不是非常准确, 严格来说应该是保留前面iteration产生的最大differ情况(max就是这个作用), 同时当前bit能够产生differ;
    • 如果当前位无法产生differ怎么办(without breaking previous max differs)? 其实就没怎么办, tmp这个伸脚变量就被丢弃了, max没有得到更新;
    • 这个判断具体是怎么实现的? 首先, 我们previous的max是怎么来的? 类似于最上面的那个第一个解释, 如果我们上一个it饿啊提哦你, 是abcde在前i - 1 bits上的differ导致了max(未必是全differ, 但是肯定是尽可能多, 并且尽可能高位的differ), 那么我们在这一个i bit上面, 应该考虑什么? 我们应该考虑至少还有两个数字, 他们对应的prefix: prefix1 and prefix2, 首先这两个数字要在abcde当中, 这样max前面的(i-1)bit的differ被保留了, 同时, 我们要争取在当前的bit, 也能有一个differ; 所以我们要的是: prefix1 ^ prefix2 = tmp (which is previous max, with bit-i set).
    • 很奇怪的地方是, 这里实际上判断的并不是这个. 这个是因为作者利用了xor的一个性质: if a xor b = c, then b ^ c = a, a ^ c = b. 这个是一个非常强力的性质; 所以你如果看这里的set.contains没有看懂, 可以举一个例子看看. contains完成的其实是一个search hit操作, 也就是一个相等判断, 这里实际上最后判断的是: perfix1 ^ tmp = prefix2 (the one found in set). 这样的一个操作利用xor的性质完成了一个等价的操作;
  • 你可能有点奇怪, 为什么要break? 因为我们在当前的i bit, 只要保证来自于前面i - 1 bits的abcde这五个当中, 至少有两个留下来就行了; 实际上有几个我们根本不在乎. 所以只要有一个contains hit, 直接就可以结束: we can rest assured that we can set bit-i of max;
• 这个算法其实核心思路还是一个greedy. 只不过具体的思路用的跟我的不一样; 具体来说, 是查询的实现不一样; 他这个代码确实比我的简短太多了; 不过比我的代码也难很多; 我的代码, 我觉得如果我训练充足, 完全有把握十分钟写出来, 他这个代码, 我觉得大部分人估计都没这个把握;
• 发现对准prefix分析是这个算法的核心点; 事实上, trie也是这个性质; 我们一般也往往是见到overlapping prefix很多的时候, 立刻就想到trie的; 只不过这个人对于核心矛盾抓的更准, 直接设计了一个更加简练的算法; 总体来说这个算法属于相当相当聪明的算法; 对问题本身的理解, 以及对bit操作的熟练度, 都体现的非常高;

这个是一个不错的解释:

int findMaximumXOR(vector<int>& nums) {  
    int max = 0, mask = 0;  
    unordered_set<int> t;  
    // search from left to right, find out for each bit is there   
    // two numbers that has different value  
    for (int i = 31; i >= 0; i--){  
        // mask contains the bits considered so far  
        mask |= (1 << i);  
        t.clear();  
        // store prefix of all number with right i bits discarded  
        for (int n: nums){  
            t.insert(mask & n);  
        }  

        // now find out if there are two prefix with different i-th bit  
        // if there is, the new max should be current max with one 1 bit at i-th position, which is candidate  
        // and the two prefix, say A and B, satisfies:  
        // A ^ B = candidate  
        // so we also have A ^ candidate = B or B ^ candidate = A  
        // thus we can use this method to find out if such A and B exists in the set   
        int candidate = max | (1<<i);  
        for (int prefix : t){  
            if (t.find(prefix ^ candidate) != t.end()){  
                max = candidate;  
                break;  
            }  

        }  
    }  
    return max;  
}

这个是关于xor性质的解释:

@robert501128 said in Java O(n) solution using bit manipulation and HashMap:

I saw deeply and found out a very important xor feature I missed, that is: if a^b=c, then a^c=b, b^c=a. That's why the answer using this code:

for(int prefix : set){  
    if(set.contains(tmp ^ prefix)) {  
        max = tmp;  
        break;  
    }  
}

另外, 撇开跟我的代码的联系, 你有没有想过他这个代码到底是怎么完成加速的? 其实他这里用的东西就是我自己思考的时候提到的, reuse history的部分. 不过我当时没有想到具体怎么使用; 这里展示了, xor还正好有一个性质, 可以让我们这样使用历史信息;

比如上面我们分析, 前i - 1 bits我们知道了abcde产生了max, 我们现在希望当前i bit的操作能产生tmp, which is max with an extra bit-i set; 这个东西, naive的做法是什么? 当然是abcde里面取pair, 然后挨个尝试, 是否跟目标tmp相等, 这样的做法就是N^2; 为什么他这里这个利用了xor性质之后的做法就可以做到O(N)? 因为这里就是巧妙使用了set.contains这个操作; JAVA里面这个操作是O(1)的:

A HashSet carries an internal HashMap with entries and uses equals() as well as the equals method of the HashCode to determine equality.

所以这样就把一个提取pair出来之后再比较的generate&test的操作, 变成了一个类似2sum的历史信息流操作; 在2sum里面, 我们对于key的产生, 只要一个类似sum - i的操作就行, 但是这里就复杂一些, 要i ^ tmp这个, 但是寻找的目标是类似的; 一个是寻找a + b = sum, 一个是a ^ b = tmp; 很subtle的一个小技巧; again, 这个算法里面很多很精髓的技巧;

另外, 关于上面解释的时候, inductive的部分(只在符合previous max的subset里面搜索):

@ming328 said in Java O(n) solution using bit manipulation and HashMap:

@icezhou0784 I don't fully understand your question but my understanding is when a number x is not contained in the i-th run, x will never be contained in latter runs since x doesn't have its counterpart to achieve the first i bits of max. In latter runs, x will always make set.contains(tmp ^ prefix) false.

The program tries to set each bit as 1 if there is a pair. After dealing with all bits, the result is maximum and there is at least one pair which can get the max value.

Hope it helps.

另外还是提个醒, 这个bit总结的帖子, 在这里又被提到了: https://discuss.leetcode.com/topic/50315/a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

这个是discussion一个高票的trie解法, 不过实际上慢的没人样: 120(17):

public class Solution {  
    class Trie {  
        Trie[] children;  
        public Trie() {  
            children = new Trie[2];  
        }  
    }  

    public int findMaximumXOR(int[] nums) {  
        if(nums == null || nums.length == 0) {  
            return 0;  
        }  
        // Init Trie.  
        Trie root = new Trie();  
        for(int num: nums) {  
            Trie curNode = root;  
            for(int i = 31; i >= 0; i --) {  
                int curBit = (num >>> i) & 1;  
                if(curNode.children[curBit] == null) {  
                    curNode.children[curBit] = new Trie();  
                }  
                curNode = curNode.children[curBit];  
            }  
        }  
        int max = Integer.MIN_VALUE;  
        for(int num: nums) {  
            Trie curNode = root;  
            int curSum = 0;  
            for(int i = 31; i >= 0; i --) {  
                int curBit = (num >>> i) & 1;  
                if(curNode.children[curBit ^ 1] != null) {  
                    curSum += (1 << i);  
                    curNode = curNode.children[curBit ^ 1];  
                }else {  
                    curNode = curNode.children[curBit];  
                }  
            }  
            max = Math.max(curSum, max);  
        }  
        return max;  
    }  
}

他的主要问题在于:

• 过于依赖频繁的位运算, 不如我直接一开始搞成char方便快速;
• 非要走完所有的32位, 这个在average上会导致速度慢很多;
• trie的node里面的array造成的overhead;

这个是discussion一个实际上做到了跟我一样快的trie解法:

public class Solution {  
    public class Node {  
        Node one;  
        Node zero;  
        Node() {  
            this.one = null;  
            this.zero = null;  
        }  
        Node set(int n) {  
            if (n == 0) {  
                if (this.one == null) this.one = new Node();  
                return this.one;  
            }  
            if (this.zero == null) this.zero = new Node();  
            return this.zero;  
        }  
    }  

    public int findMaximumXOR(int[] nums) {  
        Node root = new Node();  
        int re = 0;  
        for (int num : nums) {  
            int digit = num;  
            int tmp = 0;  
            Node setNode = root;  
            Node findNode = root;  
            int pos = 30;  
            while (pos >= 0) {  
                digit = (num >> pos) & 1;  
                setNode = setNode.set(digit);  
                if (digit == 1) {  
                    if (findNode.one != null) {  
                        tmp = tmp | (1 << pos);  
                        findNode = findNode.one;  
                    } else {  
                        findNode = findNode.zero;  
                    }  
                } else {  
                    if (findNode.zero != null) {  
                        tmp = tmp | (1 << pos);  
                        findNode = findNode.zero;  
                    } else {  
                        findNode = findNode.one;  
                    }  
                }  
                pos--;  
            }  
            re = Math.max(re, tmp);  
        }  
        return re;  
    }  
}

所以感觉实际上最大的差距还是避免了array instance variable; 这个东西看来引入的速度损失是最厉害的; 我另外一个优化是bit长度考虑的小于32, 结果最后居然跟这个速度差不多, 所以其实bit操作比我的string array那些操作更好? 算了, 不想搞了;

他这个算法本身大概意思其实大家都差不多的, 就是一个greedy查询; 他这里一个有意思的地方在于insert和lookup放在一个循环里面解决的; 为什么可以这样? 因为我们最后要找的是xor,是一个pair计算出来的结果; 一个num, 跟他自己是无法产生一个max xor的; 同时, pair这个东西, 还记得我们以前是怎么产生pair的吗?

for (int i = 0; i < n; i++)  
    for (int j = 0; j < i; j++)

我们可以只iterate一个三角形, 而不是整个矩形; 这里利用的就是这样一个思路; 虽然我们实际上进行xor的思路并不是这样一个N^2的pair-based approach, 但是整体的思路是可以类似的; 任何一个num, 只要我们保证它跟它之前的所有的数字全都有过xor(并且结果被记录到max里面), 那么我们最后就可以安心, 整个nums的所有的pair之间都产生过xor了;

这个是一个人的简写:

class Solution {  
    public class TrieNode {  
        TrieNode[] next = new TrieNode[2];  

        public TrieNode goTo(int bit) {  
            if (next[bit] == null)  
                next[bit] = new TrieNode();  
            return next[bit];  
        }  
    }  

    public int findMaximumXOR(int[] nums) {  
        int maxans = 0;  
        TrieNode root = new TrieNode();  

        for (int n : nums) {  
            int maxTmp = 0;  
            TrieNode i = root, j = root;  

            for (int k = 30; k >= 0; k--) {  
                int bit = (n >> k) & 1;  
                i = i.goTo(bit);  
                if (j != null) {  
                    if (j.next[1 ^ bit] != null) {   
                        j = j.next[1 ^ bit]; // i, j better go along opposite path in trie tree.  
                        maxTmp |= 1 << k;  
                    } else  
                        j = j.next[bit]; // i, j go same direction -> no maxTmp increase.   
                }  
            }  

            maxans = Math.max(maxans, maxTmp);  
        }  
        return maxans;  
    }  
}

不过这个简写最后速度很有问题, 因为这个人也用了array instance variable; 他最后的速度还是上面那个人的速度的两倍都不止;

discussion又看到一个解法:

public class Solution {  
    public int findMaximumXOR(int[] nums) {  
        List<Integer> left = new ArrayList<>();  
        List<Integer> right = new ArrayList<>();  
        for(int i=0; i<nums.length; i++) {  
            left.add(nums[i]);  
            right.add(nums[i]);  
        }  
        return helper(left, right, 1<<30);  

    }  
    public int helper(List<Integer> left, List<Integer> right, int bit) {  
        if(left.size()==0||right.size()==0) return 0;  
        if(left.size()==1||right.size()==1) {  
            int max = 0;  
            for(Integer l: left) {  
                for(Integer r: right) {  
                    max = Math.max(max, l^r);  
                }  
            }  
            return max;  
        }  
        List<Integer> oneLeft = new ArrayList<>();  
        List<Integer> zeroLeft = new ArrayList<>();  
        List<Integer> oneRight = new ArrayList<>();  
        List<Integer> zeroRight = new ArrayList<>();  
        while((oneLeft.size()==0||zeroRight.size()==0)&&(oneRight.size()==0||zeroLeft.size()==0)&&bit!=0) {  
            oneLeft = new ArrayList<>();  
            zeroLeft = new ArrayList<>();  
            oneRight = new ArrayList<>();  
            zeroRight = new ArrayList<>();  
            for(Integer i:left) {  
                if((i&bit)==0) zeroLeft.add(i);  
                else oneLeft.add(i);  
            }  
            for(Integer i:right) {  
                if((i&bit)==0) zeroRight.add(i);  
                else oneRight.add(i);  
            }  
            bit >>= 1;  
        }  
        return Math.max(helper(oneLeft, zeroRight, bit), helper(zeroLeft, oneRight, bit));  
    }  
}

奇形怪状, 有点不想看了, 不过这个解法最后的速度跟我的是一样的;

大概看了一下, 好像也是一个用mask(不过是bit mask, 不是prefix mask)来完成extract bit then examine bit这种操作的思路; 有点像之前那个bit解法里面有个人说过的subset不断缩小的思路, 因为他这里每一个参数表里的list都是在上一个iteration对pass进来的list重新filter之后重新add, 所以其实是缩小了: if((i&bit)==0) zeroLeft.add(i);这样的, 就是一个缩小的过程, 而且filter in的条件就是某一个bit上的数值;

不太想看是因为这个人代码里面用了这么多的变量(list类的), 但是每一个变量的名字和变量本身代表的意思都懒得解释, 这种代码看起来就很烦人了. 以后有时间再说了;

Problem Description

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 2^31.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]  

Output: 28  

Explanation: The maximum result is 5 ^ 25 = 28.

Difficulty:Medium
Total Accepted:14.7K
Total Submissions:32K
Contributor: shen5630
Companies
google
Related Topics
bit manipulation trie

Problem Description

这个是我发在discussion关于这个bit解的评价:

Subtleties behind this brilliant algorithm:

• Bit masking
• Greedy search based on prefix
• Variation of 2sum: see below for the analogy

The classic problem of 2sum actually achieved the acceleration from O(N^2) to O(N) in a way very similar to the second loop in this algorithm.

• In 2sum, we want to find two numbers so that a + b = sum, naive way is to generate all pairs, and test each pair. This takes time O(N^2).
  • Instead, we only look at one number at each iteration, and try to find sum - a in the HashMap.
• In this problem (the second part where you try to update max): we want to find two prefixs out of the set so that prefix1 xor prefix2 = tmp, with tmp being the greedily updated max.
  • Instead, we only look at one prefix at each iteration, and try to find tmp ^ prefix1 instead.
    • of course, this part is a little more complicated than the subtraction in 2sum: we have to know the thing about a xor b = c ⇒ a xor c = b, and b xor c = a.

Note that both approaches benefitted from the O(1) lookup provided by hashing data structures.

A HashSet carries an internal HashMap with entries and uses equals() as well as the equals method of the HashCode to determine equality.

2sum is a wonderful problem that keeps haunting (in a good way) the leetcode playground. There is also a very brilliant solution, which is also a clever variation of 2sum, for the problem Path Sum III which impressed me a lot back then.