Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # coding=utf-8
- """
- TRIE树py实现
- 运行速度有点慢啊,用时1000ms,打败10%,估计是`to_bit`和`to_num`耗时了,
- 改成bit的移位操作应该可以优化,有待于profile考证
- ~~时间复杂度是O(nlog(m)),m是n的最大位数~~
- 时间复杂度是O(n),bit位32写死在程序里面了
- """
- from collections import defaultdict
- from pprint import pprint
- def default_factory():
- return defaultdict(default_factory)
- def to_bit(k):
- """1024 -> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"""
- return (['0']*32+list(bin(k)[2:]))[-32:]
- def to_num(k):
- """[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] -> 1024"""
- return int(''.join(k),2)
- def not_(l):
- return [{'0':'1','1':'0'}[bit] for bit in l]
- class TRIE:
- def __init__(self):
- self._root = default_factory()
- def __contains__(self, other):
- node = self._root
- for bit in other:
- if bit not in node:
- return False
- node=node[bit]
- return True
- def add(self, num):
- node = self._root
- for bit in num:
- node = node[bit]
- node['value']=num
- def find_most_closed(self, other):
- node = self._root
- res = []
- for bit in other:
- if bit not in node:
- bit = {'0':'1','1':'0'}[bit]
- node=node[bit]
- res.append(bit)
- assert node['value']==res
- return res
- def freeze(self):
- self._root=dict(self._root)
- class Solution(object):
- def findMaximumXOR(self, nums):
- """
- :type nums: List[int]
- :rtype: int
- """
- nums = [to_bit(k) for k in nums]
- trie = TRIE()
- for num in nums:
- trie.add(num)
- res=[]
- for num in nums:
- not_num = not_(num)
- r = trie.find_most_closed(not_num)
- r = to_num(r)
- num = to_num(num)
- res.append(num^r)
- return max(res)
- s=Solution()
- nums = [3, 10, 5, 25, 2, 8]
- z=s.findMaximumXOR(nums)
- assert z==28
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement