動機

真的很有趣，利用bit是list，與xor的特性，所以我可以從最高位一位一位建答案

Problem

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

 

Example 1:

Input: nums = [3,10,5,25,2,8]Output: 28Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]Output: 0

Example 3:

Input: nums = [2,4]Output: 6

Example 4:

Input: nums = [8,10,2]Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]Output: 127

 

Constraints:

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 231 - 1

Sol

一次一次建ret，所以我們要看的是這個位元能不能設成1

這樣就是找ret^1 == p^q，之後就能推出ret^1^p == q

ret^1 == p^q (q,p are prefixs)
ret^1^p == p^q^p
ret^1^p == q

這樣就是從最高位開始看能不加1

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ret = 0
        for i in reversed(range(32)):
            ret <<= 1 # allocate a 0
            pres = {n >> i for n in nums} # prefixs from 31~i # set!!!!!
            if any([ret^1^p in pres for p in pres]):
                ret = ret^1
        return ret