疫情每天打卡写题

       
05/20
        • Critical connections in a network/Critical Routers
                ○ find bridges in the undirected graph,找这个无向图中除了环之外的那些connection, 对于每个点，如果他本身和自己的邻居点在一个环里的时候，那么通过
                   DFS他们最终都会被互相访问到，所以lowestRank可以说是一样的，进而我们需要将他们的lowestRank都统一为最小的那个
                ○ dfs: iterate all vertex in the graph, try to do dfs()
                ○ variable: discoverTime: the time when the node is visited first time
                              par: parent
                              lowestRank: default -1, store the min jump to achieve this vertex
                ○ case1: child == par                                                                          -> continue
                   case2: lowestRank[child] == -1: 邻居未被访问                        -> dfs, choose min
                   case3: lowestRank[cur] = min(lowestRank[cur], lowestRank[child])
                             if  lowestRank[cur] == discoverTime + 1 and cur != 0: ->add to the result
               
                ○ Time O(n), Space O(n)

        • Alien Dictionary
                ○ directed graph + topological sorting
                ○ Use two hashmaps to create a graph: parent
                                                                                child
                for each two consecutive words, find the first different char and generate edges
                Then start with the vertex with no par, add it to the list
                ○ Two invalid cases:     when build graph   ->   len(word1) > len(word2) and  word1[:len(word2)] == word2
                                                   end                           ->    still vertex left in parent dictionary, these vertex are on the same level

                ○ Time O(n + alpha + V + E) -> n + alpha time to build graph
                                                  -> V + E == n + alpha topological sorting
                   Space O(V + E)

        • Kth smallest elements in Binary Search Tree
                ○ One property of BST is that left node val smaller than the right node val, therefore 1st we need to trace back down to the end of the left of the
                   tree. And then trace back, and update to k-1 for each step. Return root.val once K==1
                ○ Using stack to store the node, when we go down to the bottom of the left part of the tree
                ○ Time O(n), Space O(n)

        • Find K Pairs with Smallest Sums (sorted)
                ○ min_heap: store the sum and index
                            set(): store the used pairs
                ○ Increment value in index array for the element that forms next minimum value pair
                ○ pop_heap to get current smallest sum and along with the indices of the element that make up the sum.
                            repeat till k == 0 or no heap
                ○ Time O(nlog(n)), Space O(n)

05/21

        • Longest Bitonic Sequence
                ○ monopoly increase or decrease sequence also consider as Bitonic sequence
                ○ Two Dp: dp1[i] -> the longest increasing subsequence ending with array[i], i -> 1 to n - 1
                            dp2[i] -> the longest decreasing subsequence ending with array[i], i -> n - 2 to 0
                            dp1[i] + dp2[i] -1                                                                                          i -> 0 to n - 1
                            initial max = dp1[0] + dp2[0] -1 -> monopoly increase or decrease array
                ○ Time O(n), Space O(n)

        • Largest square of 1's in a binary matrix
                ○ M[i][j] represents using (i, j) as the bottom-right corner, the largest edge length
                ○ M[i][j] = 0                                                              if A[i][j] == 0
                   min(M[i - 1][j - 1], M[I - 1][j], M[i][j - 1] ) + 1        if A[i][j] == 1
                ○ keep a largest_count
                   Time O(n^2)       Space O(n^2) -> O(n)

        • Count Square Submatrices with All Ones
                ○ M[i][j] represents using (i, j) as the bottom-right corner, the largest edge length
                if M[i][j] == 3: use (i, j) can construct size of 1 square to size of 3 square, therefore we only need to keep a total and add each M[i][j] to get the ans
                Time O(n^2) Space O(n^2) -> O(n)

        • Given a bunch of matches, try to find the largest square
                        • 火柴节点看做点, 每个节点记录左边和下边两条边
                        • M1[i][j] 记录以matrix[i][j]为左边点向右延伸的最长边, 从右往左
                        • M2[i][j] 记录以matrix[i][j]为顶点向下延伸的最长边，从下往上
                        • M3[i][j] 记录以matrix[i][j]为左上顶点可以组成的最大正方形
                                □ for length in range(min(M1[i][j], M2[i][j])) -> 判断右边边长和下面边长是否>= length
                          Time O(n^2) Space O(n^2)

        • Largest Square Of 1s - Q4
                ○ for (i, j) enumerate the top left corner
                        for size // 边长可以小优化, 从(m - i, n -j)最小值开始
                                run 4 for loops to check whether each side is all one
                   preprocessing: Compute M1, M2, M3, M4 /improve只要找往右看和往下看
                 ○  Time O(n^2) Space O(n^2)

05/23


• Interval List intersections
        ○ i, j indicates current interval index to compare
        ○ for each pair, 找交集一开始的位置和结束的位置, 如果非空则加入res
        更新i，j -> If A[i][1] < B[j][1] (A在前)     ->    i+=1
        ○ Time O(n), Space O(1)

• Merge Intervals
        ○ 1st sort + stack
        ○ compare the current right bound with the left bound of the top element in stack:
                § if cur_right <= prev_left: update prev_left with the max cur_left and prev_left
                § else: append to the res
        ○ Time O(nlog(n) + n), Space O(1)
       
• Insert intervals
        ○ Sol1 Add node + sort + stack
                § compare the current right bound with the left bound of the top element in stack
                § Time O(n log(n) + n), Space O(1)
        ○ Sol2 res to store the pair with correct order
                § 3 cases:
                        § No-overlapping: newInterval < curr      ->   newInterval.end < curr.start
                        § No-overlapping: newInterval > curr      ->   curr.end              < newInterval.start
                        § Overlapping:                                            ->   update newInterval with min start and max end
                § Time O(n), Space O(1)

05/24
        • Sorted Array to binary search Tree (height balanced BST)
                ○ recursive
                ○ mid = len(num) // 2  ->  root node for each subtree
                left of mid are left subtree nodes and right of mid are right subtree nodes
                ○ Time O(n), Space O(h)
       
        • Sorted List to binary search Tree (height balanced BST)
                ○ recursive
                ○ 3 cases:
                        if not head: return None
                        if not head.next: return TreeNode(head.val)
                        find the prev node of the mid node by adding dummy head and slow/fast pointers
                        then setting mid mode as root, and break the left part (left subtree) with the right part (right subtree not include root)
                   Time O(n) Space O(logn)
        • Greatest Common factor
                ○ Sol1:
                        start with small number and go through all possible facotor
                        Time O(n), Space O(1)
                ○ Sol2: The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.
                        gcd(a, b) == gcd(b, a % b)   with   a > b
                       
        • Palindrome Number
                ○ Sol1: reverse the number first than check if is equal
                            Time O(length(str(num))) Space O(1)
                            might overflow
                ○ Sol2: find the largest power of 10 which is smaller then x first. Then check if left most digit is equal to right most digit and so on.
                             x // b != x % 10         -> compare the most right digit with the left most digit
                    Time O(length(str(num))//2) Space O(1)

05/26
• Contiguous Array
        ○ dictionary: key: sum include i index number,    val: i
        ○ treat 0 as -1, then if we got the same sum, we will have contiguous subarray with equal number of 0 and 1
        ○ initial : dic = { 0: -1}
        ○ Time O(n), Space O(n)

• Continuous Subarray Sum
        ○ Hashmap: key: sum(nums[:i] % k), val:i
        ○ If sum(nums[i:j] % k == 0, then sum(nums:j) % k == sum(nums[:i]) % k)
                § d = b - a
                d % k == 0    ->      (b - a) % k == 0
                                      ->               b % k == a % k
        If k == 0, then become contiguous array prob
        ○ Time O(n), Space O(n)

• Shortest Length to Sorted Array
        ○ Sol1: Sorted + compare
                § sorted the array and determine the left and right elements which mismatch
                § Time O(nlogn), Space O(n)
        ○ Sol2:
                § determine the correct position of min and max element in unsorted subarray
                        § search from left to right  -> find 1st num i > right
                        search from right to left  -> find 1st num j < left
                        -> got a sub array which must unsorted
                        Then find min, max between this range => here i might be larger than j
                        § from 0 to i - 1, check 1st num > min  ->   right bound of the unsorted subarray
                        from j + 1 to n, check 1st num < max  ->  left bound
                        § Corner case: len(nums) == 1 and sorted array
                        Time O(n), Space O(1)

05/25
昨天写了忘贴了

        • Uncrossed Lines
                ○ DP
                ○ dp[i][j] -> the number of uncrossed connected line before and include A[i], B[j]
                ○ 2 cases: A[i] == B[j]  -> dp[i][j] == dp[i - 1][j - 1] + 1
                             A[i]  != B[j]   -> dp[i][j] == max(dp[i][j - 1], dp[i - 1][j])
                ○ Time O(mn), Space O(mn) -> O(n)
                       
        • Unique binary search tree
                ○ DP + Catalan number
                ○ Logic:
                        • F(n) the number of unique BSTs containing 1,...,n
                        pick any root from 1 to n:
                                then left subtree contain 1…i - 1            -> number of possible left subtree F(i -1 )
                                right subtree contain nodes i + 1 …n     -> number of possible left subtree F(n - i )
                                total = F(i- 1) + F(n - i)
                        • dp[x]  =>  choose x as root, how many unique binary search tree can be generated
                                § for j in range(i):
                                        dp[i] += dp[j] * dp[i - j - 1]
                ○ Time O(n^2) Space O(n^2)  -> O(n)

        • Unique binary search tree II
                ○ Recursive
                ○ recursively split the array to [1,…n]. During ever split, make a new root node for every different combination
                of left/right subtree structures
                Use l, r to give the range of current possible root val
                for I in range(l,r):
                        for lc in self.generage(l, i) or [None]:      =>    [None]: there might be not left/right subtree
                                for rc in self.generage(i + 1, r):
                ○ Time O(n ^2)

        • Decode Ways
                ○ Recursive
                        • each level choose 1 or 2 num to decode
                        • go through all combination
                        • Time O(n^2)
                ○ DP
                        • dp[i] how many ways to encode include i index element
                                § if s[i-1: i] in 1 to 9     -> dp[i] += dp[i - 1]
                                § if s[i-2: i] in 10 to 26 -> dp[i] += dp[i - 2]
                                § core case dp[0] = 1, dp[1] = 0 if s[0] == "0" else 1
                        • Time O(n), Space O(n)

        • Number of Ways of Decode
                ○ DP
                        • dp[i] how many ways to encode include I index number
                                § multi-cases -> consider about the cur num and prev num
                        • Time O(n), Space O(n)

05/27

         • Bipartite
                ○ a colored node should have ALL connected neighbors in different colors.
                ○ DFS & recursive
                        § 用一个dict存已经遍历过的点和他标记过的颜色
                        § 从一个点开始做DFS，从这个点开始的一条路径上所有点满足要求才走另一条路。同时需要存一个visited，避免重复遍历
                ○ BFS & priority queue
                        § 用一个dict存已经遍历过的点和他标记过的颜色
                          从一个点开始做BFS，这个点的所有neighbor和它颜色不一样再看他的neighbor是否满足。同时需要存一个visited，避免重复遍历
        • Depth of Forest
                ○ undirect graph + Breadth-First Search
                ○ use hashmap to create a undirect graph: key -> parent node,   val -> child node list
                        • go through each node in graph key list, use queue to check the level
                        • for each node, make a visited variable to check cycle
                ○ Time O(V+E), Space (V+E)

        • Longest Ascending Path in Matrix
                ○ Sol1: Breadth-Frist Search implemented Topological sort
                        • build directed graph: each cell is node and directed edge from node x to node y if x < y
                                □ queue      -> push node with no number of node larger than it self; initialize with smallest node in each path
                                □ indegree  -> current level, how many node larger than it
                        • Time O(V+E) Space O(V+ E)
                ○ Sol2: dp + recursive
                        • dp[i][j] -> start from i, j the longest increasing path we can get
                        • for each cell check the four cells around it
                                        dp[i][j] = 1 + max(self.check(i - 1, j) if i - 1 >= 0 else 0,
                                                                        ….                                             )
                   Time O(mn) Space O(mn)

05/28
        • Game of Life
                ○ go through all the matrix and replace the cell with the number of neighbors == 1
                ○ if cell == 2 -> flip to 1
                if cell >=  3 -> flip to 0
                ○ Time O(mn), Space O(1)

        • Fraction to Recurring Decimal
                ○  divmod(x, y)   calculates both x / y and x % y and returns both the values

        • Flatten Nested List Iterator
                ○ Sol1 recursive  to flatten the whole iterator on the constructor
                        § using deque to store the flatten result
                        § Time O(n) Space O(n)
                ○ Sol2 using stack to flatten the list as you go
                        § reverse the list to the stack
                        § if not self.stack[-1].isInteger() -> append reverse list self.stack[-1] to the stack
                                                                     this action should be done in the hasNext function      (e.g. [[]]  ->  no integer after expend the nestList)
                        § e.g   [[1, 2], 3, [4, 5]]  ->  [[4, 5], 3, [1, 2]]
                                                      ->  [[4, 5], 3,   2, 1 ]
                                                      ->  [  5,  4, 3,   2, 1 ]
                        § Time O(n), Space O(n)
        • Count Bits
                ○ Sol1 : for each integer we count 1 in its' bit operation
                ○ Sol2: dp
                        if num is power of 2, then only one 1 in its' bit representation
                        start from the power of 2, the increase of 1 in its' bit operation is similar to the previous
                        j = 0
                        for i in range(n):
                                dp[i] = dp[j] + 1
                                j += 1
                                if i + 1 = power_two:
                                        j = 0
               
               
        • Counting bits
                ○ Sol1
                        § for each num count how many 1 in the bits version
                        do i >> j & 1
                        § Time O(n*k) k-> number of bits used to represent a number
                ○ Sol2 dp + pattern
                        § dp[i] = dp[i // 2] + 1  ->    if i is odd
                                 = dp[i // 2]         ->    if i is even
                    Time O(n), Space O(n)

05/29
今天出门买菜，休息一下~

• Integer to Roman
        ○ use two array to map number to the Roman:
        increment res string by go through the whole array
        be careful with case such as 9 - "IX"
        • Or recursive
        • Time O(n), Space O(12) -> 12 Roman numerals  
• Roman to Integer
        • dictionary to map Roman to number
        • from right to left, if right > left  ->  need to minus left number ;
                                if right < left  ->  add right number;
           Time O(n)

05/31

        • Maximum Product of Two Elements in an array
                ○ store 4 variables, max1, max2, min1, min2
                ○ the final answer could be max1 * max2 or min1 * min2 (two negative number)
                ○ go through the array and update these four variables, then compare the result in the end
                   Time O(n), Space O(1)
        • Edit Distance
                ○ Sol1 recursion:
                        min(replace/delete/insert )
                        从最后一个开始对比，终止条件i ==0 or j == 0
                        Time O(3^(m + n))
                       
                ○ Sol2 DP:
                        ○ M[i][j] represents the min edit distance from s1[0 … i - 1] to s2[0 … j - 1]
                        ○ core case: if not S1 OR not S2
                        ○ initial: M[0][0] = 0, M[0][j] = j, M[i][0] = i
                        ○ if  == :
                                M[i][j] = M[i - 1][j - 1]
                        else:
                                replace:  = M[i - 1][j - 1] + 1
                                delete对于i:      = M[i - 1][j] + 1
                                insert对于i:       = M[i][j - 1] + 1
                                M[i][j] = min (r, d, i)
                 Time complexity : O(mn), Space O(mn) -> O(m)

        • Maximum Product of Numbers (3 num)
                ○ 用max_heap和min_heap 找到最大的三个数和最小的两个数
                ○ res =  max( max1 * max2 * max3,  min1 * min2 * max1) 
                        max1 -> largest number
                        max2 -> second largest number
                   Time O(nlog3)
        • Reorder Routes to Make All Paths Lead to the City Zero
                ○ Sol1: Bfs
                        • Build to hashmap to store connections between the cities; visited set() to store cities be visited
                        • start from the neighbor of 0, only count if need to reverse the link
                        • then start from these neighbors, repeat step2
                        • Time O(V+E), Space O(V+E)
                ○ Sol2: DFS
                        • run dfs starting from city 0, using neighboring cities rather than connections
                        • count the total number of outgoing edges that we visit
                        • need to store the cities be visited and the edges be visited
                   Time O(V + E), Space O(V + E)