Diffculty: Medium

227. Basic Calculator II

Topic: String

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1
Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

Approach1

my

def calculate(self, s: str) -> int:
    # 初始化sign为 “+”，是因为开头是数字
    num ,stack ,sign = 0 , [] , '+'
    for i in range(len(s)):
        ch = s[i]
        if ch.isdigit():
            num = num * 10 + int(ch)  # 针对多位数
        #根据当前数字之前的符号，来决定如何处理当前数值
        # 并将处理后的数值压入栈中
        if ch in "+-*/" or i == len(s)-1:
            if sign == "+" :
                stack.append(num)
            elif sign == "-" :
                stack.append(-num)
            elif sign == "*":
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop()/num))
            num = 0
            sign = ch
    return sum(stack)

Approach2

230. Kth Smallest Element in a BST

Topic: Tree, Binary Search

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

Follow up:

• What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Approach1

中序遍历

def kthSmallest(root: TreeNode, k: int) -> int:
    def help(root,res):
        if root == None:
            return res
        help(root.left, res)
        res.append(root.val)
        help(root.right, res)
    res = []
    help(root, res)
    print(res)
    return res[k-1]

# =====================
def kthSmallest(root: TreeNode, k: int) -> int:
    def helper(node):
        if not node:
            return []
        return helper(node.left)+[node.val]+helper(node.right)
    
    return helper(root)[k-1]

Approach2

236. Lowest Common Ancestor of a Binary Tree

Topic: Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition. 

Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the binary tree.

Approach1

Approach2

238. Product of Array Except Self

Topic: Array

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Approach1

Approach2