t********e
发帖数: 25 | 1 Given n unsigned integer, output 2 integers which has the maximum result
after XOR. | g*******y
发帖数: 1930 | 2 把所有数写成二进制，然后把所有的数插入到一颗二叉树上成为leaf；定义左分支=0,
右分支=1，从root到每个leaf的路径的二进制编码等于leaf的数。
用两个指针p0, p1来“遍历”这个树，如果指针p0往左走，p1就尽可能往右走,vice
versa，思想是尽可能在高位(靠近root)选择两个相异的bit。
如果假设所有的数都是d位的话，复杂度就是O(nd),换句话说O(nlogn) | t********e
发帖数: 25 | | h*********e
发帖数: 56 | 4 很好的模型。但是贪婪算法好象不能保证最优解吧？总选不一样的方向是对的，但到底
是选 左右 还是 右左，还是有区别的。请考虑以下例子：
000，010，101，110
,
【在 g*******y 的大作中提到】
: 把所有数写成二进制，然后把所有的数插入到一颗二叉树上成为leaf；定义左分支=0,
: 右分支=1，从root到每个leaf的路径的二进制编码等于leaf的数。
: 用两个指针p0, p1来“遍历”这个树，如果指针p0往左走，p1就尽可能往右走,vice
: versa，思想是尽可能在高位(靠近root)选择两个相异的bit。
: 如果假设所有的数都是d位的话，复杂度就是O(nd),换句话说O(nlogn)
| c*******s
发帖数: 6 | 5 nice algorithm
but how about space complexity
you need approximately 2^32 space
so it is good for very large n, but not on small n
correct me if i am wrong, thx
,
【在 g*******y 的大作中提到】
: 把所有数写成二进制，然后把所有的数插入到一颗二叉树上成为leaf；定义左分支=0,
: 右分支=1，从root到每个leaf的路径的二进制编码等于leaf的数。
: 用两个指针p0, p1来“遍历”这个树，如果指针p0往左走，p1就尽可能往右走,vice
: versa，思想是尽可能在高位(靠近root)选择两个相异的bit。
: 如果假设所有的数都是d位的话，复杂度就是O(nd),换句话说O(nlogn)
| g*******y
发帖数: 1930 | 6 binary tree, n leaves, d height, at most O(n*d). Furthermore, we can argue
the space complexity will be linear, because the input size of problem is n*
d bits if we assume every input number has d bits.
【在 c*******s 的大作中提到】
: nice algorithm
: but how about space complexity
: you need approximately 2^32 space
: so it is good for very large n, but not on small n
: correct me if i am wrong, thx
:
: ,
| a****s
发帖数: 559 | 7 1.先把这n个unsigned integers，每个都取位反，得到n个新的unsigned integers.
2.用原来的n个旧数生成小尾羊说的二叉树。
3.把新的n个数也放入2中二叉树。如果加入某个新数时其位置已经被某旧数占据，则该
新数取反前的旧数和占据该位置的旧数之XOR为0xFFFFFFFF，最大。
4.如果没有任何新数和旧数走到同一位置，查看旧数和新数的上一层的父节点。如果出
现某新数和某旧数有同一父节点，则该新数取反前的旧数和同父的旧数之XOR为
0xFFFFFFFE.
5.如果还没有，再往上找同父节点，以此类推。
真正在编程时，可以在插入新数时就一直保持一个有同父节点的最深的新旧数对（或多
个，有可能多解）。这样新数插入完，就有了结果，不需再用4.5.的办法向上回朔。 |
|
