defget(self, key): """ :type key: int :rtype: int """ if key in self.dic: n = self.dic[key] self._remove(n) self._add(n) return n.val return-1
defput(self, key, value): """ :type key: int :type value: int :rtype: void """ if key in self.dic: self._remove(self.dic[key]) n = Node(key, value) self._add(n) # imp value - node self.dic[key] = n if len(self.dic) > self.capacity: n = self.head.next self._remove(n) del(self.dic[n.key]) def_add(self, node): p = self.tail.prev p.next = node self.tail.prev = node node.prev = p node.next = self.tail def_remove(self, node): p = node.prev n = node.next p.next = n n.prev = p
# Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value)
deftop(self): """ :rtype: int """ return self.stack[-1][0]
defgetMin(self): """ :rtype: int """ return self.stack[-1][1]
# Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()
def__init__(self): """ Initialize your data structure here. """ self.queue = []
defpush(self, x): """ Push element x onto stack. :type x: int :rtype: void """ self.queue.append(x) size = len(self.queue) while size > 1: self.queue.append(self.queue.pop(0)) size -= 1
defpop(self): """ Removes the element on top of the stack and returns that element. :rtype: int """ return self.queue.pop(0)
deftop(self): """ Get the top element. :rtype: int """ return self.queue[0]
defempty(self): """ Returns whether the stack is empty. :rtype: bool """ return len(self.queue) == 0
# Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty()
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None
classCodec:
defserialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ ifnot root: return"" queue = [root] res = [] while queue: node = queue.pop(0) if node: queue.append(node.left) queue.append(node.right) res.append(str(node.val) if node else"#") # strip left ',' return",".join(res).strip(',')
defdeserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ ifnot data: returnNone nodes = [] for i in data.split(","): if i != '#': nodes.append(TreeNode(i)) else: nodes.append(None) queue = [nodes[0]] index = 1 while queue: node = queue.pop(0) if index < len(nodes) and nodes[index]: node.left = nodes[index] queue.append(nodes[index]) if index + 1 < len(nodes) and nodes[index+1]: node.right = nodes[index+1] queue.append(nodes[index+1]) index += 2 return nodes[0]
# Your Codec object will be instantiated and called as such: # codec = Codec() # codec.deserialize(codec.serialize(root))
def__init__(self): """ Initialize your data structure here. """ self.array = [] self.dic = dict()
definsert(self, val): """ Inserts a value to the set. Returns true if the set did not already contain the specified element. :type val: int :rtype: bool """ if val in self.dic: returnFalse self.dic[val] = len(self.array) self.array.append(val) returnTrue
defremove(self, val): """ Removes a value from the set. Returns true if the set contained the specified element. :type val: int :rtype: bool """ if val notin self.dic: returnFalse # val.index in self.array index = self.dic[val] # check not the last if index < len(self.array) - 1: last = self.array[-1] self.dic[last] = index self.array[index] = last self.array.pop() del(self.dic[val]) returnTrue
defgetRandom(self): """ Get a random element from the set. :rtype: int """ return self.array[random.randint(0, len(self.array)-1)]
# Your RandomizedSet object will be instantiated and called as such: # obj = RandomizedSet() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()
def__init__(self): """ Initialize your data structure here. """ self.array = [] self.dic = dict()
definsert(self, val): """ Inserts a value to the collection. Returns true if the collection did not already contain the specified element. :type val: int :rtype: bool """ if val notin self.dic: self.dic[val] = set() self.dic[val].add(len(self.array)) self.array.append(val) returnTrue else: self.dic[val].add(len(self.array)) self.array.append(val) returnFalse
defremove(self, val): """ Removes a value from the set. Returns true if the set contained the specified element. :type val: int :rtype: bool """ if val notin self.dic: returnFalse # val.index in self.array index = self.dic[val].pop() if index < len(self.array) - 1: last = self.array[-1] self.array[index] = last # last item delete # remove old insert new self.dic[last].remove(len(self.array)-1) self.dic[last].add(index) self.array.pop() ifnot self.dic[val]: del(self.dic[val]) returnTrue
defgetRandom(self): """ Get a random element from the set. :rtype: int """ return self.array[random.randint(0, len(self.array)-1)]
# Your RandomizedCollection object will be instantiated and called as such: # obj = RandomizedCollection() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()
Trie类型
简单构建
在程序中需要简单构建一个Trie
1 2 3 4 5 6 7 8
trie = {} for w in words: t = trie for c in w: if c notin t: t[c] = {} t = t[c] t['#'] = '#'
from collections import defaultdict classTrieNode(object): def__init__(self): """ Initialize your data structure here. """ self.nodes = defaultdict(TrieNode) # Easy to insert new node. self.isword = False# True for the end of the trie. classTrie(object):
def__init__(self): """ Initialize your data structure here. """ self.root = TrieNode()
definsert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ curr = self.root for char in word: curr = curr.nodes[char] curr.isword = True
defsearch(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.root for char in word: if char notin curr.nodes: returnFalse else: curr = curr.nodes[char] return curr.isword
defstartsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ curr = self.root for char in prefix: if char notin curr.nodes: returnFalse else: curr = curr.nodes[char] returnTrue # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix)
def__init__(self): """ Initialize your data structure here. """ self.root = TrieNode()
defaddWord(self, word): """ Adds a word into the data structure. :type word: str :rtype: void """ curr = self.root for char in word: curr = curr.node[char] curr.isWord = True
defsearch(self, word): """ Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. :type word: str :rtype: bool """ return self.find(self.root, word) deffind(self, trie, word): if word == '': return trie.isWord if word[0] == '.': for i in trie.node: if self.find(trie.node[i], word[1:]): returnTrue else: child = trie.node.get(word[0]) if child: return self.find(child, word[1:]) returnFalse
def__init__(self, sentences, times): """ :type sentences: List[str] :type times: List[int] """ self.root = TrieNode() self.keyword = "" for i, sentence in enumerate(sentences): self.addRecord(sentence, times[i]) defaddRecord(self, word, rank): p = self.root for char in word: if char notin p.children: p.children[char] = TrieNode() p = p.children[char] p.isEnd = True p.data = word # compare p.rank -= rank
defsearch(self, word): p = self.root for char in word: if char notin p.children: return [] p = p.children[char] return self.dfs(p) defdfs(self, root): res = [] if root: # find the end if root.isEnd: res.append((root.rank, root.data)) for child in root.children: res.extend(self.dfs(root.children[child])) return res definput(self, c): """ :type c: str :rtype: List[str] """ res = [] if c != "#": self.keyword += c res = self.search(self.keyword) else: self.addWord(self.keyword,1) self.keyword = "" return [item[1] for item in sorted(res)[:3]]
# Your AutocompleteSystem object will be instantiated and called as such: # obj = AutocompleteSystem(sentences, times) # param_1 = obj.input(c)
# Below is the interface for Iterator, which is already defined for you. # # class Iterator(object): # def __init__(self, nums): # """ # Initializes an iterator object to the beginning of a list. # :type nums: List[int] # """ # # def hasNext(self): # """ # Returns true if the iteration has more elements. # :rtype: bool # """ # # def next(self): # """ # Returns the next element in the iteration. # :rtype: int # """
defnext(self): ret = self.temp self.temp = self.iter.next() if self.iter.hasNext() elseNone return ret
defhasNext(self): return self.temp isnotNone
# Your PeekingIterator object will be instantiated and called as such: # iter = PeekingIterator(Iterator(nums)) # while iter.hasNext(): # val = iter.peek() # Get the next element but not advance the iterator. # iter.next() # Should return the same value as [val].
def__init__(self): """ Initialize your data structure here. """ self.dic = dict()
defshouldPrintMessage(self, timestamp, message): """ Returns true if the message should be printed in the given timestamp, otherwise returns false. If this method returns false, the message will not be printed. The timestamp is in seconds granularity. :type timestamp: int :type message: str :rtype: bool """ # condition one if message in self.dic and timestamp - self.dic[message] < 10: returnFalse else: self.dic[message] = timestamp returnTrue
# Your Logger object will be instantiated and called as such: # obj = Logger() # param_1 = obj.shouldPrintMessage(timestamp,message)
def__init__(self): """ Initialize your data structure here. """ self.count = 0 self.queue = []
defhit(self, timestamp): """ Record a hit. @param timestamp - The current timestamp (in seconds granularity). :type timestamp: int :rtype: void """ ifnot self.queue or self.queue[-1][0] != timestamp: self.queue.append([timestamp,1]) else: self.queue[-1][1] += 1 self.count += 1 defgetHits(self, timestamp): """ Return the number of hits in the past 5 minutes. @param timestamp - The current timestamp (in seconds granularity). :type timestamp: int :rtype: int """ # move forward while self.queue and timestamp - self.queue[0][0] >= 300: self.count -= self.queue.pop(0)[1] return self.count
# Your HitCounter object will be instantiated and called as such: # obj = HitCounter() # obj.hit(timestamp) # param_2 = obj.getHits(timestamp)