疫情每天打卡写题

ztamber

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 (复习)

ztamber

06/02
• Delete Node in a Linked List
○ update the cur val with the next node val
○ update the cur.next with the cur.next.next
○ Time O(1)

• Insert into a Cyclic Sorted List
• case1: no head
• case2: insert val > max or insert val < min
• case3: insert val between two nodes' val
○ Sol1: find the max val in the list, then the next val must be min
set cur == min,  check if is case 2 or case3
insert node if cur.next val > x or cur.next != head
○ Sol2: use two pointers point to the possible pair of nodes between the insert node
break the loop if case2 or case3:
case2: prev <= insertVal <= cur
case3: prev >= cur and insertVal >= prev or insertVal <= cur
○ Time O(n), Space O(1)

• ReOrder Linked List
○ two pointers + recursive/iterative
○ two pointers to two separate linked list (No need dummy head)
○ then reverse the right part by recursive / iterative
○ connect two parts with right order
               Time O(n)

• Copy a linked list with extra pointer
○ Major challenge is how to avoid multiple duplicate of the same node
(只建立一一对应关系)
○ HashMap <key = original Node, val = duplicate node>
• prev -> store the dic[previous node ] to connected with the current node  (need to store the new head when prev == None)
• for each round, check whether random node exist and whether it be copied in hashmap
• prev, current = dic[current], current.next
                  Time O(n), Space O(n)

ztamber

06/03
贪心算法

• Two City Scheduling
○ we need to find way to compare the cost for each people fly to A or B; Using greedy algorithm.
§ For each person,we're trying to minimise extra costs obtained by not sending people to their optimal city.
○ Therefore sorted the  array by the saving costs  x[0] - x[1] -> let first part of people fly to A, second to B
○ Time O(nlogn), Space O(1)

• Meeting Schedule
○ Greedy algorithm: Select two meeting have the smallest gapping time
§ sorted the array by the meeting finished time
§ select the first meeting have start time after the previous finished meeting time, then update the finished time
○ Time O(nlogn), Space O(1)

• Meeting Room II
○ Sol1: sort start time +  min_heap
• By sorting the start time which allow us to find the earliest available meeting once the most recent one is end
§ case 1: if the next meeting start time > recent end time -> replace the recent end time with this end time
§ case 2: if the next meeting start time < recent end time -> push end time into min_heap
§ return size heap
• Time O(n), Space O(n)
○ Sol2: sorted start & end time
• 当做人进出房间，需要知道的是当前房间里面有多少人,并不需要知道谁在房间, 如果两个人同时在房间(meeting overlap), 则需要两个房间
• 用two array / Hashmap 记录start/end time, room: current overlap meeting, res
if start time < end time -> room += 1 -> update min number of rooms
else : room  -= 1                                  -> release a room
         Time  O(nlogn), Space(n)

ztamber

06/06
• Random Pick Weight
○ Sol1 get the sum and random choose number from the sum
since the cumulated sum follows increase order, we could choose the range represented by the index of array which include the random choose number
random.randrange(a, b) -> a <= number < b
○ Sol2 improve the pickIndex part by using BS
§ replace the original array by the accumulated sum
§ Therefore we can apply BS to find out which range include the random number
○ Time O(nlogn)

• Random pick Index
○ Sol1 optimize memory
§ go through the array and if cur == target:
replace it only if count == randit(1, count)
Reservoir sampling
○ Sol2 Hashmap
§ use a dictionary to pre-process the nums array.
§ key: number, val: list of its indices
§ run reservoir sampling over this input

• Random10 using random7
○ (rand7() - 1) * 7 + (rand7() - 1) will get random 0 ~ 48
○ discard 40 ~ 48 -> evenly distribute between 0 to 39
%10 + 1 get evenly distributed between 1 to 10

ztamber

06/08

• Determine whether a number x is a power of 2
○ x's binary representation has only one bit set (写成2进制的2的幂次只有一个1)
○ x > 0
○ Sol1  For loop 31位置/第一个是符号位
x & 1 == 1 ->    记录当前位置是否为1
count       ->    记录多少1
x >>= 1    ->    每次比较后右移一位
○ Sol2 ((x & (x - 1))  == 0 && x > 0)
x - 1                ->       唯一一个1变成0, 他的后面都变成1
x &(x - 1)       ->       如果多余一个1不等于0
○ Sol3 Math
§ if x is power of 4, 8, 16… then x is power of2
§ using while loop to check these till the 2 power of target > n, then divide n by target
then check whether the left number is 1 or not
                     Time O(log(n))

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

• Coin Change
○ each level represents a coin value
○ How many states depends on dynamic changing

• Generalized Reservoir Sampling
○ once self.count > k -> random choose 0 to self.count - 1, if  num < k replace it with cur val
if self.count < k       -> append to the array
idea: for each number, have k/# of counts prob be kept in the array

• Random10 using random7
○ (rand7() - 1) * 7 + (rand7() - 1) will get random 0 ~ 48
○ discard 40 ~ 48 -> evenly distribute between 0 to 39
               %10 + 1 get evenly distributed between 1 to 10

zurich.hill

有兴趣一起刷题吗？如果有的话，留一个微信号呗~ java的

ztamber

zurich.hill 发表于 2020/06/10 03:53:42
有兴趣一起刷题吗？如果有的话，留一个微信号呗~ java的

可以呀，不过我用python，如果不嫌弃的话可以加我zt☺️1996😊0223

ztamber

06/09
• 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)

• Is subsqeuence (with follow up)
○ Sol1
§ using two pointers, one points to the target index not be matched and another point to the current index want to be compared
§ Time O(m * n) Space O(1)    -> m targets, n = max(len(target),  len(string))
○ Sol2
§ hashmap + binarysearch
§ map the index of longer string t and for each letter in s, find the index position in t and search to the right part, if not exits, return False
§ Time O(m*logn), Space O(n)

• Longest Harmonious Subsequence
○ Hashmap
○ Count each number freq in the array, then find each number + 1 or - 1 freq in dic and compare the sum with res
○ Time O(n) , Space O(n)

• Increasing Triplet Subsequence
○ keep track the first two min subsequence number
○ 3 cases:
§ min_2 == None and cur > min_1 -> min_2 = cur
§ cur <= min_1                                     -> min_1 = cur
§ cur > min_1 and cur <= min_2       -> min_2 = cur
§ cur > min_2                                     ->    return True
○ Time O(n), Space O(1)

ztamber

06/10
• Range Sum Query
○ prefix sum
prefix_sum[i] : the accumulate sum include i index element
○ sum between the j and i  ->  prefix_sum[j] - prefix_sum[i - 1]
○ Time O(n), Space O(n)

• Range Sum Query 2D
○ prefix sum
§ prefix[i][j]: the sum of the elements inside the rectangle defined by its upper left corner (0, 0) and lower right corner (i, j)
§ therefore the rectangle be consisted of (row1, col1) and (row2, col2) = prefix[row2, col2] - prefix[row1 - 1, col2] - prefix[row2, col1] + prefix[row1 - 1, col1 - 1] + matrix[row2, col2]
         Time O(n^2) + O(1), Space O(n^2)

• Search Insert Position
○ Sol1: Brute Force
○ Sol2: Binary Search
§ find the first number >= target, then the target shound be inserted in it's position
§ in the end check whether num[l] >= target
         Time O(log(n)), Space O(1)

• Target Sum
○ Sol1 Depth-First-Search
• go through all possible combination of the elements and count how many can get the target number
• Time O(2^n)
○ Sol2 Dp
• if we want to know how manys way to add/minus all elements to get the target, we need to know how many ways to combine the previous elements to get the target - last element and target + last element
• Hashmap:  by adding the current element, key: all combination sum, val: # ways to get this sum
         Time O(n), Space O(n)

ztamber

06/11

• Rainbow Sort II
○ use index to separate colors:
i: all letters to the left hand side of i (not include i) are 0
j: all letters in [i, j) are 1
c: current explore letter, [j, r]
r: all letters to the right sidr of r (not include r) are 3
○  case1: input[c] == 0  -> swap(j, c), then swap(j, i); i++, j++, c++
   case2: input[c] == 1  -> swap(j, c)                         ; j++, c++
   case3: input[c] == 2  ->                                           ; c++
   case4: input[c] == 3  -> swap(c,r)                            ; r--
○ Time O(n), Space O(1)

• Rainbow Sort III
○ Sol1 quick sort
○ Time O(nlog(n)), Space O(nlogn)
○ Sol2
○ each time sort two color, smallest& largest, k colors to k/2 sort two color
§ s: indicate current small number need to be sort, initial 1
l: indicate current largest number need to be sort, initial k
low: all letter to the left hand side of low (not include low) are smaller or equal to s
right: all letter to the right hand side of right(not include right) are larger or equal to l
               Time O(N*K/2), Space O(1)

• Largest Sum of a subarray
○ 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]
○ 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

疫情每天打卡写题

浏览过的版块