SHARE
TWEET

Untitled

a guest Jun 19th, 2017 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # coding=utf-8
  2. """
  3. TRIE树py实现
  4.  
  5. 运行速度有点慢啊,用时1000ms,打败10%,估计是`to_bit`和`to_num`耗时了,
  6. 改成bit的移位操作应该可以优化,有待于profile考证
  7.  
  8. ~~时间复杂度是O(nlog(m)),m是n的最大位数~~
  9.  
  10. 时间复杂度是O(n),bit位32写死在程序里面了
  11. """
  12.  
  13. from collections import defaultdict
  14. from pprint import pprint
  15.  
  16. def default_factory():
  17.     return defaultdict(default_factory)
  18.  
  19. def to_bit(k):
  20.     """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]"""
  21.     return (['0']*32+list(bin(k)[2:]))[-32:]
  22. def to_num(k):
  23.     """[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"""
  24.     return int(''.join(k),2)
  25. def not_(l):
  26.     return [{'0':'1','1':'0'}[bit] for bit in l]
  27.  
  28.  
  29. class TRIE:
  30.     def __init__(self):
  31.         self._root = default_factory()
  32.  
  33.     def __contains__(self, other):
  34.         node = self._root
  35.         for bit in other:
  36.             if bit not in node:
  37.                 return False
  38.             node=node[bit]
  39.         return True
  40.        
  41.        
  42.     def add(self, num):
  43.         node = self._root
  44.         for bit in num:
  45.             node = node[bit]
  46.         node['value']=num
  47.            
  48.     def find_most_closed(self, other):
  49.         node = self._root
  50.         res = []
  51.         for bit in other:
  52.             if bit not in node:
  53.                 bit = {'0':'1','1':'0'}[bit]
  54.             node=node[bit]
  55.             res.append(bit)
  56.         assert node['value']==res
  57.         return res
  58.    
  59.     def freeze(self):
  60.         self._root=dict(self._root)
  61.  
  62. class Solution(object):
  63.     def findMaximumXOR(self, nums):
  64.         """
  65.         :type nums: List[int]
  66.         :rtype: int
  67.         """
  68.  
  69.         nums = [to_bit(k) for k in nums]
  70.        
  71.         trie = TRIE()
  72.        
  73.         for num in nums:
  74.             trie.add(num)
  75.            
  76.         res=[]
  77.         for num in nums:
  78.             not_num = not_(num)
  79.             r = trie.find_most_closed(not_num)
  80.             r = to_num(r)
  81.             num = to_num(num)
  82.             res.append(num^r)
  83.         return max(res)
  84.  
  85. s=Solution()
  86. nums = [3, 10, 5, 25, 2, 8]
  87. z=s.findMaximumXOR(nums)
  88. assert z==28
RAW Paste Data
Top