LC
P1. Word Pattern II
哎呀，第一道题就写得我死去活来的。
class Solution(object):
def wordPatternMatch(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
p2s = {}
return self.dfs(pattern, str, p2s)
def dfs(self, pattern, remain, p2s):
if not pattern and not remain:
return True
if not pattern or not remain:
return False
for i in range(1, len(remain)+1):
s = remain[:i]
p = pattern[0]
if p in p2s and p2s[p] == s:
if self.dfs(pattern[1:], remain[i:], p2s):
return True
elif p not in p2s and s not in p2s.values():
p2s[p] = s
if self.dfs(pattern[1:], remain[i:], p2s):
return True
del p2s[p]
return False
s = Solution()
ans = s.wordPatternMatch('abab', 'xyzabcxzyabc')
print ans
再用一种我觉得更好理解的写法吧。这道题的难点在于不要瞎back tracking。年少的时候不懂事，不知道每一个back tracking 背后都偷偷标好了价格。
class Solution(object):
def wordPatternMatch(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
return self.dfs(pattern, str, {}, {})
def dfs(self, pattern, remain, p2s, s2p):
#base case
if not pattern and not remain:
return True
if not pattern or not remain:
return False
for i in range(1, len(remain)+1):
s = remain[:i]
p = pattern[0]
# does not match then continue
if p in p2s and p2s[p] != s:
continue
if s in s2p and s2p[s] != p:
continue
if p in p2s and p2s[p] == s: # already back tracked
if self.dfs(pattern[1:], remain[i:], p2s, s2p):
return True
else: # fresh back tracking.
p2s[p] = s
s2p[s] = p
if self.dfs(pattern[1:], remain[i:], p2s, s2p):
return True
del p2s[p]
del s2p[s]
return False
s = Solution()
ans = s.wordPatternMatch('abab', 'xyzabcxzyabc')
print ans
P2. Falling Squares
这道题倒是不难，就是把我翔都写出来了。先抄一个答案放这里。
class Solution:
def fallingSquares(self, positions):
"""
:type positions: List[List[int]]
:rtype: List[int]
"""
ans = []
heights = {}
for pos, side in positions:
# finds nearby positions, if any
left, right = pos, pos+side-1
# compare to see if this block overlaps with L/R boundaries of existing blocks
nearby = [key for key in heights.keys() if not (key[1] < pos or key[0] > right)]
# finds height of block based on heights of existing and overlapping blocks
if len(nearby) > 0:
h = max(heights[key] for key in nearby) + side
else:
h = side
# update the heights for left and right boundaries
heights[(pos,right)] = h
# add height to ans
if len(ans) == 0:
ans.append(h)
else:
ans.append(max(h,ans[-1]))
return ans
s = Solution()
ans = s.fallingSquares([[1, 1], [2, 1]])
print ans
P3. Serialize and Deserialize Binary Tree
有段时间没写了。写出来的感觉很粗糙。勉强能用。看了下原来写的，觉得自己很屌啊！
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 data and data[0] == '#':
data.pop(0)
return None
node = TreeNode(int(data.pop(0)))
node.left = self.deseriHelper(data)
node.right = self.deseriHelper(data)
return node
a = TreeNode('1')
b = TreeNode('2')
c = TreeNode('3')
b.left, b.right = a, c
s = Codec()
ans = s.serialize(b)
print ans
ans = s.deserialize(ans)
print ans.val, ans.left.val, ans.right.val
P4. Sudoku Solver
好吧，这道题是典型的back tracking, 过了一年再来写。感觉又有一些感触。 主要是怎么back tracking。我发现我有时候还是有点处理不好recursive body。比如这道题。如果当前的位置不是'.'， 那么就该直接return 他的下一位的结果。因为根本不用back tracking我记得之前好像也犯过类似的错误。
class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return board
dic = set()
for i in range(len(board)):
for j in range(len(board)):
num = board[i][j]
if num != '.':
row, col, square = ('row', i, num), ('col', j, num), (i//3, j//3, num)
dic.add(row)
dic.add(col)
dic.add(square)
self.helper(0, 0, board, dic)
return board
def helper(self, i, j, board, dic):
# print board[0], i, j
if i == len(board)-1 and j == len(board[0]):
return True
if j == len(board[0]):
i += 1
j = 0
if board[i][j] != '.':
return self.helper(i, j+1, board, dic)
for num in '123456789':
row, col, square = ('row', i, num), ('col', j, num), (i//3, j//3, num)
if row not in dic and col not in dic and square not in dic:
board[i][j] = num
dic.add(row)
dic.add(col)
dic.add(square)
if self.helper(i, j+1, board, dic):
return True
board[i][j] = '.'
dic.remove(row)
dic.remove(col)
dic.remove(square)
board = [
[".",".","9","7","4","8",".",".","."],
["7",".",".",".",".",".",".",".","."],
[".","2",".","1",".","9",".",".","."],
[".",".","7",".",".",".","2","4","."],
[".","6","4",".","1",".","5","9","."],
[".","9","8",".",".",".","3",".","."],
[".",".",".","8",".","3",".","2","."],
[".",".",".",".",".",".",".",".","6"],
[".",".",".","2","7","5","9",".","."]]
s = Solution()
ans = s.solveSudoku(board)
print ans
另外一种号称更加清晰的方法
class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
self.board = board
self.row = [[1]*10 for i in range(9)]
self.col = [[1]*10 for i in range(9)]
self.box = [[[1]*10 for i in range(3)] for _ in range(3)]
for i in range(9):
for j in range(9):
if board[i][j]!='.':
v = int(board[i][j])
self.row[i][v] = self.col[j][v] = self.box[i//3][j//3][v] = 0
self.BT(0, 0)
def BT(self, i, j):
if i==9:
return True
if self.board[i][j] != '.':
return self.BT(i+ (j+1)//9, (j+1)%9)
for v in range(1,10):
if self.row[i][v] and self.col[j][v] and self.box[i//3][j//3][v]:
self.board[i][j] = str(v)
self.row[i][v] = self.col[j][v] = self.box[i//3][j//3][v] = 0
if self.BT(i+ (j+1)//9, (j+1)%9): return True
self.row[i][v] = self.col[j][v] = self.box[i//3][j//3][v] = 1
self.board[i][j] = '.'
return False
board = [
[".",".","9","7","4","8",".",".","."],
["7",".",".",".",".",".",".",".","."],
[".","2",".","1",".","9",".",".","."],
[".",".","7",".",".",".","2","4","."],
[".","6","4",".","1",".","5","9","."],
[".","9","8",".",".",".","3",".","."],
[".",".",".","8",".","3",".","2","."],
[".",".",".",".",".",".",".",".","6"],
[".",".",".","2","7","5","9",".","."]]
s = Solution()
ans = s.solveSudoku(board)
print board
P5. Word Break II
我好像在写word break 1的时候就把2给写了。
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
self.memo = collections.defaultdict(list)
self.dfs(s, 0, len(s), wordDict)
return self.memo[(0,len(s))]
def dfs(self, s, i, j, wordDict):
if (i, j) not in self.memo:
if s[i:j] in wordDict: # if in the dict add to memo
self.memo[(i, j)] += [s[i:j]]
for k in range(i+1,j):
if s[i:k] in wordDict: # take the first part
tail = self.dfs(s, k, j, wordDict) # recurse rest
self.memo[(i,j)] += [s[i:k]+' '+t for t in tail]
return self.memo[(i, j)]
这道题我airbnb我刚写过呀。我直接复制粘贴过来一下好了。说明这道题真是高频题目
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
import heapq
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
heap = []
dummy = ListNode()
cur = dummy
for node in lists:
if node:
heapq.heappush(heap, [node.val, node])
while heap:
tmp = heapq.heappop(heap)
cur.next = tmp
cur = cur.next
if tmp.next:
heapq.heappush(heap, tmp.next)
return dummy.next
这道题说明了，平时瞎逼逼讨论数据结构确实有用。去年我跟玩神才讨论过这道题。你看这不就变成著名公司Uber的面试题目了么。来我们大概把这道题写一遍。这道题我也能AC, 说明我确实有点厉害啊。
class Node(object):
def __init__(self, key):
self.key = key
self.count = 1
self.left = None
self.right = None
def __repr__(self):
print self.key
return repr(self.right)
class AllOne(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.head = None
self.tail = None
self.dic = {}
def inc(self, key):
"""
Inserts a new key <Key> with value 1. Or increments an existing key by 1.
:type key: str
:rtype: void
"""
if not self.dic:
node = Node(key)
self.dic[key] = node
self.head = node
self.tail = node
else:
if key not in self.dic:
node = Node(key)
self.dic[key] = node
self.tail.right = node
node.left = self.tail
self.tail = node
else:
node = self.dic[key]
node.count += 1
while node.left and node.count > node.left.count:
# swap 2 nodes
if self.tail == node:
self.tail = node.left
self.swap(node.left, node)
if not node.left:
self.head = node
def dec(self, key):
"""
Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
:type key: str
:rtype: void
"""
if key not in self.dic:
return
else:
node = self.dic[key]
node.count -= 1
while node.right and node.count < node.right.count:
# swap 2 nodes
if self.head == node:
self.head = node.right
self.swap(node, node.right)
if not node.right:
self.tail = node
if not node.count and len(self.dic) == 1:
self.head = None
self.tail = None
self.dic = {}
if not node.count and node.left:
self.tail = node.left
del self.dic[key]
node.left.right = None
def getMaxKey(self):
"""
Returns one of the keys with maximal value.
:rtype: str
"""
if self.head:
return self.head.key
else:
return ""
def getMinKey(self):
"""
Returns one of the keys with Minimal value.
:rtype: str
"""
if self.tail:
return self.tail.key
else:
return ""
def swap(self, left, right):
leftLeft = left.left
rightRirhgt = right.right
left.right = rightRirhgt
left.left = right
right.left = leftLeft
right.right = left
if rightRirhgt:
rightRirhgt.left = left
if leftLeft:
leftLeft.right = right
s = AllOne()
s.inc('a')
s.inc('b')
s.inc('c')
s.inc('d')
s.inc('a')
s.inc('b')
s.inc('c')
s.inc('d')
s.inc('c')
print s.tail.key
print s.tail.left.key
s.inc('d')
s.inc('d')
s.inc('a')
果然Pokemon永远是高山啊！仰止仰止！抄一个答案以示尊敬。
def minWindow(self, s, t):
need, missing = collections.Counter(t), len(t)
i = I = J = 0
for j, c in enumerate(s, 1):
missing -= need[c] > 0
need[c] -= 1
if not missing:
while i < j and need[s[i]] < 0:
need[s[i]] += 1
i += 1
if not J or j - i <= J - I:
I, J = i, j
return s[I:J]
P9. Regular Expression Matching
面试前得记得再写一次哟
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
dp = [ [False]*(len(s) + 1) for _ in range(len(p) + 1) ]
dp[0][0] = True
for i in range(1, len(p) + 1):
for j in range(1, len(s) + 1):
if p[i-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[i-1] == '*':
dp[i][j] = dp[i-1][j-1] or dp[i-1][j] or dp[i][j-1]
if i >= 2 and j >= 2:
dp[i][j-2] = dp[i-2][j-2]
else:
dp[i][j] = dp[i-1][j-1] and p[i-1] == s[j-1]
return dp[-1][-1] == 1
args = ["aab", "c*a*b"]
s = Solution()
print s.isMatch("aa","a")
print s.isMatch("aa","aa")
print s.isMatch("aaa","aa")
print s.isMatch("aa", "a*")
print s.isMatch("aa", ".*")
print s.isMatch("ab", ".*")
print s.isMatch("aab", "c*a*b")
P10. LRU Cache
hmm最后一题了。
import collections
class LRUCache(object):
def __init__(self, capa):
self.dic = collections.OrderedDict()
self.capa = capa
def get(self, key):
if key in self.dic:
value = self.dic.pop(key)
self.dic[key] = value
return value
def set(self, key, val):
if key in self.dic:
self.dic.pop(key)
elif len(self.dic)==self.capa:
self.dic.popitem(last=False)
self.dic[key]=val
so = LRUCache(5)
so.set(1,1)
so.set(2,2)
so.set(3,3)
so.set(4,4)
so.set(5,5)
so.set(6,6)
so.set(7,7)
print so.dic