疫情每天打卡写题

06/14
这两天在写一个data challenge；没怎么刷题
                       
• Cheapest Flight Within K stops
        ○ Sol1 Backtrack/recursive
                • build a graph and then check all the route start from start city to the dst.
                • base case: flight cost > self.res, stops > k, or stops < k and src == dst
                        k level represents, the city we can arrive whith in k-1 stops
                        for each level, we can choose whether we want to fight to the city we can arrive (check duplication)
                • Time O(E*V), Space O(E*V)
        ○ Sol2 BFS + Queue
                • use queue to store the stops and total cost to reach this stops
                • start from the src and visit adjacent stop in bfs way,
                        □ stop < k + 1
                        □ check cur == dst
                • try all the direct stop from the source till terminate the loop
• String replace
                ○ transform into list, then replace it by check each index to find s, using a point which pointer to the end of list we will return.
                ○ two case, if S > T, replace on the orignial list and move the pointer
        if  S < T, first check how many S need to be replace and add the extra space to the list, and check it from the right to the left

06/15
今天复习了tree的题目，每一题用recursive和iterative写一遍
        • Reverse a binary tree upside down
                ○ 对于一个根节点来说，目标是将其左子节点变为根节点，
                                                右子节点变为左子节点，
                                                原根节点变为右子节点，
                                                没有左子节点或没有节点，直接返回
                ○ recursive: new_node = self.reverse(root.left) -> then reverse
                ○ iterative: for each iteration,
                        • Store the next root, the left child of the current node.
                        • Flip. Left point the current node to the right subtree on the last level, and right point the current node to its parent.
                        • Update the previous, the current and the last right node for next iteration.
                   Time O(h)     

        • Delete In Binary Search Tree
                ○ recursive
                ○ 4 cases:   not root:          ->   None
                             root  <   target   ->   root.right = self.delete(root.right)
                              root   >   target   ->   root.left = self.delete(root.left)
                              root  ==  target:  if only have one subtree, return that half
                                                    else replace the root with the most left node of the right subtree
                ○ Time O(h + h), Space O(h)
        • Insert In Binary Search Tree
                ○ insert as a left node
                ○ Sol1 iterative
                ○ Sol2 recursive
                        § if not root: return the InsertNode
                        § if root.val > val: search for the left substree
                        § if root.val < val: search for the right substree
                ○ Time O(h)

06/16
        • Least Insertions To Form a Palindrome
                ○ dp[i][j] represent the minimum insert to form a palindrome from i to j
                        • base case: only one letter, dp[i][j] = 0
                        • induction rule:
                                □ if word[i] == word[j]: dp[i][j] = dp[i + 1][j - 1]
                                □ else: dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
                                □ for j in range(n): for i in range(j - 1, -1, -1)
                ○ Time O(n*(1 + 2 +..n)),  Space O(n^2)

        • Form A Ring With Words (an array of word to concatenated to form a ring)
                ○ DFS + recursive
                        • each level represents add one more word to form a ring
                        • for each level, we can choose the left valid word to form a ring (swap the used word to the left)
                                □ check start char of cur word == end char of the last word
                                □ once used all the word, we check the last word can connect to the first word
                    Time O(n!)
               
        • Restore IP Address
                ○ Recursive
                        • For each level, we choose to add 1 to 3 valid char in to current path
                                □ cur num <= 255, if add 2 or more char, the first one can't be "0"
                        • Stop till we already got three separate part on the path; count by dots number
                ○ Time O(3^4)?

        • Valid IP Address
                ○ check each chunk is valid or not

06/17

        • Next Permutation
                 ○ search for the first num < left num -> swap this number get larger one; number in descending order
                        then find the last ascending position
                        reverse the second part  
                    Time O(n)
       
        •  Surrounded Regions
                ○ flip all node connected with the "O" on the board line to "1"
                        § initial: add "O" on the board line on the stack
                        § flip node directly connnect to the nodes in the stack to "1" and add new node to the stack
                        § After that filp all the "1" to "O", else to "X"
                ○ Time O(n^2), Space O(1)
        •  number of island I
        •  number of island II
        •  Kth Closest Point To original : heap

06/20

        • Palindrome Permutation
                if odd number > 2 -> False


        • Permutation Sequence
                ○ Sol1 DFS + recrusive
                        • list all permutations and count k
                        • be careful with permutations order, can't use swap, eg. 321 should be generated after 312
                                                                        w Need to use s store the current str, rest store the left str
                        • improve time complexity:
                                □ if self.k > math.factorial(len(res) - 1): continue
                        • Time O(n)
                ○ Sol2 Math
                        •  use a loop to check the region that the sequence number falls in and get the starting digit
                        • then we adjust the sequence number and continue. (can not swap, delect handled number)
                                □ k -= 1 -> the first permutation is itself
                                □ index, k = divmode(k, math.factorial(n)),       index -> the index of the digit need to add to permutation
                        • Time O(n)
                              

        • Print all permutations of a string (with duplicate letters)
                ○ use hashset for deduplication:
                        If use only one HashSet in the main function     Space O(n!)
                        Defined at each call - stack level           Space O(n^2)
                ○ Sol1 recursive String + Reorder O(n^2)
                ○ Sol2 recursive list + Swap O(n!)

06/22

        • Missing number (unsorted)
                ○ Sol 1:
                        § sum of first n numbers  = n * (n + 1)//2 
                        § missing number = sum - array_sum
                        § Time O(n), Space O(1) -> Overflow
                ○ Sol2:
                        § Xor
                        § assume a1 ^ a2 ^ a3 …a_n = A;  a1 ^ a2 ^ a3 …a_n-1 = B => A^ B = a_n
                        § two variables, one update with ^index, one update by ^ array[index]
                        § Time O(n), Space O(1)
               
        • Single Number II / Single Number
                ○ Sol1:
                        § count appearance of 1 for all 32 bit
                        § if number exists 3 times, the counts of 1 for each bits will be 0 or 3
                                • go through 32 bit,
                                        ® count all appearance of 1 on position i with num & (1 << i) == 1(1 << i)
                                        ® evlaute the counts modulo 3, if left 1 means the unique number have 1 on position I
                                        single |= (count % 3) << i
                                        ® Finally, deal with the overflow in python: maximum value for int32 is 2^31 -1, so number more than that will be negative ->  single - (1 << 31)
                        Time O(32n)

                ○ Sol2:
                        one: 每个bit表示这个位置上出现的1
                        two: 每个bit表示这个位置上是否出现了两个1,
                        如果相同位置上one和two的bit都是1, 说明这个位置上1出现了3次，那么将1从这两个里面同时移除(two 位置上为1，one必定为1)
                        § x1, x2, mask
                        x2 ^= (x1 & i ) -> i的所有位置上的1是否同时出现在x1中, 如果是的话说明1在这个位置1起码出现了两次, 更新到x2
                        x1 ^= i                    -> 更新i的所有位置上的1到x1上, 如果已经出现过1, 还是1,如果未出现更新成1
                        mask = ~(x1 & x2) -> 找出相同位置上的x1和x2都为1的取反, 剩下的是只出现了一次1的位置
                        x2 &= mask
                        x1 &= mask           -> 保留x1, x2里面只有x1为1的1
                        Time O(n)
                ○ 两种方法用的是相同思路，可以延伸至 K repeats, 第一个取模换成k
                                                                                        第二个k-1个variable表示这个位置的1出现了几次，if k-1 to 1 all have 1, then exclude all of them
                                                                               
        • Single Number III
                ○ Sol1:
                        § dictionary
                        § Time O(N), Space O(1)
                ○ Sol2: Bit operation
                        § get x = a ^ b by XOR all element in the array
                        § the 1 bit in x means a and b have different bit in that position, depends on these we can separate all the numbers into two buckets
                                □ find the most right 1 bit in x (or any one of 1 bit in x) by x & - x
                                □ bucket one has number have 1 bit in that position;
                                bucket two has number have 0 bit in that position;
                                Then since all other numbers appear twice, therefore the left in each bucket by XOR is the unique number
                        § Time O(N), Space O(1)

        • Binary Number with Alternating Bits
                ○ prev = n & 1 find the last digit is 0 or 1
                ○ then move bit to the right by n <<= 1, and check the current last digit XOR with prev
                        § cur = n & 1
                        § if cur == prev: False
                        else: prev = cur
                   Time O(32)

06/24


• Least Moves To Asceding Array
        ○ 1st Find: to move two unsorted (desc) nums need 1 = 2 - 1 swap, if three (desc) need 2 = 3 - 1 swap
                        if one nums in the right (asc) position, no need to move it
        ○ smallest swap = unsorted number - cycle number (cycle means if these number in wrong position but their index cover the sorted array indexes)
                • store a sorted array and may the index with val
                • create array to flag visited element,
for each element in the original array, assume it in the right place, then check whether the element in the sorted array with the same index be visited, if not then replace it with the element we currently check

                       
        • 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)
                       
       • Longest Substring With K Typed Characters
                ○ Sliding Window + dictionary
                ○ l and r to represent current sliding window, dic store the number of each char in this sliding window
                        § when move r and add char, check len(dic)
                                □ if len(dic) == k: check res
                                □ if len(dic)   >  k: move l until one char in dic == 0
                  Time O(n) Space O(n)

06/26

• Find the Duplicate Number
        ○ Sol1: set() then compare different sum/count
                § Time O(n), Space O(n)
        ○ Sol2: sort
                § Time O(nlogn), Space O(nlogn)
        ○ Sol3:看成cycle linked list 找连接点
                § the value of the cell will lead us to next point, f move 2 faster than s to find the connect point
                § let s point back to the first cell, and once s and f meet again, find the duplicate num
           Time O(n), Space O(1)
• Shortest Word I/ Shortest Word II
                ○ use dictionary to store all the index
                ○ then compare each of them
                ○ Time O(n), Space O(n)
       
• Nested List Weight Sum I
                ○ Sol1: stack
                        § stack to store all the cell and level in original array
                        § expand stack if it is not integer, then update level
                                              if it is interger, then add it to the result by mutiple the current level
                        § Time O(n), Space O(n)
                ○ Sol2: recursive
                        § go through the each item in the list
                                        ® if it is integer, multiple cur level and add to the res
                                        ® if not, add one level and get the list go to next recursive level
                        § Time O(n), Space O(h)
                       
• Nested List Weight Sum II
                ○ sol1: BFS
                        § if is integer, add to the current sum
                        for each level, if we go through all the cell and still find next level, we will add previous um again
                        • lower level sums are added multiple times to total sum.
                ○ Sol2: Recursive
                        • first get the total depth the next recursive to get current sum *  (max_level - level + 1)
• Sum Root to Leaf Number
• Max Path Sum From Leaf to Root

06/30
接了一个ML实习，这两天太忙了，写题目就少了点
        • Longest Palindrome Substring
                ○ Sol1: recursive
                        • two case: odd and even
                        • Time O(n^(log(n))), Space O(n)
                       
                ○ Sol2:dp
                        • dp[i][j] whether i to j is a valid plindrome substring
                        • use k to indicate the current length - 1of substring we are looking for , i indicate the start index
                                § j = i + k
                                § case1 s[i] == s[j], if j - i  <=  1 or dp[i + 1][j - 1]: dp[i][j] = True, then check max
                                § case2 s[i] != s[j], dp[i][j] = False
                        • Time O(n ^2), Space O(n ^2)
                       
        • Longest Palindrome Subsequence
                ○ dp
                        • dp[i][j] ->the longest palindromic subsequence between index i and index j.
                        • initial: each cell itself is a palindromic subsequence with length 1
                                from 0 to len(str) -> how many cells between i and j, j = i + k
                                case1 i == j:   dp[i][j] = 1
                                case2 str[i] == str[j]: dp[i][j] = dp[i + 1][j - 1] + 2
                                case3 str[i]  != str[j]: dp[i][j] = max(dp[i + 1][j]  +  dp[i][j - 1])
                        • Time O(n^2), Space O(n^2)

        • Largest Sum of a subarray
                ○ sol1 dp
                        • Base case: M[0] = array[0]
                        • Induction rule:
                                □  M[i] represents the max subarray sum in the range[0, I,
                                 M[i] = case1: if M[i - 1] < 0, M[i] = array[i]
                                          case2: if M[i - 1] >= M[i] = M[i - 1] + array[i]
                ○ sol2 binary search
                ○ Follow up: recorde range
                        § need 4 variables-> cur_start, cur_end, final_start, final_end
                        § for updating cur_start: when M[i - 1] < 0
                                        cur_end = cur
                   Final_start = cur_start when M[i] > res