-
Notifications
You must be signed in to change notification settings - Fork 305
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Google | Onsite #32
Comments
算法高频Money Exchange计算汇率,类似 LC 399 例子:
创建 class Solution(object):
def calcEquation(self, equations, values, queries):
self.graph = {}
self.build_graph(equations, values)
return [self.find_path(q) for q in queries]
def build_graph(self, equations, values):
def add_edge(f, t, value):
if f in self.graph:
self.graph[f].append((t, value))
else:
self.graph[f] = [(t, value)]
for vertices, value in zip(equations, values):
f, t = vertices
add_edge(f, t, value)
add_edge(t, f, 1/value)
def find_path(self, query):
b, e = query
if b not in self.graph or e not in self.graph:
return -1.0
q = collections.deque([(b, 1.0)])
visited = set()
while q:
front, cur_product = q.popleft()
if front == e:
return cur_product
visited.add(front)
for neighbor, value in self.graph[front]:
if neighbor not in visited:
q.append((neighbor, cur_product*value))
return -1.0 Unique Paths
参考LC里面的unique path,多加几个corner case。 class Solution:
def uniquePaths(self, m, n):
if not m or not n:
return 0
dp = [[1] * n] * m
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1] Minimum Cost to Hire K WorkersLC有这道题了,sort一遍按照(wage/quality)的ratio, 保证放入heap里面的是从性价比最高的考试,当放入的大小超出heap规定的k,找到heap里面quality最高的,因为超出k的时候,代表这个时候放入的值相对应的性价比会拉爆团队,这时候及时之前性价比高的员工,也会因为新的ratio而变得很贵,这时候约高的quality越贵。 class Solution(object):
def mincostToHireWorkers(self, quality, wage, K):
workers = []
for w, q in zip(wage, quality):
workers.append((float(w)/q, q))
workers.sort()
res = float('inf')
qsum = 0
heap = []
for r, q in workers:
heapq.heappush(heap, -q)
qsum += q
if len(heap) > K:
qsum += heapq.heappop(heap)
if len(heap) == K:
res = min(res, qsum * r)
return res Delete node in Doubly Linked List
'''
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
'''
def deleteNode(head, pos):
cur = head
if pos == 1:
head = head.next
head.prev = None
return
while cur.next and pos - 1 > 0:
cur = cur.next
pos -= 1
cur.prev.next = cur.next Array | String | HashMaximize Distance to Closest PersonExample 1:
Example 2:
复杂答案: class Solution(object):
def maxDistToClosest(self, nums):
res = 1
l, r = 0, 0
for i, num in enumerate(nums):
if num == 0:
r += 1
elif num == 1:
r = i
if nums[l] == 0 : #0001
res = max(res, r - l)
else:
if (r - l - 1) % 2 == 0: # odd
res = max(res, (r - l - 1) // 2)
else: # even
res = max(res, (r - l) // 2)
l = i
return max(res, r - l) 简答: class Solution:
def maxDistToClosest(self, seats):
start, n, ans = -1, len(seats), 0
for index, value in enumerate(seats):
if value == 0: continue
ans = index if start == -1 else max(ans, (index-start)//2)
start = index
return ans if seats[n-1] == 1 else max(ans, n-1-start) Coins in a Line
public class Solution {
public boolean firstWillWin(int n) {
boolean[] dp = new boolean[n + 1];
boolean[] flag = new boolean[n + 1];
return search(n, dp, flag);
}
boolean search(int i, boolean[] dp, boolean[] flag) {
if (flag[i] == true) {
return dp[i];
}
if (i == 0) {
dp[i] = false;
} else if (i == 1) {
dp[i] = true;
} else if (i == 2) {
dp[i] = true;
} else {
dp[i] = ! (search(i - 1, dp, flag) && search(i - 2, dp, flag));
}
flag[i] = true;
return dp[i];
}
} Equilibrium index of an array数组平衡index 就是在数组中找到一个index 他的左边和 跟右边和相等
用sum扫一遍得到 import unittest
def equilibrium(nums):
cur_sum = sum(nums)
leftsum = 0
for i, num in enumerate(nums):
cur_sum -= num
if leftsum == cur_sum: return i
leftsum += num
return -1
class MyTest(unittest.TestCase):
def test(self):
self.assertEqual(equilibrium([-7, 1, 5, 2, -4, 3, 0]), 3)
self.assertEqual(equilibrium([1, 0, 1]), 1)
if __name__ == '__main__':
unittest.main() 可能变种:
Extended Word连续3个相同
Follow up: #给予下面方程
def in_dictionary()
TreeTree TraversalPreorder class Solution(object):
def preorderTraversal(self, root):
res = []
stack = [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.right)
stack.append(node.left)
return res Postorder class Solution(object):
def postorderTraversal(self, root):
res, stack = [], [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
res.append(node.val)
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return res Level-order class Solution(object):
def levelOrder(self, root):
res = []
if not root: return res
q = [root]
while q:
res.append([node.val for node in q])
temp = []
for node in q:
if node.left:
temp.append(node.left)
if node.right:
temp.append(node.right)
q = temp
return res Binary Tree Maximum Path Sum
class Solution(object):
def maxPathSum(self, root):
self.res = - float('inf')
self.dfs(root)
return self.res
def dfs(self, root):
if not root: return 0
left = self.dfs(root.left)
right = self.dfs(root.right)
self.res = max(self.res, left + right + root.val)
cur_max = max(left, right) + root.val
return cur_max if cur_max > 0 else 0 Binary Expression Tree
class Et:
def __init__(self , value):
self.value = value
self.left = None
self.right = None
def isOperator(c):
if (c == '+' or c == '-' or c == '*'
or c == '/' or c == '^'):
return True
else:
return False
def inorder(t):
if t is not None:
inorder(t.left)
print t.value,
inorder(t.right)
def constructTree(postfix):
stack = []
for char in postfix :
if not isOperator(char):
t = Et(char)
stack.append(t)
else:
t = Et(char)
t1 = stack.pop()
t2 = stack.pop()
t.right = t1
t.left = t2
stack.append(t)
t = stack.pop()
return t
# test
postfix = "ab+ef*g*-"
r = constructTree(postfix)
print "Infix expression is"
inorder(r) 220系列 123
165. Compare Version Numbers750 Number Of Corner RectanglesTree Isomorphism ProblemLC 815. Bus Routes (bfs) 输入一个整数n 输出叶子树量为n的所有full binary treeDFS/BFS778. Swim in Rising Water
|
设计Design Hashmap
class Item(object):
def __init__(self, key, value):
self.key = key
self.value = value
class HashTable(object):
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]
def _hash_function(self, key):
return key % self.size
def set(self, key, value):
hash_index = self._hash_function(key)
for item in self.table[hash_index]:
if item.key == key:
item.value = value
return
self.table[hash_index].append(Item(key, value))
def get(self, key):
hash_index = self._hash_function(key)
for item in self.table[hash_index]:
if item.key == key:
return item.value
raise KeyError('Key not found')
def remove(self, key):
hash_index = self._hash_function(key)
for index, item in enumerate(self.table[hash_index]):
if item.key == key:
del self.table[hash_index][index]
return
raise KeyError('Key not found')
|
Google Onsite前2天准备
The text was updated successfully, but these errors were encountered: