liyunrui

class Solution:
    """
    
    Thought Process: 
        1.prefix sum+get all pair i, j -> O(n^2)
    [4,5,0,-2,-3,1]
            i
     j j j  j
     
     

liyunrui

class Solution(object):
    """        
    Prfix sum+Hashmap
        公式推導:
        range(i,j) = range(0,j)-range(0,i) where j > i
        ->range(i,j)-k = range(0,j)-range(0,i)-k
        we're looking for range(i,j)-k == 0
        So, when we keep track of number of prefix sum in hashmap
        So, if range(0,j)-k in hashmap, number of range(i,j)-k ==0 is eqaul to number of range(0, i)

liyunrui

class Solution:
    """
    PQ:
        -Can I assume len(secret) == len(guess)? Yes
        -Contain digit only in the given string
    Thought Process:
        Two-passes:
            step1: count bulls is easy, just traverse two strings together, O(n). In the mean time, we keep track of frequenc of un-matched character in secrect, in order to use later.
            step2: count cows. just traverse guess, O(n). If currend index of secret != current guess and secret_cnt[g] > 0:
            cow+=1

liyunrui

class Solution:
    """
    PQ:
        -Can I assume there's only one starting point in the given grid ?
        -at most 6 keys in the given grid --> "abcdef"
        -There could be mutiple pathes to find all keys with same minimum step.
    Thought Process:
        -grid--> apprently, it's a graph problem.
        -Each cell is node in the graph
        -edge is 4 directions

liyunrui

class Solution:
    """
    BFS
        It's a shortest problem. So we think about bfs.
        Starting bfs on knight. During the bfs, we keep track of step we moved, when we meet target(x,y), we reach our goal by return step.
        
    BFS+Pruning(Symmetric Properties)
        All solutions below are based on symmetry, meaning (x, y), (-x, y), (x, -y), (-x, -y) will have the same results.

        Instead of search whole boards with 8 direction when level by level bfs. So, we can do some pruning.

liyunrui

class Solution:
    """
    
    Thought Process:
        grid coordinates/matrix --> It's definitely graph problem.
            -each cell(x,y) is node in the graph
            -it's directed graph, path exist only rooms[next_i][next_j] > rooms[i][j]
                (-1 is wall)
        Brute Force
            For each cell, we do dfs to find distance to shortest gate.

liyunrui

class Solution:
    """
    Thought Process: 
        grid coordinates --> It's definitely graph problem.
            -each cell(x,y) is node in the graph
            -it's directed edge, path exist only height of neighbor >= current of height(這裡很tricky, 周圍比較高, 所以水才可以留到current node)
                neighbor node -> current node
        
        DFS 
            Idea is we starting dfs on the border, exploring neighbor by neighbor. And, in the mean time, we use two hashset for two oceans to record if we can visited the ocean from the cell(x, y). For example,

liyunrui

class Solution:
    """
    Thought Porcess:
        stack:
            Idea is use a stack to maintain all the open Parentheses on the left side of s[i].
            And top of stack is closest open Parentheses
            
            We traverse the given string forward.
                when encounter the open parenthese, we append the index
                when encounter the close parenthese, 

liyunrui

class Solution:
    """
    Parathenses Problem --> stack + greedy
    Thought Process:
        Greedy+stack:
        We use stack to keep track of index of unmatched left parentheses.
        Top of stack is nearest index of unmatched left parenthese.
        
        We traverse the given string forward.
            when encounter the open parenthese, we append the index

liyunrui

class Solution:
    """
    So, may i know what will hapeen when a new asteroid is added on the right?
    Ask interview to provide more examples to discuss such as [-2,-1,1,2]
    Does return order matter?
    
    Thought Process:
        Brute Force/ Naive way:
            we iterate
        Stack: