sc 21-30
P21. 24点游戏。给你几个数字，判断他们做加减乘除运算是否可以得到24，顺序可以是任意的。dfs搜索搞定。。。但是这里要注意一些细节，每次计算得到新的数之后最好加入数组做下一次搜索，不然容易出错。
思路：就是DFS，这个问题好有趣。我加入了Path 来打印出结果，方便理解。
class Solution(object):
def game24(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
return self.dfs(nums, '')
def dfs(self, nums, path):
"""
:type nums: List[int]
:type cur: int
:type path: str
:rtype: bool
"""
if len(nums)==1 and nums[0]==24:
print path
return True
for i in range(len(nums)-1):
for j in range(i+1,len(nums)):
tmp = nums[i]+nums[j]
if self.dfs(nums[:i]+nums[i+1:j]+nums[j+1:] + [tmp], path + ' ' + str(nums[i])+'+'+str(nums[j])):
return True
tmp = nums[i]-nums[j]
if self.dfs(nums[:i]+nums[i+1:j]+nums[j+1:] + [tmp], path + ' ' + str(nums[i])+'-'+str(nums[j])):
return True
tmp = nums[i]*nums[j]
if self.dfs(nums[:i]+nums[i+1:j]+nums[j+1:] + [tmp], path + ' ' + str(nums[i])+'*'+str(nums[j])):
return True
tmp = nums[i]/nums[j]
if self.dfs(nums[:i]+nums[i+1:j]+nums[j+1:] + [tmp], path + ' ' + str(nums[i])+'/'+str(nums[j])):
return True
return False
nums = [1,3,1,5]
so = Solution()
print so.game24(nums)
P22. 一个是 word break 2，给个字典，如何break Ilovenyc .
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
memo = {len(s): ['']}
def sentences(i):
if i not in memo:
memo[i] = [s[i:j] + (tail and ' ' + tail)
for j in range(i+1, len(s)+1)
if s[i:j] in wordDict
for tail in sentences(j)]
return memo[i]
return sentences(0)
def dfs(s, wordDict, cur, res):
if not s: return [None]
if s in wordDict:
return res.append((cur + ' ' + s).strip())
for word in wordDict:
l = len(word)
if word == s[:l]:
dfs(s[l:], wordDict, cur+' '+ s[:l], res)
P23. 判断一个图是不是 bipartite: https://en.wikipedia.org/wiki/Bipartite_graph
思路：BFS解，到下一个node的时候换另一个颜色。然后check下访问过的node的颜色就行了。
class Solution():
def isBipartite(self, graph):
"""
:type graph: dict[List]
:rtype: bool
"""
s = [1]
visited = {1:0}
while s:
tmp = s.pop(0)
children = graph[tmp]
color = visited[tmp]
for c in children:
if c in visited:
if visited[c] + color!=1:
return False
else:
s.append(c)
visited[c] = 1 if color==0 else 0
print(visited)
return True
graph = {1:[2,3], 4:[2,3], 2:[1,4], 3:[1,4]}
so = Solution()
print(so.isBipartite(graph))
P24. 一面国人小哥，人非常好。题目是面经里提过的 toddle() 和 getToddleList()，具体可以看这个帖子:
http://www.1point3acres.com/bbs/thread-160016-1-1.html
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Solution():
def __init__(self):
self.root = None
self.tail = None
self.table = {}
def toggle(self, val):
if val not in self.table:
node = Node(val)
self.table[val] = node
if not self.root:
self.root = node
self.tail = node
else:
node.left = self.tail
self.tail.right = node
self.tail = node
else:
node = self.table[val]
pre = node.left
cur = node.right
if pre:
pre.right = cur
if cur:
cur.left = pre
def getList(self):
res = []
node = self.root
while node:
res.append(node.val)
node = node.right
return res
so = Solution()
so.toggle(1)
so.toggle(2)
so.toggle(3)
so.toggle(2)
print so.getList()
P25. 3sum
https://leetcode.com/problems/3sum/
class Solution():
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
for i in range(len(nums)-2):
if i>0 and nums[i-1]==nums[i]:
continue
a = nums[i]
l, r = i+1, len(nums)-1
while l<r:
if a + nums[l] + nums[r] == 0:
res.append([a, nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
elif a + nums[l] + nums[r]<0:
l += 1
else:
r -= 1
return res
nums = [-1, 0, 1, 2, -1, -4]
so = Solution()
print so.threeSum(nums)
P26. 题目是用前序和中序数组重建二叉树，LC 原题。
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
思路: 就是用Inorder来做参照，如果inorder没了，说明不能继续recurse下去了。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if inorder:
num = preorder.pop(0)
root = TreeNode(num)
index = inorder.index(num)
root.left = self.buildTree(preorder, inorder[:index])
root.right = self.buildTree(preorder, inorder[index+1:])
return root
再来一个
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if inorder:
num = postorder.pop()
root = TreeNode(num)
index = inorder.index(num)
root.right = self.buildTree(inorder[index+1:], postorder)
root.left = self.buildTree(inorder[:index], postorder)
return root
P27. 分享个楼主惨痛的snapchat电面。OA就不说了，简单的数独问题， 做完当天下午约电面，电面是国人大叔。在面之前也是跟其他人一样，把地里的题都刷了一遍，什么bigInteger， DP， Zigzag print等等。 结果电面不是这些啊，并且楼主成功被自己蠢哭，第一题就没搞定。干货： 一个dictionary里面存String单词，有millions这么多，给一个char array， 让返回所有的单词，这些单词的所有字母必须在char array里面。比如：char array = {a,c,a,r,t}, dictionary={"a","aa","cat","cats","aaa","cc"} 那么你返回的list里面包含的单词应该是：a, aa, cat这类的。其实我并不知道为啥aa也算单词， 不包含的像cats， aaa, cc这样的。
思路：刚开始我说：将char array处理成map
悲剧就此时发生，楼主对trie里面的成员变量理解的不够深刻。想DFS去遍历，但是不会写呜呜呜呜呜~哎~都别问我为什么，因为不知道怎么写循环，而且那会没想清楚就开始写代码，写到一半发现，不会用trie里的成员变量呢，就慌了。一个小时硬是没做出来，我也是醉醉的。面试结束，自己静下心来，20分钟竟然写出来了，我擦擦擦擦擦擦。
我的思路: 我怎么觉得这道题不应该用Trie啊
class Solution(object):
def validWord(self, charArray, words):
"""
:type charArray: List[char]
:type words: List[str]
:rtype: List[str]
"""
dic = set(charArray)
res = []
for w in words:
tmp = set(w)
if len(tmp| dic)==len(dic):
res.append(w)
return res
charArray = ['a', 'c', 'a', 'r', 't']
words= ["a","aa","cat","cats","aaa","cc"]
so = Solution()
a = so.validWord(charArray, words)
print a
P28.We obtained a log file containing runtime information about all threads and mutex locks of a user program. The log file contains N lines of triplets about threads acquiring or releasing mutex locks. The format of the file is: The first line contains an integer N indicating how many more lines are in the file. Each of the following N lines contains 3 numbers separated by space. The first number is an integer representing thread_id (starting from 1). The second number is either 0 (acquiring) or 1 (releasing). The third number is an integer representing mutex_id (starting from 1). Now we want you to write a detector program that reads the logs line by line and output the line number of the trace where a deadlock happens. If there is no deadlock after reading all log traces, output 0.
Example:
4
1 0 1
2 0 2
2 0 1
1 0 2.
Output:
4
中文描述:其实就是维护一个图，然后每新读一个record就找一次有没有环的说。因为mutex如果有环才会死锁。中间那个数为0就加一条边，中间那个数为1就减少一条边。代码如下。还是比较简单的。
import collections
class Solution(object):
def lockDetector(self, log):
"""
:type charArray: List[char]
:type words: List[str]
:rtype: List[str]
"""
graph = collections.defaultdict(set)
for i in range(len(log)):
[a, b, c] = log[i]
if b:
graph[a].remove(c)
else:
if a!=c:
graph[a].add(c)
self.visited = set()
if self.findCircle(a, graph):
return i+1
return -1
def findCircle(self, a, graph):
s = [a]
while s:
tmp = s.pop()
children = graph[tmp]
if tmp not in self.visited:
self.visited.add(tmp)
else:
return True
for c in children:
s.append(c)
return False
log = [[1,0,1], [2,0,2], [2,0,1], [1,0,2]]
so = Solution()
a = so.lockDetector(log)
print(a)
P29 上来说implement big number library的时候 我吓了一身冷汗 然后发现是 two strings 加减乘除 才放心开始写 但是要在codepad上run 发现自己写zero-bug code的能力还是不太行。。。 改了改bug 写了unit test 时间就差不多没了。。所以没写完全部operation 哭。。。
class Solution(object):
def add(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1 = list(num1)[::-1]
num2 = list(num2)[::-1]
if len(num1)<len(num2):
num1, num2 = num2, num1
carry = 0
index = 0
while index<len(num1):
n2 = int(num2[index]) if index<len(num2) else 0
tmp = n2 + int(num1[index]) + carry
cur = tmp%10
carry = tmp//10
num1[index] = str(cur)
index += 1
if carry: num1.append('1')
return ''.join(num1[::-1])
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1 = num1[::-1]
num2 = num2[::-1]
res = [0]*(len(num1) + len(num2))
for i in range(len(num2)):
for j in range(len(num1)):
tmp = int(num2[i])*int(num1[j])
res[j+i] += tmp
res[j+i+1] += res[j+i]//10
res[j+i] = res[j+i]%10
while len(res)>1 and res[-1]==0:
res.pop()
return ''.join(map(str,res))[::-1]
num1 = '124'
num2 = '5679'
so = Solution()
a = so.add(num1, num2)
print(a)
a = so.multiply(num1, num2)
print(a)
P30.准备的面经题一道没有。面的是secretSanta, 简单的说就是，每个人都必须给别人礼物，每个人都必须收礼物。自己不能给自己礼物。 string[] name = {mary, alice, mike}; output： mary -> mike mike -> alice, alice -> marry 错误情况是：marry ->mike, mike -> marry, alice ->
class Solution():
def secretSanta(self, names):
res = []
self.dfs(names, names, [], res)
return res
def dfs(self, giver, receiver, cur, res):
if not giver:
cur.sort()
res.append(cur)
for j in range(len(receiver)):
if giver[0]!=receiver[j]:
new_giver = giver[1:]
new_receiver = receiver[:j] + receiver[j+1:]
record = giver[0] + '->' + receiver[j]
self.dfs(new_giver, new_receiver, cur + [record], res)
names = ['A', 'B', 'C']
so = Solution()
a = so.secretSanta(names)
print a
print len(a)