Heaps BST
Heaps BST
class Solution:
# @param A : list of integers
# @param B : integer
# @return a list of integers
Profit Maximisation
import heapq
class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def solve(self, A, B):
cost = 0
A = [-el for el in A]
heapq.heapify(A)
for i in range(B):
smallest = A[0]
heapq.heapreplace(A, A[0] + 1)
cost += abs(smallest)
return cost
class Solution:
# @param A : list of integers
# @param B : integer
# @return a list of integers
def dNums(self, A, B):
seen = {}
res = list()
ptrs = [None]*len(A)
for i in range(B):
seen[A[i]] = i
res.append(len(seen))
for i in range(B, len(A)):
if seen[A[i-B]]==i-B:
del seen[A[i-B]]
seen[A[i]] = i
res.append(len(seen))
return res
class Solution:
# @param A : integer
# @param B : list of integers
# @return an integer
def nchoc(self, A, B):
h = [-b for b in B]
heapify(h)
s = 0
for _ in range(A):
chocs = -heappop(h)
s = (s + chocs) % 1000000007
heappush(h, -(chocs // 2))
return s
for _ in range(B):
rtn = left_branch.pop()
node = rtn.right
while node:
left_branch.append(node)
node = node.left
return rtn.val
Burn a Tree
class Solution:
# @param A : root node of tree
# @param B : integer
# @return an integer
def solve(self, A, B):
def bottom_up(node, starting):
if not node: return 0, False # think 2 nodes total:
root -> initial
if node.val == starting: return 1, True # initial leaf; leaaf
always return 1
import sys
sys.setrecursionlimit(10**4) # as 2 <= number of nodes <= 10 ^ 5
self.time = 0
bottom_up(A, B) # A: root, B: initial leaf
return self.time
class Solution:
# @param A : root node of tree
# @return an integer
def maxDepth(self, A):
if not A:
return 0
return 1 + max(self.maxDepth(A.left), self.maxDepth(A.right))
class Solution:
# @param A : tuple of integers
# @return the root node in the tree
def sortedArrayToBST(self, A):
if len(A) == 0:
return None
mid = len(A)/2
root = TreeNode(A[mid])
root.left = self.sortedArrayToBST(A[:mid])
root.right = self.sortedArrayToBST(A[mid+1:])
return root
class Solution:
# @param A : root node of tree
# @return a list of list of integers
def verticalOrderTraversal(self, A):
if A == None:
return []
queue = [(A,0)]
ans = {} # dict x -> [values] for current level
# Iterate by level, so values are properly stacked.
while queue:
queue2 = []
for node, x in queue:
ans.setdefault(x,[]).append(node.val)
if node.left is not None:
queue2.append((node.left, x-1))
if node.right is not None:
queue2.append((node.right, x+1))
queue = queue2
if right:
return [root] + right
if left:
return [root] + left
return []
Diagnol traversal:
select a node and store its left child node and add go towards right leaf node
class Solution:
# @param A : root node of tree
# @return a list of integers
def solve(self, A):
res = []
roots = [A]
while len(roots)>0:
new_roots = []
for node in roots:
while node is not None:
new_roots.append(node.left)
res.append(node.val)
node = node.right
roots = new_roots
return res
class Solution:
# @param A : root node of tree
# @return a list of integers
def solve(self, A):
result = []
previous = [A]
while previous:
result.append(previous[-1].val)
current = []
for node in previous:
if node.left:
current.append(node.left)
if node.right:
current.append(node.right)
previous = current
return result