LC
P21. Course Schedule
topo sort的经典题型。不过这道题的corner case感觉有点不太make sense.
import collections
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
if not prerequisites: return True
pre = collections.defaultdict(set)
nex = collections.defaultdict(set)
for p in prerequisites:
pre[p[0]].add(p[1])
nex[p[1]].add(p[0])
start = [k for k in nex if k not in pre]
l = len(set([k for k in nex] + [k for k in pre]))
res = []
while start:
tmp = start.pop()
res.append(tmp)
for c in nex[tmp]:
pre[c].remove(tmp)
if not pre[c]:
del pre[c]
if c not in pre:
start.append(c)
return len(res) == l
s = Solution()
ans = s.canFinish(2, [[1,0]])
print ans
P22. Search in Rotated Sorted Array
这道题还是写得有一点点挣扎。不过最后意识到了应该怎么写。就是先找到有序的那一段，然后判断target在不在里面，不过不在那么就一定在另外一段里面。我觉得这一段对于考验corner case特别强调。 2分查找的精髓在于，每一次循环都在缩小范围，而每一次解都应该在缩小的范围之内。
l和r是两个互相逼近的关系，因为这里用的//整除，所以，永远l永远都不可能通过+1到达r，极限的情况是比r小1。而光靠//， r就能够逼近l。所以这里r需要取len(nums)而不是len(nums)-1
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums: return -1
l, r = 0, len(nums)
while l < r:
mid = (l + r)//2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]: # left in order
if nums[0] <= target < nums[mid]:
r = mid
else:
l = mid + 1
else: # right in order
if nums[mid] < target <= nums[-1]:
l = mid + 1
else:
r = mid
return -1
s = Solution()
ans = s.search([4, 5, 6, 7, 0, 1, 2], 2)
print ans
P23. One Edit Distance
这道题，主要是能分析三种情况，一种是insert, 一种是replacement， 还有一种delete。遇到不一样的话，就可以通过长度来判断是哪一种。
class Solution(object):
def isOneEditDistance(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
ls, lt = len(s), len(t)
for i in range(min(ls, lt)):
if s[i] != t[i]:
if ls == lt:
return s[i+1:] == t[i+1:] # replacement
elif ls < lt:
return s[i:] == t[i+1:] # insert
elif ls > lt:
return s[i+1:] == t[i:] # delete
return abs(ls - lt) == 1 and (s in t or t in s) # the difference have to be the last char
s = Solution()
ans = s.isOneEditDistance('ac', 'acc')
print ans
P24. Find K Pairs with Smallest Sums
这道题是一道经典的heap的题目，不过总感觉用tuple写起来可读性不高。到时候还是要看看那天那个大神怎么用一个class然后重新定义build in equal method的。
import heapq
class Solution(object):
def kSmallestPairs(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[List[int]]
"""
pairs = [(-(i+j), i, j) for i in nums1 for j in nums2]
heap = []
for p in pairs:
if len(heap) == k:
if -p[0] < -heap[0][0]:
heapq.heappop(heap)
heapq.heappush(heap, p)
else:
heapq.heappush(heap, p)
return [[p[1], p[2]] for p in heap]
s = Solution()
ans = s.kSmallestPairs([1,1,2], [1,2,3], 2)
print ans
P25. Word Break
很喜欢这道题。
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
return self.helper(s, set(wordDict))
def helper(self, s, dic):
# base case
if not s:
return True
for i in range(1, len(s)+1):
if s[:i] in dic:
if self.helper(s[i:], dic):
return True
return False
s = Solution()
ans = s.wordBreak("leetcode", ["leet", "code"])
print ans
然后time limit exceed了。应该上面这种做法会重复计算很多路径，所以我们用memo来优化一下。
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
self.memo = {'': True}
return self.helper(s, set(wordDict))
def helper(self, s, dic):
# base case
if s in self.memo:
return self.memo[s]
for i in range(len(s), 0, -1):
if s[:i] in dic:
if self.helper(s[i:], dic):
self.memo[s] = True
return self.memo[s]
self.memo[s] = False
return self.memo[s]
word = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
dic = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
s = Solution()
ans = s.wordBreak(word, dic)
print ans
稍微再简化一下代码
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
return self.helper(s, set(wordDict), {'': True})
def helper(self, s, dic, memo):
if s not in memo:
for i in range(len(s), 0, -1):
if s[:i] in dic:
if self.helper(s[i:], dic, memo): # if any one of path works return True
memo[s] = True
return memo[s]
memo[s] = False # tried all the path, return False
return memo[s]
s = Solution()
ans = s.wordBreak("a", ["a"])
print ans
P26. Implement Trie (Prefix Tree)
这种题目，写熟了真的是毫无难度！
class Node(object):
def __init__(self):
self.dic = {}
self.isWord = False
def __repr__(self):
return repr(self.dic)
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = Node()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
cur = self.root
for s in word:
if s not in cur.dic:
cur.dic[s] = Node()
cur = cur.dic[s]
cur.isWord = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
cur = self.root
for s in word:
if s not in cur.dic:
return False
cur = cur.dic[s]
return cur.isWord
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
cur = self.root
for s in prefix:
if s not in cur.dic:
return False
cur = cur.dic[s]
return True
s = Trie()
s.insert('abc')
s.insert('abb')
print s.search('abd')
print s.root
P27. Reverse Words in a String II
这种string处理的题目遇到python, 真的是找死。
class Solution(object):
def reverseWords(self, str):
"""
:type str: List[str]
:rtype: void Do not return anything, modify str in-place instead.
"""
str[:] = list(' '.join(''.join(str).strip().split()[::-1]))
抄一个正常的放这里。
class Solution(object):
def reverseWords(self, s):
"""
:type s: a list of 1 length strings (List[str])
:rtype: nothing
"""
s.reverse()
index = 0
for i in range(len(s)):
if s[i] == " ":
s[index: i] = reversed(s[index: i])
index = i + 1
s[index: ] = reversed(s[index: ])
P28. Spiral Matrix
这道题，有点恶心，不过我们一层一层剥开他的心。
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix or not matrix[0]:
return []
res = []
while matrix:
# upper
res += matrix[0]
matrix = matrix[1:]
# right
if matrix and matrix[0]:
for row in matrix:
res.append(row.pop())
# buttom
if matrix and matrix[0]:
res += matrix[-1][::-1]
matrix = matrix[:-1]
# left
if matrix and matrix[0]:
for row in reversed(matrix):
res.append(row.pop(0))
return res
s = Solution()
ans = s.spiralOrder([
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
])
print ans
P29. Copy List with Random Pointer
这道题就是我去年去uber面试的那道题呀。有几个corner case没有特别处理好。
class RandomListNode(object):
def __init__(self, x):
self.label = x
self.next = None
self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
dic = {}
if not head:
return head
cur = head
while cur:
dic[cur] = RandomListNode(cur.label)
cur = cur.next
cur = head
while cur:
dic[cur].next = dic[cur.next] if cur.next else None
dic[cur].random = dic[cur.random] if cur.random else None
cur = cur.next
return dic[head]
P30. Clone Graph
我先写一个两遍过的解法。
# Definition for a undirected graph node
class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
if not node:
return node
dic = {}
stack = [node]
visited = set()
# deep copy node
while stack:
tmp = stack.pop()
visited.add(tmp)
dic[tmp.label] = UndirectedGraphNode(tmp.label)
for c in tmp.neighbors:
if c not in visited:
stack.append(c)
# copy neighbors
for n in visited:
for c in n.neighbors:
dic[n.label].neighbors.append(dic[c.label])
return dic[node.label]
a = UndirectedGraphNode(-1)
b = UndirectedGraphNode(1)
a.neighbors.append(b)
s = Solution()
ans = s.cloneGraph(a)
print ans.label
然后我再写一个一遍过的解法。
# Definition for a undirected graph node
class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
def __repr__(self):
return repr(self.label)
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
if not node:
return node
root = UndirectedGraphNode(node.label)
visited = {node.label: root}
stack = [node]
while stack:
cur = stack.pop()
for c in cur.neighbors:
if c.label not in visited:
stack.append(c)
visited[c.label] = UndirectedGraphNode(c.label)
visited[cur.label].neighbors.append(visited[c.label])
return root