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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把所有数写成二进制,然后把所有的数插入到一颗二叉树上成为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把所有数写成二进制,然后把所有的数插入到一颗二叉树上成为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.的办法向上回朔。 |
|