疫情每天打卡写题

05/10
• Course Schedule
  ○ recursive and dictionary
  ○ 用dict组成directed graph, then use recursive to check whether there exits any cycle

  ○ Time complexity O(V^2 + EV) each dfs in adjacency list is O(V+E) and we did V times
  ○ Space O(E)
       
• Course Schedule II
  ○ 与前一个做法类似
  ○ 用一个array来存上课顺序
  ○ 当一个course 的所有条件满足时加入array, 如果这个课时存在cycle直接返回【】
Time complexity O(V^2 + EV) , Space O(E)


• Celebrity Problem
  ○ Sol1: direct graph
   • count the indegree and outdegree for each person
   • array[i] => how many people liked him/her more than # of people he/she liked
   • a celebrity will have n - 1 number of people like him/her
   • Time O(n^2), Space O(n) -> n: # of people

• Find Town Judge
   • same as above
   • count the indegree and outdegree for each person
   • array[i] => how many people trust him/her more than # of people he/she trust
   • Time O(n), Space O(n) -> n: n # of relationship

• Minimum Height Trees
  ○ Topological algorithm
  ○ core case è if n <=1 :return [0]
  ○ 先做graph从最外围开始减掉叶子(叶子只与另一个node相连接), 最后留下的root就是tree的root
               

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/01

        • Invert Binary Tree
                ○ Sol1 recursive
                        § base case: not root
                        § need to exchange right and left node at the same time
                        § return root
                        § Time O(n), Space O(h)
                ○ Sol2 Iterative
                        § Queue: initial - [root]
                        § for the each element in each level, first push left/right node into queue, then exchange right and left node
                        § Time O(n), Space O(n/2)

        • Serialize and Deserialize Binary Tree
                ○ Sol1 iterative
                        § Serialize:
                                □ queue: initial - [root]
                                □ once we popleft node from the queue, append the left and right children into queue and append the val of the current node to the res, if not node, append it as "#"
                        § Deserialize:
                                □ queue: initial -[TreeNode(nodes[0])]
                                □ use a global variable index ref to the node in the array
                                □ popleft node from the queue and add the left and right children (if not "#") to this node
                        § Time O(n), Space O(n)
                ○ Sol2 recursive
                        § Serialize:
                                □ preorder serialize: can separate the right and left subtree
                                □ give different order of nodes than the iterative output
                        § Deserialize:
                                □ preorder
                                □ pop the left node and add to the left and right node recursively
               
        • Serialize and Deserialize Binary Search Tree
                ○ recursive / iterative:
                        § Serialize:
                                □ global variable -> append node.val by preorder
                                □ Or apply iterative way to generate Binary search tree
                        § Deserialize:
                                □ first node is root
                                □ separate left and right subtree by finding the first element > root
                        § Time O(n), Space O(n)

        • Insert row into Tree
                ○ Sol1: recursive
                        § case1: depth == : new_root
                        case2: recursive
                                if d == 2 -> insert row into current level
                                store left and right child node and replace the left and right with insert val;
                                append original left and right child to the cur.left.left, cur.right.right
                        § Time O(n), Space O(h)
                ○ Sol2: iterative
                        § queue -> store node and depth
                        § find the level before the insert level
                   Time O(n), Space O(n/2)
         •  Unique Binary search Tree I (复习)
         •  Unique Binary search Tree II (复习)

       
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/11

• Flood Fill
        ○ BFS
        ○ 从起点展开找相邻需要填充的pixel放入queue
        ○ temp存起始点的数值, visited存已经遍历过的点
           Time: O(mn) Space: O(mn)

• Min() function when using stack with time O(1):
        APIs for a Stack:
                                        add()
                                        Pop/Remove()
                                        Top()
                                        Min()
                ○ Sol1: two stack, one store min, one store element

• Trap Max water
                ○ Sol1:
                        • Two dp
                        • left_max = max(left_max[i - 1], height[i]) => 包含i的左边节点最大值
                                从左往右升序
                        right_max = max(left_max[i - 1], height[i]) => 包含i的左边节点最大值
                                从右往左升序
                        • Time O(n) Space O(n)
                       
                ○ Sol2:
                        • left_max, right_max, left, right
                        • 通过小挡板确定最大水位
                        max记录存水
                                if left_max < right_max:
                                        max+= max(0, left_max - A[i])
                          Time O(n) Space O(1)

• Sort in Customer Order
        ○ Sol1: Insertion sort
                *  j : left of the j (not include j) are the element be sorted as A2 array order
                *  Time O(n^2), Space O(1)
        ○ Sol2: Hash table
                * store all letter from A1 to a dictionary
                * loop A2 to check if it is in the A1.dict
                * sort the rest and put into the output
                * Time O(M + N), Space O(n)

• Minimum Window Substring
        ○ sliding window to generate valid substring by checking if all target letters been found
        ○ length: length of target letter
           dict:  target letter count - current window letter count
                if length == 0: all letter in target be found and update and move window  
                if dict[letter] > 0 -> a target letter have not be found
        ○ Time O(n),  Space O(n)

05/12
        • Find Single element in sorted array
                ○ Binary search
                ○ 单独数字的index只能为偶数
                ○ 当mid不等于左右返回mid
                当mid为偶数时如果不等于左边的数, 那么mid左边不包括mid的数不可能成为单独的数字
                                                     等于左边的数, 那么mid右边包括mid的数不可能成为单独的数字
                当mid为奇数时如果等于左边的数, 那么单独的数字出现在右边, 反之在左边
                Time O(log(n)), Space O(n)
         • Find in Mountain array
                ○ 3 BS
                ○ 1st Find the peak element index, l < r (only one peak)
                   2nd search in left part of peak, l <= r (may not be a target behind the peak)
                   3rd search the right part, l <= r
                   Time O(log(n)), Space O(n)

          • Missing number (sorted)
                 ○ Sol1:
                     if num[mid] > mid + 1, missing num in the left, (can be mid)
                     if num[mid] == mid + 1, missing num in the right part (can not be mid)
                     注意返回index+1并且还要判断是否最后一个数是missing num
                     Time O(logn), Space O(1)
                 ○ Sol2: Xor …
                    Time O(n) Space O(1)

           • 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)

05/13

        • Remove K digits
                ○ Sol1: using stack
                        need to make right most digit as small as possible, and we add/remove until k = 0
                        need to check empty stack when we go through the array and whether k == 0
                        remove all "0" in the head
                       * Time O(n), Space O(n)
                ○ Sol2: DFS
                         枚举所有可能
                        * Time O(n! /k!)

        • Distance to the First Greater Number
                ○ Stack, store the number which did not find the next greater element and it's index
                        nums in stack follow descending order
                ○ append stack if not stack or stack[-1] > num
                if num > stack[-1]: use index to indicate the distance and the position
                ○ Time O(n), Space O(n)

        • Next Greater Number I
                ○ Stack, store the number which did not find the next greater element
                        num in stack follow descending order
                dict, key: number, val: the first number on its right greater than it
                ○ 1st go through the first list generate the dict, then the second to get ans
                ○ Time O(n), Space O(n)

        • Next Greater Number II
                ○ Stack
                ○ similar to the previous one, need one more loop to mimic a circle
                ○ Time O(n), Space O(n)
               
        • Next Greater Number III
                ○ Stack
                ○ start from the right, find the first num smaller than it's right, and switch it with the most right num larger than it. Then reorder the right part as ascending order
                        e.g.    xxx 2 4 3 2 1 ->  xxx 3 4 2 2 1 ->  xxx 3 1 2 2 4
                ○ Time O(n + log(n)) ? Space O(n)
               
        • Remove Duplicate Letters
                ○ Stack & Greedy,
                ○ data structure:
                        * counter for the char freq
                        * boolean list: whether we have this letter in the stack
                        * stack: store the appropriate order of the string without duplicates
                ○ logic: if current char was used in sol string, continue
                          if not, keep replacing the last char of current sol with smaller char, and keep
                          the char if there is no duplicate after it
                *  Time O(n), Space O(n)

5/14今天看了一个新data structure, Trie

       • Implement Trie (Prefix Tree)

                   ○ Initial :  每个节点对应一个前缀, 每个节点的child用dic来存， 并且判断这个节点是否是一个单词的结尾
                   ○ 注意: search 中需要判断最后的节点是否为某个单词结尾

                   Time O(m) Space O(nm)

         • Word search II
                 ○ Sol1 Brute Force, DFS
                 ○ For each word, start from each element of the matrix, DFS
                    for each path, need store the elements be used
                    Time O (k*n*m*4^L)          k: # of words,
                                                               m*n matrix,
                                                               L the longest length of the word
                 ○ Sol2
                 ○ Build a prefix tree by the words
                 ○ For each element, DFS, whether it appears in the prefix tree
                    store a visited path

                    Time O(k*L + m*n*L)            k*L: built a prefix tree

05/15
周五休息一下~
        • Maximum Sum Circular Subarray
                ○ Obs1: total sum - min subarray sum = max sum in circular subarray (in general case)
                ○ Obs2: if all negative number in the array: obs1 = 0  ->  therefore also need max sub array sum
                ○ Calculate min subarray sum and max subarray sum
                     case1: total - min_sub == 0               ->     return max_sub
                     case2: total - min_sub < max_sub   ->      return max_sub
                     case3: total - min_sub > max_sub   ->       return max_sub
                  Time O(n), Space O(1)

        • Smallest Element Larger than Target
                ○ BS
                ○ while l < r - 1         ->       防止死循环
                     最后先判断num[l] > target 再判断num[r]是否 大于target
                Time O(logn) Space O(1)

        • Search for a range
                ○ step1: First Occurrence
                   step2: Last Occurrence
                              return range
                Time O(log(n)), Space O(1)

   05/16     

        • Odd Even Linked List
                ○ even, odd, evenhead = head.next, head, head.next
                ○ update even and odd, after while loop append evenhead to odd
                ○ Time O(n), Space O(1)

        • Partition Linked List
                ○ Similar to Odd even linked list
                ○ made two linked list, l1 = temp1 = ListNode(None), l2 = temp2 = ListNode(None)
                更新temp1, temp2
                temp1.next = l2.next è return l1.next
                ○ Time O(n), Space O(1)
               
        • Delete Nodes At Indices
                ○ make a dummy head to keep the newhead; k -> track the index of current node in original list
                go through all the delete index node,  delete next node if k + 1 == index
                need to check whether the deleted node exist
                ○ Time O(n), Space O(1)
        • Remove Linked List Elements
                ○ create a dummy head just in case the head will be deleted
                ○ track the prev node and check if prev.next.val == val
                while prev.next and prev.next.val == val            =>       prev.next = prev.next.next
                ○ Time O(n), Space O(1)
               
        • Reverse Alternate Nodes
                ○  odd-even linked list first, and then reverse the even part
                linked the new evenhead to the odd part
                ○ Time O(n), Space O(1)
        • Check if linked list is Palindrome
                ○ Sol1
                        • separate the linked list to left and right part
                        • then reverse the right part and compare it with the left part
                        • Time O(n), Space O(1)
                ○ Sol2
                        • recursive, self.res
                        • compare each node in recursive way
                        if there is one pair does not match, update res = false
                        • Time O(n), Space O(n)

05/17
        • Count compete tree nodes
                        * Recursive + property of the complete tree
                              *  If the depth of right subtree equal to the depth of left subtree, then the left subtree is a perfect tree.
                              * Otherwise, the left subtree has one more level than the right subtree and the right subtree is a perfect tree.
                              * # of node = The nodes of a perfect tree (2 ** h - 1) + 1 root node + recursively the number of nodes in the complete subtree
               
                Time complexity: O(log(n)^2)
                                             Find height is O(logn), and halve the tree in every recursive step -> O(log(n)) steps.

        • Word Pattern
                ○ pattern and word must in one - one relationship
                ○ two dictionary: key: pattern,       val: word
                                            key: word             val: patter
                if pattern not exist, check whether word already have a match
                if pattern exist, check whether word match the val
                ○ Time O(n), Space O(n)
       
         • Word Pattern II
                ○ Recursive to go through all possible matching between pattern and word
                and two Hashmap to store the match pair
                ○ if current pattern in the 1st Hashmap,
                        check whether the match val == input word val (be careful about the length)
                if current pattern not in the 1st Hashmap
                        go through the input string, and check whether new substring in 2nd hashmap,
                        if already exist continue
                        else recursive
                ○ Time O(n ^ m), Space O(m + n) pattern m, string n

           • Find all anagrams of a substring S2 in a long string S1
                ○ Hashmap to store the S2 letter frequency, Match indicates how many letter be matched in current substring
                ○ For each step: update the hashmap frequency, if freq == 0 -> match += 1
                                                                                               if i > len(s1) -> update the dic[s1[i - len(s2)]] & match
                   Then if match == len(dic) -> update res
                ○ Time O(len(S1))

05/18

        • Reorder Data in Log Files
                 ○ divide logs into two parts, one is digit logs, the other is letter logs
                 ○ when suffix is tie, sort by identifier  -> letters.sort(key = lambda log: log.split()[0])
                    then sorted by suffix                           
                    Time O(nlog(n)) Space O(n + m)

         • Permutation in String
                ○ Same as find all anagrams of a substring in a long string
                ○ number_matches  <= len(reference HashMap) : how many letter completed match in substring
                HashMap: the frequency of each letter in the substring
                ○ For each step:  update Hashmap, if number_matches == len(reference HashMap) return True
                ○ Time O(len(S1))

        • English Words to Integer e.g. "Five hudred and thirty one" -> 531
                ○ recursive + dictionary
                ○ check negative or not
                if number < 100  or num == "and"     ->  additive
                if number > 100                                   ->  multiplicative  num * muls[number] + self.add(lst[1:])
                ○ Time O(n), Space O(m)  ->  n: n words, m: Hashmap space
        • Top K Frequently Mentioned Keywords
                ○ min_heap + Hashmap
                ○ Counter(word_list)
                   go through the hashmap and update the heap with (freq, word)
                   Time O(n), Space O(n + k + (n - k)log(k))


        • Trim Binary Search Tree
                        * recursive
                        * find the root: if root.val > R  -> return self.trim(root.left,   L, R)
                                            if root.val < R ->  return self.trim(root.right, L, R)
                           trim the right and left subtree:
                                                root.left   =  self.trim(root.left,    L, R)
                                                root.right =  self.trim(root.right, L, R)
                        Time O(n), Space O(h)

05/19

如果有人看的话分享一个youtuber，有时候刷题会去看他的讲解，感觉还不错。
https://www.youtube.com/user/xxfflower

        • Ugly Number
                ○ if num = 2^i * 3^j * 5 ^k, it is a ugly number
                ○ core case: num == 0
                        check if num % factor == 0 to update num
                        return num == 1
                ○ Time O(log2(n) + log3(n) + log5(n)), Space O(1)

        • Ugly Number II
                ○ Sol1
                        generate all ugly number then sort it
                        return nums[n-1]
                        Time O(Nlog(N)), Space O(N)
                ○ Sol2
                        generate all ugly number by order
                                i2, i3, i5 -> which candidate be processed by this factor
                                ugly_num-> increase order of candidates
                                new_num = min(     ugly_num[i2] * 2,
                                                           ugly_num[i3] * 3,
                                                           ugly_num[i5] * 5)
                                if new_num == ugly_num[i2] * 2   ->   i2+=1
                        Time O(N), Space O(N)

        • Ugly Number III
                ○ Binary search + greatest common divisor
                        F(N) = (total number of positive integers <= N which are divisible by a or b or c.)
                        F(N) = N/a + N/b + N/c - N/lcm(a, c) - N/lcm(a, b) - N/lcm(b, c) + N/lcm(a, b, c)(lcm = least common multiple)
                        math.gcd(x, y) -> return the greatest common factor
                ○ Find the least integer N that satisfies the condition F(N) >= K
                ○ Time O(log(2^1e9)),  Space O(1)

        • Power(a, b)
                ○ Sol 1 recursive
                        2 case: b < 0, b > 0
                        helper function: b == 1,       return 1
                                               b is even,  res = a^b//2 * a^b//2
                                                 b is odd,   res = a^b//2 * a^b//2 * a  
                        check overflow
                        Time log(b), Space log(b)
                ○ Sol2 iterative
                        2 case: b < 0, b > 0
                        initial: ans = 1
                                 if b % 2 == 1: ans *=  a   b  - = 1
                                 else:                a = a*a      b //= 2
                   Time log(b), Space O(1)

       • Online stock span
                ○ stack:
                       store the current stock price and the span of the stock's price today, then stock price in stack is following descending order
                       Push every pair of <price, result> to a stack.
                       Pop lower price from the stack and accumulate the count.

                   Time: Amortized is O(1), worst case O(1), Space O(n)