[Leetcode421](python): 数组中两个数之间最大的异或值

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。你能在O(n)的时间解决这个问题吗？

示例:

根据 Trie Tree(字典树/前缀树/单词查找树) 对Trie基本结构的描述，编写构建结点，以及构建trie树，以及trie树的基本 *** 作方法。

本题的解题思路：Trie树 + 位运算

对于25 (0000 0000 0000 0000 0000 0000 0001 1001) 而言，使得异或结果最大的数x为0000 0000 0000 0000 0000 0000 000

从根节点开始搜索，node = root，直至到第5位，当前node为第6位右分支。

25第5位为1，则x的第5位为0，结果为最大，选择右分支，node = nodezero；

25第4位为1，则x的第4位为0，结果为最大，选择右分支，node = nodezero；

25第3位为0，则x的第3位为1，结果为最大，选择左分支，node = nodeone；

25第2位为0，则x的第2位为1，结果为最大，当前nodeone为空，所以选择nodezero, node = nodezero；

25第1位为1，则x的第1位为0，结果为最大，当前nodezero为空，所以选择nodeone, node = nodeone；最终找到x为5(00101)。

对于数组中每一个数进行上述 *** 作，更新最大异或值。

建立Trie树的时间复杂度是O(32n)，这里的32即Trie树的键值最大长度；Trie树的高度为32，因此查找每个数的最大异或值得时间复杂度是O(32n)，合起来是O(64n)也即时间复杂度为O(n)

>

给定一个数组，求子数组的最大异或和。

一个数组的异或和为，数组中所有的数异或起来的结果

三层循环,时间复杂度为O(n^3)

start--i的异或结果为0--i的异或结果^0---start的异或结果

两层循环,时间复杂度为O(n^2),空间换时间

前缀树也叫字典树,是处理字符串的常见的数据结构

(1)根节点没有字符路径,除根节点外,每一个结点都被一个字符路径找到

(2)从根节点到某一节点,除路径上经过的字符连接起来,为扫过的对应字符串

(3)每个节点下上的所有的字符路径上的字符都不同

int path=((num>>move)&1);将int的32位的每一位都分离出来

传入一个值,遍历每一位,int path=(num>>move)&1;得到当前的位数

如果当前的位数为31,即当前为符号位,则选择本身( 符号位如果是1,选择1异或变为正,0也是这样 ),其他位置尽量为1,则path^1;

best=curnexts[best]!=nullbest:(best^1);

如果期待的位置不为空,则走,如果为空,只能走异或的情况

res |=(path^best)<<move;将得到的值移动到对应的位数

概述

i = 14，异或算法转换二进制，同则取0异则取1；

解析

异或是一种基于二进制的位运算，用符号XOR或者^表示，其运算法则是对运算符两侧数的每一个进制位同值则取0，异值则取1

简单理解就是不进位加法，如1+1=0，0+0=0，1+0=1

For example:

3^5 = 6

转成二进制后就是 0011 ^ 0101 二号位和三号位都是异值取1 末尾两个1同值取零，所以3^5 = 0110 = 6

而 i = 50 ，j = 60；

所以：

i 的二进制 = 00110010

j 的二进制 = 00111100

同位相同取0，不同取1所以得出来的值为00001110

i = i ^ j；所以i = 00001110 = 14

拓展内容

异或运算符

性质

1、交换律 

2、结合律（即(a^b)^c == a^(b^c)） 

3、对于任何数x，都有x^x=0，x^0=x 

4、自反性 A XOR B XOR B = A xor 0 = A

异或运算最常见于多项式除法，不过它最重要的性质还是自反性：A XOR B XOR B = A，即对给定的数A，用同样的运算因子（B）作两次异或运算后仍得到A本身。这是一个神奇的性质，利用这个性质，可以获得许多有趣的应用。 例如，所有的程序教科书都会向初学者指出，要交换两个变量的值，必须要引入一个中间变量。但如果使用异或，就可以节约一个变量的存储空间： 设有A,B两个变量，存储的值分别为a，b，则以下三行表达式将互换他们的值 表达式 （值） ： 

A=A XOR B (a XOR b) 

B=B XOR A (b XOR a XOR b = a) 

A=A XOR B (a XOR b XOR a = b)

#code:

google面试题的变形：一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数？

异或 *** 作(相同为0，不同为1)，if里面是交换两个数

a[1]=36=100100

a[2]=20=10100

a = a ^ (a + 1); 100100^ 10100=110000

( a+1 ) = a ^ (a + 1); 110000^10100=100100=36

a = a ^ (a + 1); 110000^100100=010100=20

以上就是关于[Leetcode421](python): 数组中两个数之间最大的异或值全部的内容，包括:[Leetcode421](python): 数组中两个数之间最大的异或值、字符数组 异或、子数组的最大异或和等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！