Add Solution.py for 0421.Maximum XOR of Two Numbers in an Array

Hinsteny · Hinsteny · commit c51b492bb2e6 · 2019-06-20T14:04:03.000+08:00
diff --git a/solution/0421.Maximum XOR of Two Numbers in an Array/Solution.py b/solution/0421.Maximum XOR of Two Numbers in an Array/Solution.py
@@ -0,0 +1,19 @@
+class Solution:
+    def findMaximumXOR(self, nums: List[int]) -> int:
+        max = 0
+        mask = 0
+        for i in range(30, -1, -1):
+            current = 1 << i
+            # &#26399;&#26395;&#30340;&#20108;&#36827;&#21046;&#21069;&#32512;
+            mask = mask ^ current
+            # &#22312;&#24403;&#21069;&#21069;&#32512;&#19979;, &#25968;&#32452;&#20869;&#30340;&#21069;&#32512;&#20301;&#25968;&#25152;&#26377;&#24773;&#20917;&#38598;&#21512;
+            _set = set()
+            for num in nums:
+                _set.add(num & mask)
+            # &#26399;&#26395;&#26368;&#32456;&#24322;&#25110;&#20540;&#30340;&#20174;&#21491;&#25968;&#31532;i&#20301;&#20026;1, &#20877;&#26681;&#25454;&#24322;&#25110;&#36816;&#31639;&#30340;&#29305;&#24615;&#25512;&#31639;&#20551;&#35774;&#26159;&#21542;&#25104;&#31435;
+            flag = max | current
+            for prefix in _set:
+                if prefix ^ flag in _set:
+                    max = flag
+                    break
+        return max
diff --git a/solution/README.md b/solution/README.md
@@ -768,7 +768,8 @@
 &#9474;&nbsp;&nbsp; &#9492;&#9472;&#9472; Solution.java
 &#9500;&#9472;&#9472; 0421.Maximum XOR of Two Numbers in an Array
 &#9474;&nbsp;&nbsp; &#9500;&#9472;&#9472; README.md
-&#9474;&nbsp;&nbsp; &#9492;&#9472;&#9472; Solution.java
+&#9474;&nbsp;&nbsp; &#9500;&#9472;&#9472; Solution.java
+&#9474;&nbsp;&nbsp; &#9492;&#9472;&#9472; Solution.py
 &#9500;&#9472;&#9472; 0423.Reconstruct Original Digits from English
 &#9474;&nbsp;&nbsp; &#9492;&#9472;&#9472; Solution.cpp
 &#9500;&#9472;&#9472; 0427.Construct Quad Tree

-Original file line number
+Diff line change
 │   └── Solution.java
 ├── 0421.Maximum XOR of Two Numbers in an Array
 │   ├── README.md
 -│   └── Solution.java
 +│   ├── Solution.java
 +│   └── Solution.py
 ├── 0423.Reconstruct Original Digits from English
 │   └── Solution.cpp
 ├── 0427.Construct Quad Tree