liyunrui

class Solution:
    """
    Problem Clarifcation:
        -There's duplicates in the given array
    Problem formulation
        -We need to return all possible unique permuluation. S
    
    Thought Process:
        -Greedy+Backtracking
        prev: the previous number we put it in the current index. The reason why we need prev variable is we need one more constraint to avoid duplicate result in our answer.

liyunrui

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        n = len(points)
        # edge case
        if n == 0:
            return 0
        ending_time, ans = float('-inf'), 0 # the earliest end time
        # sort the balloons by their end x-coordinate
        for i in sorted(points, key=lambda x: x[1]):
            start_time = i[0]

liyunrui

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    """
    root->left->right(pre-order)
    left->right->root(post-order)

liyunrui

class LRUCache:
    """
    把最近一次使用的放到ordercit的end端, 最後沒被使用的放在beginning端
    
    1.we need a hashmap to help us to find a key in O(1)
    2.each time when get and put method is invoked, we need doubly-linked-list to put the key into the end (latest data) and remove the data associated this key in O(1)
    """
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.od = collections.OrderedDict()

liyunrui

class MaxStack:
    """   
    push 1, 5
    tmp_stack = []
    stack = [5,1]
    max_stack = [5,5]
    
    這題多了一個pop max 是最難的地方
    tmp = stakc.pop() # 1
    tmp_max = max_stack.pop() # 5

liyunrui

class MinStack:
    """
    Problem Clarificaiton:
        Can I assumm all valid operations to similify code at the moment.

    In the end, ask any place that you want me to modify.
    All opeations can be done in O(1)
    Thought Process:
        We somehow need a way to ke track of a minimum--> Heap and Binary search tree
        

liyunrui

class Solution:   
    """
    Divide and Conquer:
    我們可以把我們要求的問題拆成不重複的子問題
        1.左邊subarray的最大連續合
        2.右邊subarray的最大連續合
        3.包含當前元素的的最大連續和
    用一個最小的例子[-2, 1]去展示你的idea
    [-2,1,-3,4,-1,2,1,-5,4]
      0 1. 2 3. 4 5. 6 7 8

liyunrui

class Solution:
    """
    1.有加號, 減號, 乘號, 除號!沒有括號
    2.All the integers in the expression are non-negative integers, which means there's no leading negative sign and no 3*-5
    10+3-2
          i
        
    3+5
     i
    1.遇到+/-號, 我們就可以parse下一個num, 然後根據sign把num放進stack

liyunrui

class Solution:
    """
    What's disibution of input string s?
    沒有乘號, 只有加號和減號!
    
    當只有加號和減號,沒有括號和乘號!
    1-1
      i
      num=1
      sign=-1

liyunrui

class Solution:
    """
    "2*(5+5*2)/3+(6/2+8)"
               i
    """
    def calculate(self, s: str) -> int:
        def cal_update(op, num, stack):
            if op == "+":
                stack.append(num)
            elif op == "-":