Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Input: [1, 2, 3, null, 5, null, 4] Output: [1, 3, 4]
# Definition fora binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None
class Solution: def rightSideView(self, root: TreeNode) -> List[int]: if not root: return [] right = self.rightSideView(root.right) left = self.rightSideView(root.left) return [root.val] + right + left[len(right):]
# Solution 1: Recursive, combine rightand left:5 lines, 56 ms # Compute the rightview of both rightandleftleft subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.
class Solution2: def rightSideView(self, root): def collect(node, depth): if node: if depth == len(view): view.append(node.val) collect(node.right, depth+1) collect(node.left, depth+1) view = [] collect(root, 0) returnview
# Solution 2: Recursive, first come first serve: 9 lines, 48 ms # DFS-traverse the tree right-to-left, addvaluesto the view whenever we first reach anew record depth. This is O(n).
class Solution3: def rightSideView(self, root): view = [] if root: level = [root] while level: view += level[-1].val, level = [kid for node in level for kid in (node.left, node.right) if kid] returnview
# Solution 3: Iterative, level-by-level:7 lines, 48 ms # Traverse the tree level by level andadd the last value of each level to the view. This is O(n).
Solution 1: Recursive, combine right and left:
5 lines, 56 ms Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.
Solution 1: Recursive, combine right and left:
5 lines, 56 ms Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.
Solution 3: Iterative, level-by-level:
7 lines, 48 ms Traverse the tree level by level and add the last value of each level to the view. This is O(n).
Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a list – whose elements may also be integers or other lists.
# """ # This is the interface that allows for creating nested lists. # You should not implement it, or speculate about its implementation # """ #class NestedInteger: # def isInteger(self) -> bool: # """ # @return True if this NestedInteger holds a single integer, rather than a nested list. # """ # # def getInteger(self) -> int: # """ # @return the single integer that this NestedInteger holds, if it holds a single integer # Return None if this NestedInteger holds a nested list # """ # # def getList(self) -> [NestedInteger]: # """ # @return the nested list that this NestedInteger holds, if it holds a nested list # Return None if this NestedInteger holds a single integer # """
defflatten(self, ls): res = [] for item inls: if item.isInteger(): res.append(item.getInteger()) else: res.extend(self.flatten(item.getList())) return res
defnext(self) -> int: returnself.ls.pop()
defhasNext(self) -> bool: return len(self.ls) > 0
# Your NestedIterator object will be instantiated and called as such: # i, v = NestedIterator(nestedList), [] # while i.hasNext(): v.append(i.next())
EQ-3 *
A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B). The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
classSolution: defgetSkyline(self, buildings: List[List[int]]) -> List[List[int]]: from heapq import heappush, heappop events = [(l, -h, r) for l, r, h in buildings] events += list({(r, 0, 0) for _, r, _ in buildings}) events.sort() res = [[0, 0]] live = [(0, float('inf'))] for l, negH, r in events: if negH: heappush(live, (negH, r)) while live[0][1] <= l: heappop(live) if res[-1][1] != -live[0][0]: res += [[l, -live[0][0]]] return res[1:]
classSolution_dcq: defgetSkyline(self, buildings: 'List[List[int]]') -> 'List[List[int]]': """ Divide-and-conquer algorithm to solve skyline problem, which is similar with the merge sort algorithm. """ n = len(buildings) # The base cases if n == 0: return [] if n == 1: x_start, x_end, y = buildings[0] return [[x_start, y], [x_end, 0]]
# If there is more than one building, # recursively divide the input into two subproblems. left_skyline = self.getSkyline(buildings[: n // 2]) right_skyline = self.getSkyline(buildings[n // 2 :])
# Merge the results of subproblem together. return self.merge_skylines(left_skyline, right_skyline)
defmerge_skylines(self, left, right): """ Merge two skylines together. """ defupdate_output(x, y): """ Update the final output with the new element. """ # if skyline change is not vertical - # add the new point ifnot output or output[-1][0] != x: output.append([x, y]) # if skyline change is vertical - # update the last point else: output[-1][1] = y
defappend_skyline(p, lst, n, y, curr_y): """ Append the rest of the skyline elements with indice (p, n) to the final output. """ while p < n: x, y = lst[p] p += 1 if curr_y != y: update_output(x, y) curr_y = y
# while we're in the region where both skylines are present while p_l < n_l and p_r < n_r: point_l, point_r = left[p_l], right[p_r] # pick up the smallest x if point_l[0] < point_r[0]: x, left_y = point_l p_l += 1 else: x, right_y = point_r p_r += 1 # max height (i.e. y) between both skylines max_y = max(left_y, right_y) # if there is a skyline change if curr_y != max_y: update_output(x, max_y) curr_y = max_y
# there is only left skyline append_skyline(p_l, left, n_l, left_y, curr_y)
# there is only right skyline append_skyline(p_r, right, n_r, right_y, curr_y)
return output
EQ-4
Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list – whose elements may also be integers or other lists. Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.
# 364. Nested List Weight Sum II # """ # This is the interface that allows for creating nested lists. # You should not implement it, or speculate about its implementation # """ #class NestedInteger: # def __init__(self, value=None): # """ # If value is not specified, initializes an empty list. # Otherwise initializes a single integer equal to value. # """ # # def isInteger(self): # """ # @return True if this NestedInteger holds a single integer, rather than a nested list. # :rtype bool # """ # # def add(self, elem): # """ # Set this NestedInteger to hold a nested list and adds a nested integer elem to it. # :rtype void # """ # # def setInteger(self, value): # """ # Set this NestedInteger to hold a single integer equal to value. # :rtype void # """ # # def getInteger(self): # """ # @return the single integer that this NestedInteger holds, if it holds a single integer # Return None if this NestedInteger holds a nested list # :rtype int # """ # # def getList(self): # """ # @return the nested list that this NestedInteger holds, if it holds a nested list # Return None if this NestedInteger holds a single integer # :rtype List[NestedInteger] # """
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. Example: Given this linked list: 1->2->3->4->5 For k = 2, should return: 2->1->4->3->5 For k = 3, should return: 3->2->1->4->5
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None
class Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: newhead = head for i in range(k): if newhead == None: # if not newhead: return head newhead = newhead.next
connect = cur = head prev = None for i in range(k): cur.next, cur, prev = prev, cur.next, cur connect.next = self.reverseKGroup(newhead, k)
returnprev
# Use a dummy head, and # l, r : define reversing range # pre, cur : used in reversing, standard reverse linked linked list method #jump : used to connect last node in previousk-group tofirst node in following k-group
class Solution1: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: dummy = jump = ListNode(0) dummy.next = l = r = head
while True: count = 0 while r andcount < k: # use r to locate the range r = r.next count += 1 ifcount == k: # if size k satisfied, reverse the inner linked list pre, cur = r, l for _ in range(k): cur.next, cur, pre = pre, cur.next, cur # standard reversing jump.next, jump, l = pre, l, r # connect two k-groups else: return dummy.next
EQ-6
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
For 1-byte character, the first bit is a 0, followed by its unicode code.
For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
class Solution: defvalidUtf8(self,data:List[int])->bool: # 1B min = 0, max 127 # 2B min = 192, max 223 # 3B min = 224, max 239 # 4B min = 240, max 247 # FB min = 128, max 191
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle. You need to return the least number of intervals the CPU will take to finish all the given tasks.
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( andclosingparentheses ), the plus + or minus sign -, non-negative integers and empty spaces . classSolution1: def leastInterval(self, tasks: List[str], n: int) -> int: max_freq = 0 num_task_max_freq = 0 all_freq = collections.Counter(tasks)
for letter, freq in all_freq.items(): if max_freq == freq: num_task_max_freq += 1 elif max_freq < freq: max_freq = freq num_task_max_freq = 1
Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
class Solution: def calculate(self, s: str) -> int: operand, sign, res = 0, 1, 0 stack = []
for ch in s: if ch.isdigit(): operand = 10*operand + int(ch) elif ch in "+-": res += sign * operand sign = 1if ch == "+"else -1 operand = 0 elif ch == "(": stack.append(res) stack.append(sign) res, sign = 0, 1 elif ch == ")": res += operand * sign operand = res sign = stack.pop() res = stack.pop() returnres + sign*operand
class Solution1_explain: def calculate(self, s: str) -> int:
stack = [] operand = 0 res = 0 # For the on-going result sign = 1 # 1 means positive, -1 means negative
for ch in s: if ch.isdigit():
# Forming operand, since it could be more than one digit operand = (operand * 10) + int(ch)
elif ch == '+':
# Evaluate the expression to the left, # with result, sign, operand res += sign * operand
# Save the recently encountered '+'sign sign = 1
# Reset operand operand = 0
elif ch == '-':
res += sign * operand sign = -1 operand = 0
elif ch == '(':
# Push the result andsignonto the stack, forlater # We push the result first, then sign stack.append(res) stack.append(sign)
# Reset operand and result, asifnew evaluation begins for the new sub-expression sign = 1 res = 0
elif ch == ')':
# Evaluate the expression to the left # with result, signand operand res += sign * operand
# ')'marks end of expression within aset of parenthesis # Its result is multiplied with signon top of stack # as stack.pop() is the sign before the parenthesis res *= stack.pop() # stack pop1, sign
# Then addto the next operand on the top. # as stack.pop() is the result calculated before this parenthesis # (operand on stack) + (signon stack * (result from parenthesis)) res += stack.pop() # stack pop2, operand
# Reset the operand operand = 0
returnres + sign * operand
EQ-9
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
class Solution: def longestValidParentheses(self, s): dp = [0]*(len(s) + 1) stack = [] for i in range(len(s)): if s[i] == '(': stack.append(i) else: if stack: p = stack.pop() dp[i + 1] = dp[p] + i + 1 - p returnmax(dp)
class Solution1: def longestValidParentheses(self, s: str) -> int: returnmax(self.helper(s,'('), self.helper(s[::-1],')'))
def helper(self, s, left): ans = 0 maxendinghere = 0 count = 0 forc in s: ifc == left: #when scan s from lefttoright, leftis'(', otherwise is')' count += 1 maxendinghere += 1 else: count -= 1 ifcount <0: maxendinghere = 0 count = 0 else: maxendinghere += 1 ifcount == 0: ans = max(ans, maxendinghere) return ans
EQ-10
Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None
class Solution: def isValidBST(self, root: TreeNode) -> bool: stack = [] current = root last_num = float('-inf') while stack or current: while current: stack.append(current) current = current.left
current = stack.pop() if last_num >= current.val: return False last_num = current.val current = current.right return True
class Solution1: # def isValidBST(self, root: TreeNode) -> bool: def isValidBST(self, root, lessThan = float('inf'), largerThan = float('-inf')): if not root: return True if root.val <= largerThan or root.val >= lessThan: return False return self.isValidBST(root.left, min(lessThan, root.val), largerThan) and \ self.isValidBST(root.right, lessThan, max(root.val, largerThan))Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.