LC
这道题，解法很多种，其实考这种题目最难对付了。重点还是在于跟面试官交流。
class Codec:
def __init__(self):
self.count = 0
self.dic = {}
def encode(self, longUrl):
"""Encodes a URL to a shortened URL.
:type longUrl: str
:rtype: str
"""
url = 'http://tinyurl.com/' + str(self.count)
self.dic[self.count] = longUrl
self.count += 1
return url
def decode(self, shortUrl):
"""Decodes a shortened URL to its original URL.
:type shortUrl: str
:rtype: str
"""
count = shortUrl.split('/')[-1]
return self.dic[int(shortUrl.split('/')[-1])]
words = ['app', 'apple', 'abc']
s = Codec()
a = s.encode('www.google.com')
b = s.decode(a)
print(b)
换一种写法，参考的pokemon哥哥的。
import string, random
char = string.ascii_letters + '1234567890'
class Codec:
def __init__(self):
self.l2s = {}
self.s2l = {}
def encode(self, longUrl):
"""Encodes a URL to a shortened URL.
:type longUrl: str
:rtype: str
"""
while longUrl not in self.l2s:
url = ''
for i in range(6):
num = random.randrange(0, len(char))
url += char[num]
if url not in self.s2l:
self.s2l[url] = longUrl
self.l2s[longUrl] = url
return self.l2s[longUrl]
def decode(self, shortUrl):
"""Decodes a shortened URL to its original URL.
:type shortUrl: str
:rtype: str
"""
short = shortUrl.split('/')[-1]
return self.s2l[short]
words = ['app', 'apple', 'abc']
s = Codec()
a = s.encode('www.google.com')
b = s.decode(a)
print(b)
print(a)
P3. Replace Words
这道题是一道很好的trie的应用题目啊。下次拿这道题来考人好了。顺便感慨一下今天学的debug方法真的是由棒又好，大概就是建一个trie。然后如果在trie里就replace掉它。
class node():
def __init__(self):
self.dic = {}
self.is_word = False
def __repr__(self):
return repr(self.dic)
class Trie():
def __init__(self, words):
self.root = node()
for w in words:
self.add(w)
def add(self, word):
cur = self.root
for c in word:
if c not in cur.dic:
cur.dic[c] = node()
cur = cur.dic[c]
cur.is_word = True
def search(self, word):
cur = self.root
for i in range(len(word)):
c = word[i]
if c not in cur.dic:
return word
cur = cur.dic[c]
if cur.is_word:
return word[:i+1]
return word
class Solution(object):
def replaceWords(self, dict, sentence):
"""
:type dict: List[str]
:type sentence: str
:rtype: str
"""
trie = Trie(dict)
res = []
words = sentence.split()
for word in words:
tmp = trie.search(word)
res.append(tmp)
return ' '.join(res)
dict = ["e","k","c","harqp","h","gsafc","vn","lqp","soy","mr","x","iitgm","sb","oo","spj","gwmly","iu","z","f","ha","vds","v","vpx","fir","t","xo","apifm","tlznm","kkv","nxyud","j","qp","omn","zoxp","mutu","i","nxth","dwuer","sadl","pv","w","mding","mubem","xsmwc","vl","farov","twfmq","ljhmr","q","bbzs","kd","kwc","a","buq","sm","yi","nypa","xwz","si","amqx","iy","eb","qvgt","twy","rf","dc","utt","mxjfu","hm","trz","lzh","lref","qbx","fmemr","gil","go","qggh","uud","trnhf","gels","dfdq","qzkx","qxw"]
sentence = "ikkbp miszkays wqjferqoxjwvbieyk gvcfldkiavww vhokchxz dvypwyb bxahfzcfanteibiltins ueebf lqhflvwxksi dco kddxmckhvqifbuzkhstp wc ytzzlm gximjuhzfdjuamhsu gdkbmhpnvy ifvifheoxqlbosfww mengfdydekwttkhbzenk wjhmmyltmeufqvcpcxg hthcuovils ldipovluo aiprogn nusquzpmnogtjkklfhta klxvvlvyh nxzgnrveghc mpppfhzjkbucv cqcft uwmahhqradjtf iaaasabqqzmbcig zcpvpyypsmodtoiif qjuiqtfhzcpnmtk yzfragcextvx ivnvgkaqs iplazv jurtsyh gzixfeugj rnukjgtjpim hscyhgoru aledyrmzwhsz xbahcwfwm hzd ygelddphxnbh rvjxtlqfnlmwdoezh zawfkko iwhkcddxgpqtdrjrcv bbfj mhs nenrqfkbf spfpazr wrkjiwyf cw dtd cqibzmuuhukwylrnld dtaxhddidfwqs bgnnoxgyynol hg dijhrrpnwjlju muzzrrsypzgwvblf zbugltrnyzbg hktdviastoireyiqf qvufxgcixvhrjqtna ipfzhuvgo daee r nlipyfszvxlwqw yoq dewpgtcrzausqwhh qzsaobsghgm ichlpsjlsrwzhbyfhm ksenb bqprarpgnyemzwifqzz oai pnqottd nygesjtlpala qmxixtooxtbrzyorn gyvukjpc s mxhlkdaycskj uvwmerplaibeknltuvd ocnn frotscysdyclrc ckcttaceuuxzcghw pxbd oklwhcppuziixpvihihp"
s = Solution()
ans = s.replaceWords(dict, sentence)
print(ans)
大神的解法
def replaceWords(self, roots, sentence):
_trie = lambda: collections.defaultdict(_trie)
trie = _trie()
END = True
for root in roots:
cur = trie
for letter in root:
cur = cur[letter]
cur[END] = root
def replace(word):
cur = trie
for letter in word:
if letter not in cur: break
cur = cur[letter]
if END in cur:
return cur[END]
return word
return " ".join(map(replace, sentence.split()))
先写个最正常的dfs
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res = []
self.helper(n, n, '', res)
return res
def helper(self, l, r, path, res):
if l<0 or r<0:
return
if not l and not r:
res.append(path)
return
self.helper(l-1, r, path + '(', res)
if r>l:
self.helper(l, r-1, path + ')', res)
args = [2]
s = Solution()
ans = s.generateParenthesis(*args)
print(ans)
pokemon大神的答案。精彩之处在于这个res居然是指向同一个地址的。太夸张了。
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
return self.helper(n, n, '')
def helper(self, l, r, path, res = []):
if 0 <= l <= r:
if not r:
res.append(path)
self.helper(l-1, r, path + '(')
self.helper(l, r-1, path + ')')
return res
args = [3]
s = Solution()
ans = s.generateParenthesis(*args)
print(ans)
P5. Kth Smallest Element in a BST
写了一个非常丑陋的。我大概知道要用in order traversal，然后每次放中间的时候加1。直到hit到了第k位就赋值。
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
self.k = k
self.val = None
self.helper(root)
return self.val
def helper(self, root):
if root:
self.helper(root.left)
self.k -= 1
if self.k == 0:
self.val = root.val
return
self.helper(root.right)
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
s = Solution()
ans = s.kthSmallest(b, 3)
print(ans)
看来 写得也不太丑嘛。换一个iterative的写法。
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
stack = []
while stack or root:
while root:
stack.append(root)
root = root.left
tmp = stack.pop()
k -= 1
if k == 0:
return tmp.val
if tmp.right:
stack.append(tmp.right)
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
s = Solution()
ans = s.kthSmallest(b, 3)
print(ans)
再写一个generator版本的
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
for val in self.in_order(root):
k -= 1
if k == 0:
return val
def in_order(self, root):
if root:
for val in self.in_order(root.left):
yield val
yield root.val
for val in self.in_order(root.right):
yield val
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
s = Solution()
ans = s.kthSmallest(b, 3)
print(ans)
P6. House Robber III
这道题就是优化问题，然后加上memo来剪枝。
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.memo = {}
return self.helper(root)
def helper(self, root):
if root not in self.memo:
if not root:
return 0
childrenValue = self.helper(root.left) + self.helper(root.right)
if root.left:
gradLeft = self.helper(root.left.left) + self.helper(root.left.right)
else:
gradLeft = 0
if root.right:
gradRight = self.helper(root.right.left) + self.helper(root.right.right)
else:
gradRight = 0
self.memo[root] = max(childrenValue, root.val + gradLeft + gradRight)
return self.memo[root]
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
s = Solution()
ans = s.rob(b)
print(ans)
P7. Exclusive Time of Functions
这道题把我折磨惨了！这道题有点merge business interval的意思。这个if很重要，如果没有的话，就不能track之前还没跑完的function.
class Solution(object):
def exclusiveTime(self, n, logs):
"""
:type n: int
:type logs: List[str]
:rtype: List[int]
"""
ans = [0]*n
stack = []
pre_time = 0
for log in logs:
(num, status, time) = log.split(':')
num, time = int(num), int(time)
if status == 'start':
if stack:
ans[stack[-1]] += time - pre_time
stack.append(num)
pre_time = time
else:
pre_num = stack.pop()
ans[pre_num] += time - pre_time + 1
pre_time = time + 1
return ans
n = 2
logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
s = Solution()
ans = s.exclusiveTime(n, logs)
print(ans)
这道题大佬们都写得好飘。我只能乖乖的dfs，而且还memory爆掉了。擦。
class Solution(object):
def getFactors(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
return self.dfs(n, [], [], 2)
def dfs(self, n, path, res, start):
if n==1 and len(path) > 1:
res.append(path+[])
return
print int(math.sqrt(n+1))
for i in range(start, n+1):
if n%i == 0:
path.append(i)
self.dfs(n/i, path, res, i)
path.pop()
return res
s = Solution()
ans = s.getFactors(16)
print(ans)
放一个乐神的答案以供瞻仰
class Solution(object):
def getFactors(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
ans, stack, x = [], [], 2
while True:
if x > n / x:
if not stack:
return ans
ans.append(stack + [n])
x = stack.pop()
n *= x
x += 1
elif n % x == 0:
stack.append(x)
n /= x
else:
x += 1
s = Solution()
ans = s.getFactors(16)
print(ans)
我觉得这道题，我解得很巧妙呀。我用相对位置做key。然后用一个list来存相对位置相同的单词。扫一遍就出结果了。
import collections
class Solution(object):
def groupStrings(self, strings):
"""
:type strings: List[str]
:rtype: List[List[str]]
"""
dic = collections.defaultdict(list)
for s in strings:
key = tuple(ord(c)-ord(s[0]) for c in s)
dic[key].append(s)
res = [val for key, val in dic.items()]
return res
s = Solution()
ans = s.groupStrings(["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"])
print ans
P10. Subsets
终于有一道题能欺负的题目了。就是一个dfs下去就行了。用一个index来决定取不取当前这一位。然后我们再来玩点飘的！注意我在递归的时候省略了res。但是结果仍然是对的。
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
return self.dfs(nums)
def dfs(self, nums, path = [], index=0, res=[]):
if index==len(nums):
res.append(path)
return
self.dfs(nums, path + [nums[index]], index + 1)
self.dfs(nums, path, index + 1)
return res
s = Solution()
ans = s.subsets([1, 2, 3])
print ans