• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
47%
SHARE
TWEET

# Untitled

a guest Jun 19th, 2017 61 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.
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:
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top