class TwoSum:
def __init__(self):
self.counter = {}
"""
@param number: An integer
@return: nothing
"""
def add(self, number):
# write your code here
self.counter[number] = self.counter.get(number, 0) + 1
#O(1)
"""
@param value: An integer
@return: Find if there exists any pair of numbers which sum is equal to the value.
"""
def find(self, value):
# write your code here
#O(n)
for key in self.counter:
if value - key in self.counter and value != key *2:
return True
if value == key * 2 and self.counter[key] >= 2:
return True
return False
Flatten Binary Tree to Linked List – Python 3 (Week 14 – 16)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: a TreeNode, the root of the binary tree
@return: nothing
"""
def flatten(self, root):
# write your code here
self.helper(root)
def helper(self, root):
if not root:
return root
left_last = self.helper(root.left)
right_last = self.helper(root.right)
if left_last:
left_last.right = root.right
root.right = root.left
root.left = None
return right_last or left_last or root
Lowest Common Ancestor II – Python 3 (Week 14 – 15)
"""
Definition of ParentTreeNode:
class ParentTreeNode:
def __init__(self, val):
self.val = val
self.parent, self.left, self.right = None, None, None
"""
class Solution:
"""
@param: root: The root of the tree
@param: A: node in the tree
@param: B: node in the tree
@return: The lowest common ancestor of A and B
"""
def lowestCommonAncestorII(self, root, A, B):
# write your code here
parentset = set()
while A is not root:
parentset.add(A)
A = A.parent
while B is not root:
if B in parentset:
return B
B = B.parent
return root
Lowest Common Ancestor of a Binary Tree – Python 3 (Week 14 – 14)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: The root of the binary search tree.
@param: A: A TreeNode in a Binary.
@param: B: A TreeNode in a Binary.
@return: Return the least common ancestor(LCA) of the two nodes.
"""
def lowestCommonAncestor(self, root, A, B):
# write your code here
if not root:
return None
if root is A or root is B:
return root
left = self.lowestCommonAncestor(root.left, A, B)
right = self.lowestCommonAncestor(root.right, A, B)
if left is None and right is None:
return None
if right is None:
return left
if left is None:
return right
return root
Time, Space O(n).
Minimum Subtree – Python 3 (Week 14 – 13)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of binary tree
@return: the root of the minimum subtree
"""
def findSubtree(self, root):
# write your code here
mini, subtree, sum = self.helper(root)
return subtree
def helper(self, root):
if root is None:
return sys.maxsize, None, 0
left_mini, left_subtree, left_sum = self.helper(root.left)
right_mini, right_subtree, right_sum = self.helper(root.right)
sum = left_sum + right_sum + root.val
if left_mini == min(left_mini, right_mini, sum):
return left_mini, left_subtree, sum
if right_mini == min(left_mini, right_mini, sum):
return right_mini, right_subtree, sum
return sum, root, sum
Time, Space O(n).
Balanced Binary Tree – Python 3 (Week 14 – 12)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
not_balance = -1
class Solution:
"""
@param root: The root of binary tree.
@return: True if this Binary tree is Balanced, or false.
"""
def isBalanced(self, root):
# write your code here
return self.maxDepth(root) != not_balance
def maxDepth(self, root):
if not root:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
if left == not_balance or right == not_balance:
return not_balance
if abs(left - right) > 1:
return not_balance
return max(left, right) + 1
Time, Space O(d).
Serialize and Deserialize Binary Tree – Python 3 (Week 14 – 11)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root:
return []
data = []
queue = collections.deque([root])
while queue:
node = queue.popleft()
data.append(str(node.val) if node else '#')
if node:
queue.append(node.left)
queue.append(node.right)
return ','.join(data)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
order = [
TreeNode(int(val)) if val != '#' else None
for val in data.split(',')
]
root = order[0]
cur_node_index = 0
cur_child_index = 1
nodes = [root]
while cur_node_index < len(nodes):
node = nodes[cur_node_index]
cur_node_index += 1
node.left = order[cur_child_index]
node.right = order[cur_child_index + 1]
cur_child_index += 2
if node.left:
nodes.append(node.left)
if node.right:
nodes.append(node.right)
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
Time, Space O(n).
Sequence Reconstruction – Python 3 (Week 14 – 10)
class Solution:
"""
@param org: a permutation of the integers from 1 to n
@param seqs: a list of sequences
@return: true if it can be reconstructed only one or false
"""
def sequenceReconstruction(self, org, seqs):
# write your code here
graph = self.build_graph(seqs)
order = self.get_order(graph)
return order == org
def build_graph(self, seqs):
graph = {}
#O(m + m) O(n*n)
for seq in seqs:
for node in seq:
if node not in graph:
graph[node] = set()
for seq in seqs:
for i in range(1, len(seq)):
graph[seq[i - 1]].add(seq[i])
return graph
def get_order(self, graph):
# O(n^2) O(n)
indegree = self.get_indegree(graph)
queue = []
#O(n)
for node in indegree:
if indegree[node] == 0:
queue.append(node)
if len(queue) > 1: #should not use != 1 because case [],[[]]
return None
order = []
#O(n*2)
while queue:
node = queue.pop()
order.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
if len(queue) > 1:
return None
return order if len(order) == len(graph) else None
def get_indegree(self, graph):
indegree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
indegree[neighbor] += 1
return indegree
Time, Space O(n^2).
Maximum Average Subarray II – Python 3 (Week 14 – 09)
class Solution:
"""
@param nums: an array with positive and negative numbers
@param k: an integer
@return: the maximum average
"""
def maxAverage(self, nums, k):
# write your code here
start = min(nums)
end = max(nums)
n = len(nums)
while end - start >= 0.000001:
mid = (start + end) / 2
if self.check(mid, nums, k):
start = mid
else:
end = mid
return start
def check(self, mid, nums, k):
n = len(nums)
preSum = [0 for i in range(n+1)]
minPresum = 0
for i in range(1, n + 1):
preSum[i] = preSum[i - 1] + (nums[i - 1] - mid)
if i >= k:
minPresum = min(minPresum, preSum[i - k])
if i >= k and preSum[i] - minPresum >= 0:
return True
return False
Time O(log (max(nums)-min(nums))*n). Space O(log (max(nums)-min(nums))).
Copy Books – Python 3 ( Week 14 – 08)
class Solution:
"""
@param pages: an array of integers
@param k: An integer
@return: an integer
"""
def copyBooks(self, pages, k):
# write your code here
if pages == []:
return 0
start, end = max(pages), sum(pages)
while start + 1 < end:
mid = start + (end - start) // 2
if self.get_least_people(pages, mid) <= k:
end = mid
else:
start = mid
if self.get_least_people(pages, start) <= k:
return start
return end
#log(end - start) * number of book
def get_least_people(self, pages, time_limit):
count = 1
time_cost = 0
for page in pages:
if time_cost + page > time_limit:
count += 1
time_cost = page
else:
time_cost += page
return count
Time O(log(end – start) * number of book ). Space O(log(end -start)).
步步发财 