Exercise G

Summary for some exercise.

Some Functions

• str.startswith(prefix)
• str.replace(old_str, new_str)
• re.replace(pattern, repl, string)
• ''.join(list)
• sort(key=lambda x: (x[0], -x[1]))
• str.isdigit() and str.isalpha()
• import queue
  • a = queue.PriorityQueue()
  • a.put(2)
  • a.queue[0]
  • a.get()

• try:
      raise Exception
  except Exception:
      print("hello")

Boundary Conditions

• Always check wether the input can be [] or None
• If there is several input, consider about their length wether will influence the process

Basic Data Structure and Algorithm

Array and string

• No. 66 - Plus One
  List
• No. 657 - Robot Return to Origin
  Count the vertical and horizon
• No. 54 - Spiral Matrix
  Traversal the array in a circle

  up = 0; left = 0
  down = len(matrix)-1
  right = len(matrix[0])-1
  direct = 0  # 0: go right   1: go down  2: go left  3: go up
  res = []
  while True:
      if direct == 0:
          for i in range(left, right+1):
              res.append(matrix[up][i])
          up += 1
      if direct == 1:
          for i in range(up, down+1):
              res.append(matrix[i][right])
          right -= 1
      if direct == 2:
          for i in range(right, left-1, -1):
              res.append(matrix[down][i])
          down -= 1
      if direct == 3:
          for i in range(down, up-1, -1):
              res.append(matrix[i][left])
          left += 1
      if up > down or left > right: return res
      direct = (direct+1) % 4

• No. 929 - Unique Email Address
  String process, split, replace
• No. 289 - Game of Life
  Process boundary of array
• No. 228 - Summary Ranges
  List
• No. 415 - Add Strings
  Vertical
• No. 448 - Find All Numbers Disappeared in an Array
  Relationship between index and value of list - use constant memory
• No. 388 - Longest Absolute File Path
  string’s function
  • str.startswith(prefix)
  • str.replace(old_str, new_str)
  • cnt * str
  • re.replace(pattern, repl, string)

HashTable

• No. 929 - Unique Email Address
  • Count the unique value
• No. 387 - First Unique Character in a String
  • Find the first unique value
• No. 890 - Find and Replace Pattern
  • Project the characters

Queue, Stack

• No. 20 - Valid Parentheses
  • Use stack to store items temporarily, when new item arrives, check wether it can meet the requirements.
• No. 394 - Decode String
  • Stack, process bracket pairs.
• No. 739 - Daily Temperatures
  • Check the current temperature with the top element in the stack
  • If current temperature is larger than the top element in the stack, pop that value, and calculate the required day for that pop item

Heap

• No. 253 - Meeting Rooms II
  • Sort the meeting intervals with the start time Sorted(list, key=lambda x:x[0])
  • Find the earliest end meeting, and assign this new meeting to that room. In order to manage the earliest end meeting, use min heap

Tree

• No. 173 - Binary Search Tree Iterator
  Travel the BST

Graph

• No.399 - Evaluate Division
  See below in Search part
• No.684 - Redundant Connection
  • Use union find to check the cycle in graph

Sort

The application of sorting can solve many problems. The basic sort functions are in here

• No. 56 - Merge Intervals
  Sorted(list, key=lambda x:x[0]), then sort one by one
• No. 253 - Meeting Rooms II
  • Sort the meeting intervals with the start time Sorted(list, key=lambda x:x[0])
  • When new meeting arrives, check wether there is any previous meeting already ends

    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        sorted_intervals = sorted(intervals, key = lambda x: x[0])
        rooms = []
        for intervals in sorted_intervals:
            if rooms == []:
                rooms.append(intervals[1])
            else:
                flag = False
                for i in range(len(rooms)):
                    if rooms[i] <= intervals[0]:
                        rooms[i] = intervals[1]
                        flag = True
                        break
                if not flag:
                    rooms.append(intervals[1])
                
        return len(rooms)

• No.1057 - Campus Bikes I & II
  • Find all the distances and sort them

Search

• No. 200 - Number of Island
  • DFS(Recursive), BFS(Queue)
  • Use a closed list(2D Array or Set) to indicate wether the item is visited
  • Check the valid(boundary)
• No. 463 - Island Perimeter
  Same with 200. The item can contribute one side if there is not other items in that specific direction
• No. 399 - Evaluate Division
  • Establish a graph to connect each number
  • Use DFS to do the graph search
• No. 489 - Robot Room Cleaner
  • Use DFS to do the graph search
  • Let robot return to previous position after one recursion
• No. 815 - Bus Routes
  • Establish a graph which indicates what buses can take at each stop
  • Use DFS to search, stored the visited stops and visited buses

Recursion

• No. 17 - Letter Combinations of a Phone Number
  DFS, Backtracking
• No. 50 - Pow(x, n)

DP

• No. 139 - Word Break
  If s[:j] can be formed by the dict, and s[j:i] are in the dict, s[:i] can be formed by the dict

  def wordBreak(self, s: str, wordDict: List[str]) -> bool:
      # dp[i] means s[0: i] (from s[0] to s[i - 1]) are in wordDict
      dp = [False for _ in range(len(s) + 1)]
      se = set(wordDict)
      dp[0] = True
      
      for i in range(len(s) + 1):
          for j in range(i):
              # check wether s[j: i] in wordDict and 
              # s[0: j] are in wordDict
              if dp[j] and s[j: i] in se:
                  dp[i] = True
                  break
      return dp[len(s)]

• No. 279 - Perfect Squares
  dp[i] = dp[i - j * j] + 1

  def numSquares(self, n: int) -> int:
      # dp[i] means least num sum to i
      dp = [float('inf') for i in range(n + 1)]
      
      dp[0] = 0
      dp[1] = 1
      for i in range(2, len(dp)):
          if i ** 0.5 == int(i ** 0.5):
              dp[i] = 1
              continue
          j = 1
          while j * j <= i:
              dp[i] = min(dp[i], dp[i - j * j] + 1)
              j += 1
  
      return dp[n]

• Unique Paths Series
  No. 62

Complex Analysis

Divide into Subproblem

• No. 23 - Merge k Sorted Lists
  • Bottom Up: Merge 2 -> Merge K
  • Up Bottom: Similar to merge sort
  • Heap to store the current item of all the nodes
• No. 42 - Trapping Rain Water
  • Convert to each position’s capacity
  • The capacity of each position = min(Max left height, Max right height) - Current height

Convert the question with definition

• No. 4 - Median of Two Sorted Array
  • Convert the median to another description
  • Binary search
  • Boundary concern
• No. 560 - Subarray Sum Equals K (Count)
  • The sum of a continuous array = The sum from 0 to current position - The sum from 0 to a position before the current position
  • The sum K continuous array = Current accumulate sum - The sum (accumulate sum - K) continuous array
  • At each position, Count(The sum K continuous array) = Count(The sum (accumulate sum - K) continuous array)

    def subarraySum(self, nums: List[int], k: int) -> int:
        if nums == []:
            return 0
        
        accu_sum = {}
        accu_sum[0] = 1
        sum_ = 0
        count = 0
        for num in nums:
            sum_ += num
            if sum_ - k in accu_sum:
                count += accu_sum[sum_ - k]
            if sum_ in accu_sum:
                accu_sum[sum_] += 1
            else:
                accu_sum[sum_] = 1
        return count

• No. 31 - Next Permutation
  • Understand Permutations
  • Find the last increasing points, swap the lower value with the first value after the peak and which is also larger than this lower value, swap them
• No. 240 - Search a 2D Matrix II
  • Find the correct searching path
• No. 336 - Palindrome Pairs
  • How to check wether two strings can form a palindrome string
  • for [str1+str2]
  • str1[:i] and str1[:1], if str1[:1] equals to the mirror of itself, and reversed str1[:i] equals to str2, then it can form a palindrome string
• No. 855 - Exam Room
  • Store each students’ positions from least to biggest
  • Check the interval when new student comes
• No. 853 - Car Fleet
  • Faster car will be blocked by slower cars
• No. 857 - Minimum cost to Hire K workers
  • Calculate the wage for single workload and sort them. All workers should be paid at the largest wage/workload to meet the requirements
  • Use a max heap to store the workload

Divide Conditions

• No. 22 - Generate Parentheses
  • Track the current number of opening bracket and closing bracket
  • If the number equals to 2 * n, it ends
    • If the opening bracket is less than n, continue add opening bracket
    • If the closing bracket is less than n and less than opening, continue add closing bracket
• Buy and sell Stock Series
• Bike and biker Series
• No. 406 - Queue Reconstruction by Height
  • Lower people won’t influence taller people, thus organize taller people firstly
  • Insert the people exactly into some positions. Although there positions will change later, but it doesn’t matter because later people won’t influence that
• No. 224 - Basic Calculator
  • Data stream
  • Divide into several conditions
  • Use stack to store previous result
  • Prefix infix suffix expression
• No. 218 - The Skyline Problem
  • Sort: what if the pos is the same
    • Sort the higher first if it is a rising edge
    • Sort the lower first if it is a falling edge
  • Divide Conditions
    • When encounter a rising edge
    • When encounter a falling edge
• No. 1057 & 1066 - Campus Bike I & II
  • Use bit number to represent status

Analysis

• No. 843 - Guess the Word
  • Min-max. Make the worst case happen at a least percentage
• No. 659 - Split Array into Consecutive Subsequences
  • Counter(number)
  • Put new number into the previous list, if there is no previous list, use 3 new values to generate a new list

Structure Implement

• No. 146 - LRU Cache
  • Generate something to store the recently used element
  • Note: dict.pop(key), list.pop(index)
  • Use LinkedList because the most recent item is in the tail of the linked list
• No. 297 - Serialize and Deserialize Binary Tree
  • Use BFS to traversal the tree
  • Use low and fast pointer to form the tree
• No. 155 - Min Stack
  2 Stacks. One store all items, one store the current min items
• No. 341 - Flatten Nested List Iterator
  Recursively flatten the nested list
• No. 535 - Encode and Decode TinyURL
  Map

HashTable

TBD

Tree

TBD

Graphs

• Adjacency Matrix
• Adjacency List

Reference

• https://www.1point3acres.com/bbs/thread-446944-1-1.html