Algorithm:

DP

1. Best Time to Buy and Sell Stock
  • everyday's max profit = today's price - minimum price before today
  • change array to stock's price change between today and yesterday == Maximum Subarray
2. Best Time to Buy and Sell Stock II
3. Maximum Subarray
  • most optimal structure:
    • dp[i] represent: maximum subarray ending with A[i]
    • if dp[i - 1] is negative, do not add it on dp[i]
    • check every dp[i], crz every dp[i] might be maximum
  • reduce Space Complexity to O(1)
4. Unique Paths
5. Unique PathsII
6. Word Break
7. Longest Palindromic Substring
8. Palindrome Partitioning
  • Find all substring T:(n^2), check if it is palindrome O(n), so brute force T: O(N*N^2)
  • BTW use DP to record if i -> j is palindrome, i - 1 -> j + 1's check is O(1)

All about Array and String

1. First Unique Character in a String
  • traversal the String Two times
    • 1st: Use map record every character's frequency
    • 2nd: first unique Character means frequency is one
  • traversal the String One Time
    • LinkedHashMap records characters's position without duplicates
    • Set records which characters without duplicates
2. Move Zeroes
  • traversal two times
    • 1st: shift all non-zeros to left part of array and record how many non-zero numbers
    • 2nd: flip right part of array to zero
  • traversal by swap
3. * Find the Duplicate Number
  • T: O(NlogN) S: O(1) Binary Search
    • pigeonhole principle: count how many numbers (count) in whole array smaller or equal than mid number
      • count > mid -> duplicate in left part of array
      • count <= mid duplicate in right part
  • T: O(N) S: O(1) Floyd's Cycle dection
    • every index linked with every value in array, if there is duplicate in array and traversal first element index to value and value to index, it should be cycle in this traversal. After my observation, the begin of cycle is duplicate number
      • find meeting point of slow and fast
      • set other point in start and traversal again to find begin of cycle
4. Missing Number
  • Sort + Binary Search -> O(NlogN)
  • Math Computation( Sum)
  • Bit Manipulation (XOR) --> n ^ n = 0, n ^ 0 = n
    • traversal whole array one time by XOR all number and their index
    • missing number is result
5. Reverse Integer
  • Traversal every digit overflow problem return 0
    • long
    • if current temp number / 10 != res, that means already overflow
6. Sqrt(x)
  • Newton iterative
  • Binary Search approach
    • 0 -> N, test mid of whole range if N / mid and mid to avoid overflow
    • precision control Math.abs(ans * ans - x) > delta
7. *Pow(x, n)
  • different situation about n: negative, 0, positive, overflow for Integer.MIN_VALUE
  • n divide 2 every time (T: O(logN))
    • n is odd: res *= x
    • x *= x
8. *Merge Intervals & Meeting Room & Maximum alive people
  • sort intervals and traversal and check every interval's intersections
    • sort by start time
    • use two pointers(start and end), merge intersection
      • start < end --> update maximum end
      • start > end --> add new interval into result and reset start and end
    • add last interval
9. Reverse Words in a String
  • Reverse two times to get result
    • Reverse whole string
    • Reverse one by one
10. Kth Largest Element in an Array
  • Sort + find Kth Largest O(NlogN)
  • Put all elements to Heap and control heap in size k: T:O(NlogK) S: O(K)
  • Quick select O(N)
    • position = partition(left -> right)
    • k - 1 == pos to decide to which part of array
11. Group Anagrams
  • Group Anagrams means set all anagrams to same hashcode
    • change string to char[]
    • sort char[]
    • turn back to string and used for map's key string.valueOf(char[])
  • set every position as start point and use depth first search whole board
    • every step have four choice: up, down, left, right
    • if depth(step) equals word's length --> find it
13. *Lexicographical Numbers
  • Depth first search every node in preorder
    • loop 1 --> 9 first
    • preorder of DFS to access every node
    • trim operation if (10 * cur + i > n) return
14. String to Integer(atoi)
  1. discards all leading whitespaces
  2. sign of number
  3. overflow
  4. invalid input
15. Roman to Integer
  • Store all Roman character and number into map and traversal it
    • if(map(i) < map(i + 1)) res -= map(i)
    • else res += map(i)
16. Rotate Array
  • the k may larger than whole length of array, so k %= nums.length
    • reverse all numbers
    • reverse first k numbers
    • reverse last n - k numbers
17. *Next Greater Element III
  • this problem is same as next permutation
    • find first decreasing number from right to left i
    • find next larger number than decreasing number j
    • swap i and j
    • reverse i + 1 to length
18. *H-index
  • According H-index's definition: O(NlogN)
    • sort array to ascending order
    • find first element satisfy citation[i] > i
  • Counting sort O(N)
    • count papers for each citation number(if some of citations over length of array, set it n, because no H-index over length)
    • find H-index from large to small citations, H-Index > papers[n]
19. Palindrome Permutation
  • Use hashSet to record every character's frequency
    • if not contains, add it in
    • if contains, remove
    • check set's size if is larger than one?
  • BitSet?
20. Factorial Trailing Zeroes
  • All trailing zeroes are comes form 10
    • 10 comes form 2 and 5
    • even number is more than 5, so the number of 5 is trailing zero
21. *Read N Characters Given Read4 II

Two pointers

1. Two Sum(return index)
  • Sort + two pointer O(NlogN)
  • HashMap O(N)
    • use map to record previous value and value's index
    • if map containsKey (target - current) value, return result
2. 3Sum
  • brute force : O(N^3)
  • sort + two pointers: O(N^2) + O(NlogN) = O(N^2)
    • skip duplicates
      • big
      • small
      • equal
3. 3Sum Closest
  • update value diff that means Math.abs(current 3Sum and target) every time
    • skip duplicates
      • big
      • small
4. Merge Sorted Array
  • merge two array from end to start to avoid overlap or shift all numbers
    • three pointers
      • index-- everytime
      • first array index - 1 -- bigger than second
      • second array index - 1-- bigger than first
    • don't forget remanence of second array if second array's size > first's actual size
5. *Remove Duplicates from Sorted Array
  • use two pointers, first is fast, second is slow
    • index++ when find the unique number
    • nums[index] == nums[i] continue
6. Search in Rotated Sorted Array
  • Binary Search
    • check mid > right(control mid)
      • target > mid--> right part
      • target < mid
        • target > right --> left part
        • target < right --> right part
    • check mid < right
      • target < mid --> left part
      • target > mid
        • target > right --> left part
        • target < right--> right part
7. Container With Most Water
  • two pointers set begin and end of array
    • better choice
      • right line higher than left line --> left++
      • left line higher than right line --> right--
8. * Trapping Rain Water
9. Longest Substring Without Repeating Characters

Linked List

1. Add Two Numbers II
  • use two stacks to reverse list
    • pop out integer every time from each of stack
    • don't forget flow
    • add result node reversely
  • reverse two list == Add Two Number
2. Add Two Numbers
  • same with Add Two NumbersII
3. Copy List with Random Pointer
  • DNA copy
    • insert new node --> copy each Node's next
    • copy random --> new node's random = original's random.next
    • split to two linked list
4. Reverse Linked List
5. Intersection of Two Linked Lists
  • image two linked lists as a cycle, use two pointers
    • first pointer get the end of list, redirect other's head
    • second pointer get the end of list, redirect other's head
    • when two pointer equals, this is intersection of lists
6. Linked List Cycle
  • two pointers, one is fast, other is slow. if they meet, that means this list has cycle
  • follow up: let head and meeting pointer moving with same speed --> next meeting point is begin of cycle
7. Swap Nodes in Pairs
  • iterative:
    • fakehead, cur
    • first, second
  • recursive

Tree

1. #Populating Next Right Pointer in Each Node II
  • recursive
  • iterative: BFS
    • Root Top-Down to left side of tree
      • upperLevel traversal to null
        • all child of upper level connected (fakeHead will helps)
2. Validate BST
  • inorder traversal is ascending order
    • because Java pass by value: set global variable pre
    • check left subtree first
    • check current node and set pre to current node
    • check right subtree last
3. Binary Tree Level Order Traversal
  • iterative: Queue
  • recursive: Depth is level order's index
    • depth >= res.size() push new level in res
    • add current node to current level: res.get(depth).add(root.val)
    • recursively to left and right
4. Binary Tree Zigzag Level Order Traversal
  • Solve this problem recursively
    • use LinkedList as inner list of result to reduce Time Complexity
    • depth is odd, add head
    • depth is even, add tail
5. Construct Binary Tree from Preorder and Inorder Traversal
  • use two pointers to close in substree
    • preorder's first is root, find it in inorder's array --> left aside of target is left subtree, right aside is right subtree
    • distance control for preorder--> index - inLeft
      • preLeft + 1 --> preLeft + distance
      • preLeft + distance + 1 --> preRight
    • inorder's subtree
      • inLeft --> index - 1
      • index + 1--> inRight
6. Same Tree
7. Symmetric Tree
8. Balanced Binary Tree
  • Res(int depth, boolean isBal)
    • update depth every time Math.max(left.depth, right.depth) + 1
    • check left's Res and right's Res
      • absolute difference of depth > 1
      • all are balance
9. Path Sum II
  • backtracking
    • root == null return;
    • root.left == null && root.right == null(leaf node)
      • sum == root.val, add it to result and don't forget remove
      • sum != root.val return;
10. Kth Smallest Element in a BST

  • Binary Search O(NlogN)

    • count the number of nodes in left subtree
      • count + 1 == k return root.val
      • count + 1 < k find in left
      • count + 1 > k find in right

  • inOrder traversal and count O(N)

    • set global variable count and res
      • root == null-->return
      • check left
      • update count and check current
      • check right
11. Serialize and Deserialize Binary Tree

Data Structure

1. Min Stack
  • use two stacks to solve
    • sequence stack like normal stack
    • min stack store current stack in real time
      • min push --> when empty of x <= min.peek()
      • min pop --> when sequence.pop() == min.peek()
2. LRU
  • use LinkedList represent degree of recent and HashMap to locate ListNode put -> O(1) get -> O(1)
    • put(key, value)
      • contains --> move previous Node to head
      • full
      • rest -> add to head
    • get(key)
      • do not contains
      • move current Node to head
  • LFU
3. Implement Queue using Stacks
  • use two stacks
    • first stack is used to collect element
    • second stack is used to reversely take element out
      • if second is not empty, take element directly
      • if second is empty, put all element of first stack into second to get reverse order
4. *Valid Parentheses
  • use stack
    • push every left bracket's right bracket
    • if current is right bracket != stack.pop() return false
    • stack.isEmpty()return false
5. Implement Stack using Queues
  • use two queues to solve
    • first queue is used to collect element
    • second queue is auxiliary to remove first queue's elements in
      • push: push all element in queue1
      • peek: same with pop
      • pop:
        • move all elements from queue1 to queue2 and only leave one element
        • swap two queues
        • return queue2.poll()
6. Implement Trie(Prefix Tree)

results matching ""

    No results matching ""