Design
1 Read N Characters Given Read4
# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):
class Solution(object):
def read(self, buf, n):
"""
:type buf: Destination buffer (List[str])
:type n: Maximum number of characters to read (int)
:rtype: The number of characters read (int)
"""
cnt = 0
while n > 0:
buf4 = [""]*4
l = read4(buf4)
if not l:
return cnt
for i in range(min(n, l)):
buf[cnt] = buf4[i]
cnt += 1
n -= 1
return cnt
2 Read N Characters Given Read4 II - Call multiple times
# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):
class Solution(object):
def __init__(self):
self.q = []
def read(self, buf, n):
"""
:type buf: Destination buffer (List[str])
:type n: Maximum number of characters to read (int)
:rtype: The number of characters read (int)
"""
cnt = 0
while n > 0:
buf4 = [""]*4
l = read4(buf4)
self.q.extend(buf4)
if not len(self.q):
return cnt
for i in range(min(len(self.q), n)):
buf[cnt] = self.q.pop(0)
cnt += 1
n -= 1
return cnt
3 Serialize and Deserialize Binary Tree
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
return self.seriHelper(root, '')
def seriHelper(self, root, res):
if not root:
return '#'
l = self.seriHelper(root.left, res)
r = self.seriHelper(root.right, res)
return str(root.val) + ',' + l + ',' + r
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
data = data.split(',')
return self.deseriHelper(data)
def deseriHelper(self, data):
if not data:
return None
if data and data[0] == '#':
data.pop(0)
return None
tmp = int(data.pop(0))
node = TreeNode(tmp)
node.left = self.deseriHelper(data)
node.right = self.deseriHelper(data)
return node
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
4 Flatten Nested List Iterator
class NestedIterator(object):
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
stack = nestedList[::-1]
res = []
while stack:
tmp = stack.pop()
if tmp.isInteger():
res.append(tmp.getInteger())
else:
nestedInteger = tmp.getList()
while nestedInteger:
stack.append(nestedInteger.pop())
self.res = res
def next(self):
"""
:rtype: int
"""
return self.res.pop(0)
def hasNext(self):
"""
:rtype: bool
"""
return len(self.res) != 0
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())
5 Add and Search Word - Data structure design
class Node(object):
def __init__(self):
self.dic = {}
self.isWord = False
class WordDictionary(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = Node()
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
cur = self.root
for c in word:
if c not in cur.dic:
cur.dic[c] = Node()
cur = cur.dic[c]
cur.isWord = True
return
def search(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.helper(word, self.root)
def helper(self, word, cur):
if not word and cur.isWord:
return True
for i in range(len(word)):
c = word[i]
if c == '.':
for key in cur.dic:
if self.helper(word[i+1:], cur.dic[key]):
return True
return False
else:
if c not in cur.dic:
return False
cur = cur.dic[c]
return cur.isWord
6 Binary Search Tree Iterator
# Definition for a binary tree node
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
if root:
self.stack = [root]
while self.stack[-1].left:
self.stack.append(self.stack[-1].left)
else:
self.stack = []
def hasNext(self):
"""
:rtype: bool
"""
return len(self.stack) > 0
def next(self):
"""
:rtype: int
"""
tmp = self.stack.pop()
cur = tmp.right
while cur:
self.stack.append(cur)
cur = cur.left
return tmp.val
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())
7 LRU Cache
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.dic = {}
self.array = []
self.capacity = capacity
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in self.dic:
self.array.remove(key)
self.array.insert(0, key)
return self.dic[key]
else:
return -1
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if key in self.dic:
self.array.remove(key)
self.array.insert(0, key)
else:
if len(self.array) == self.capacity:
del self.dic[self.array.pop()]
self.array.insert(0, key)
else:
self.array.insert(0, key)
self.dic[key] = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
8 Sparse Matrix Multiplication
class Solution(object):
def multiply(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
if not A or not A[0] or not B or not B[0]:
return [[]]
if len(A[0]) != len(B):
return [[]]
n, m = len(A), len(B[0])
res = [[0]*m for _ in range(n)]
dic = collections.defaultdict(list)
for i in range(len(B)):
for j in range(len(B[0])):
if B[i][j]:
dic[j].append((i, B[i][j]))
for i, row in enumerate(A):
for j in range(len(B[0])):
res[i][j] = sum([row[k]*b for k,b in dic[j]])
return res