Tag Hard
Airbnb tag题真的好少啊。等做完hard我就去刷面经。
真是经典老题啊。用heap来implement一个priority queue. 写得时候 第一遍还是有一些edge case和拼写错误，真的是太久没刷了！
# 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
P2. Palindrome Pairs
先写一个最暴力的naive approach吧。
class Solution:
def palindromePairs(self, words):
"""
:type words: List[str]
:rtype: List[List[int]]
"""
n = len(words)
res = []
for i in range(n-1):
for j in range(i+1, n):
tmp = words[i] + words[j]
if tmp == tmp[::-1]:
res.append([i, j])
tmp = words[j] + words[i]
if tmp == tmp[::-1]:
res.append([j, i])
return res
args = [["abcd", "dcba", "lls", "s", "sssll"]]
s = Solution()
ans = s.palindromePairs(*args)
print(ans)
其实general idea还是挺简单的，就是各种corner case，太恶心了。先放这里吧，到时候回头来再写一遍
class Solution:
def palindromePairs(self, words):
"""
:type words: List[str]
:rtype: List[List[int]]
"""
d = dict([(w, i) for i, w in enumerate(words)])
res = []
for i, w in enumerate(words):
for j in xrange(len(w)+1):
prefix, postfix = w[:j], w[j:]
if prefix[::-1] in d and i != d[prefix[::-1]] and postfix == postfix[::-1]:
res.append([i, d[prefix[::-1]]])
if j>0 and postfix[::-1] in d and i != d[postfix[::-1]] and prefix == prefix[::-1]:
res.append([d[postfix[::-1]], i])
return res
args = [["abcd", "dcba", "lls", "s", "sssll"]]
s = Solution()
ans = s.palindromePairs(*args)
print(ans)
经典中的 经典啊！朕还能挣扎着写出来，说明宝刀未老！
import collections
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
pre = collections.defaultdict(set)
suc = collections.defaultdict(set)
for i in range(len(words)-1):
top = words[i]
bot = words[i+1]
for i in range(min(len(top), len(bot))):
if top[i] != bot[i]:
pre[top[i]].add(bot[i])
suc[bot[i]].add(top[i])
break
chars = set(''.join(words))
root = chars - set(suc.keys())
res = ''
while root:
tmp = root.pop()
res += tmp
for c in pre[tmp]:
suc[c].remove(tmp)
if not suc[c]:
root.add(c)
return res if len(res) == len(chars) else ''
args = [[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]]
s = Solution()
ans = s.alienOrder(*args)
print(ans)
P4. Regular Expression Matching
这道题跟 Wildcard Matching 是兄弟题型。感觉airbnb还是有点会选题目的，都是我以前做过的，觉得比较经典的题目。
确实有点不太好写，有一些比较tricky的corner case.
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")
P5. Word Search II
不得不说，这也是一道非常好的题目。不过我真的觉得 如果onsite的时候考candidate这道题，除非是45分钟全部用来做题。不然90%都会跪吧。详细的思路在这里
我一天面点别人combination sum，这些小朋友都写得磕磕绊绊的。挣扎着写完了这道题。我的奶奶呀。
class Node(object):
def __init__(self):
self.children = {}
self.isWord = False
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
if not board or not board[0]:
return []
# build a Trie
root = Node()
for w in words:
tmp = root
for c in w:
if c not in tmp.children:
tmp.children[c] = Node()
tmp = tmp.children[c]
tmp.isWord = True
n, m = len(board), len(board[0])
res = []
for i in range(n):
for j in range(m):
c = board[i][j]
if c in root.children:
node = root.children[c]
visited = [[False]*m for _ in range(n)]
self.find(board, node, i, j, c, res, visited)
return res
def find(self, board, node, d, p, path, res, visited):
visited[d][p] = True
if node.isWord:
res.append(path)
node.isWord = False
for i, j in [(d-1, p), (d+1, p), (d, p-1), (d, p+1)]:
if 0 <= i < len(board) and 0 <= j < len(board[0]) and not visited[i][j]:
if board[i][j] in node.children:
newNode = node.children[board[i][j]]
self.find(board, newNode, i, j, path+board[i][j], res, visited)
args = [ [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
], ["oath","pea","eat","rain"]]
s = Solution()
ans = s.findWords(*args)
print(ans)
这道题到时不难，就是些起来有点恶心。不过话说回来了，什么题不恶心。2sum最不恶心。哈哈
class Solution(object):
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
stack = []
curLen = 0
res = []
for w in words:
if not stack:
newLen = len(w)
else:
newLen = len(w) + 1
if curLen + newLen > maxWidth:
# generate a new line
newLine = ' '.join(stack)
res.append(newLine)
# clear stack
stack = [w]
curLen = len(w)
else:
stack.append(w)
curLen += newLen
if stack:
newLine = ' '.join(stack)
res.append(newLine)
return res
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
args = [words, maxWidth]
s = Solution()
ans = s.fullJustify(*args)
print(ans)
好吧 这个哥哥写得比我好多了。那个round robin确实写得好，不过我感觉他那个复杂度好高啊。每次 ' ' + ' '加的时候都会copy整个字符串。
class Solution(object):
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
res, cur, num_of_letters = [], [], 0
for w in words:
if num_of_letters + len(w) + len(cur) > maxWidth:
for i in range(maxWidth - num_of_letters):
cur[i%(len(cur)-1 or 1)] += ' '
res.append(''.join(cur))
cur, num_of_letters = [], 0
cur += [w]
num_of_letters += len(w)
return res + [' '.join(cur).ljust(maxWidth)]
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
args = [words, maxWidth]
s = Solution()
ans = s.fullJustify(*args)
print(ans)