0004 - Median Of Two Sorted Arrays 0005 - Longest palindromic substring
DP: F(i, j) = F(i + 1, j - 1) && s[i] == s[j]. When j - i < 2, F(i, j) = s[i] == s[j]
[Golang] Create Two-dimensional array via make([]int, m * n)
TODO: Manacher's algorithm
[Python3] Transfer int to str.
[Python3] Use list[::-1] to get reverse.
[Golang] Modulus operation % preserves symbols
0008 - String to integer atoi
Detect a + b out of the range via comparing a and INT_MAX - b
Detect a * b out of the range via comparing a and INT_MAX / b
Integer string startswith +, - or neither
[Python3] Numbers less than zero are not palindrome.
[Python3] Use list[::-1] get reversal.
[Golang] Use modulus to get reversal.
[Golang] Numbers endswith zero are not palidrome.
[Golang] Reverse half.
0010 - Regular Expression Matching
Division and conquer
$f(x,y)$ is result of matching p[:x] and s[:y]
$f(0,0)$ is True
$f(x,y)$ can be calculated from $f(x-1, y-1)$
When $p_{x-1}$ in alphabet, $f(x,y) = f(x-1,y-1) \land p_{x-1} = s_{y-1}$
When $p_{x-1}$ is ., $f(x,y) = f(x-1,y-1)$
When $p_{x-1}$ is *
When $p_{x-2}$ is ., $f(x,y) =\prod_{i=0}^y f(x-2, y-i)$
When $p_{x-2}$ is alphabet, $f(x,y) = \prod_{i=0}^y f(x-2, y-i) \land g(s, y, i, p_{x-2})$
$g(s, y, i, p_{x-2})$ String s, from y-i to y, whether it contains only the letter $p_{x-2}$
0011 - Container with most water
Two points
Update height every times
[Python3] Compare next, add or minus
0014 - Longest common prefix
[Golang] Compare the string and the last of sorted strings?
Sort array
Two points
[Goalng] Define 2D array via var result [][]int
Two points
[Golang] Sort array via sort.Ints
0017 - Letter combinations of a phone number
Strings contain '1' return []
0019 - Remove nth node from end of list
Two points a and b. Point a is n steps further than point b.
If point a is None, it means the length of list is n. Remove the first node, that is, return head.next
Move two points to next util a reach end (a.next is None).
Remove point b.next when point a is None.
[Python3] Use list as stack
[Golang] Create map: map[type]type
[Golang] Traversing list via for index, element := range list
[Golang] Difference between byte and runc
[Golang] Append element to list via append()
0021 - Merge two sorted lists
[Python3] If one list is empty, then reset is the other
[Golang] Create point: var head *ListNode, head := &ListNode{}
0022 - Generate parentheses 0023 - Merge k Sorted Lists 0024 - Swap nodes in pairs
Return head.next if head is not null
First's next is third if fourth does not exist
0025 - Reverse Nodes in k-Group
Related to 0092 - Reverse Linked List II
Revert link list several times
Function reverse(head, tail *ListNode) *ListNode
Link list: r -> 0 -> 1 -> 2 -> 3 -> 4 -> n
revert(0, 2) reverse from 0, before 2, return r -> 1 -> 0 -> 2 -> ...revert(2, 4) reverse from 2, before 3, return r -> 3 -> 2 -> 4 -> ...revert(head, nil) reverse all of the link list, return r -> 4 -> 3 -> 2 -> 1 -> 0 -> n
0026 - Remove duplicates from sorted array
[Python3] Two points, one from head, the other from tail.
[Python3] No need to exchange variables.
[Python3] $O(m * (m - n))$
[Golang] TODO: KMP
0029 - Divide Two Integers 0030 - Substring with Concatenation of All Words
Found first element not increase from tail
Swap element if found
Sort elements after it
0032 - Longest Valid Parentheses
Dymatic programming
s[x] is ( $f(x) = 0$
s[x] is )
$s_{x-1} = ($
$x \in [0, 2): f(x) = 2$ $x \in [2, \infty]: f(x) = f(x - 2) + 2$
0033 - Search in rotated sorted array
Get rotate pivot via binary-search
Binary-search in two parts
0034 - Find first and last position of element in sorted array 0035 - Search Insert Position
Check rows, columns, blocks separately
NOTICE: Get candidate from block $board[x/33+i/3,y/3 3+y\mod3]$
TODO: next() returns the grid with the least possible
[Golang] Use bytes.Buffer save temp string.
DFS, branchs = candidates
[Golang] Copy slice via copy(dst, src)
0040 - Combination sum II 0041 - First Missing Positive
Sequences of length N can have up to N positive integers
When all positive integers from 1 to N appear, the solution is the maximum value, N+1
The range of solutions is 1 to N + 1
Modify the sequence $nums$ so that $nums_i$ represents whether the number $i+1$ has appeared
Check the sequence nums to find the first number that does not appear
If all appear, the solution is $N + 1$
0042 - Trapping Rain Water
Dynatic Programming
TODO: 2D matrix -> 1D matrix
Multiply bit by bit and add
DFS
[Golang]: Not use append() in params, why?
Quick sort
Transform string to number, sort and base-26 to base-10
$$Pow({x}, {n})=Pow\left({x}^2, \dfrac{n}{2}\right) * Pow\left(x, n \mod 2\right)$$
DP: F(n): The maximum value of the subarray ending in the nth element.
Quicksort with customized compare function
Binary Search
Find first L greater than or equal to newInternal[0] from intervals[n][1]
Find first R greater than newInternal[1] from intervals[n][0]
Insert from L before R
If L less than R, newInternal will merge element
0058 - Length of last word 0060 - Permutation sequence
Transform index 1...k to 0...K
result[n] is candidates[K // factorial(len(candidates) - 1)]
$K_{n+1} = K_n \mod {factorial\left[len\left(candidates\right) - 1\right]}$
Circle and break
Mod length of list
Combination(n, k)
Calculating factorial may overflow
Multiply then divide to avoid overflow
Divided from small to large to ensure divisible
Reverse array
[Golang] func reverse(input []int) []int
0068 - Text Justification
[Golang] bytes.Buffer.Len and bytes.Bufer.WriteString
Binary search
Heron's formula
DP: F(n) = F(n - 1) - F(n - 2)
TODO: Binet's formula
0074 - Search a 2D matrix
Binary search, twice
Transform 2D to 1D, binary search once
nums[:a] are red, nums[a:b] are white, nums[c:] are bluenums[b:c] are unknown
0076 - Minimum Window Substring
Two points
Slice window
Use queue record target character
Use make and copy instead of append
0080 - Remove duplicates from sorted array II 0081 - Search in rotated sorted array II 0082 - Remove duplicates from sorted list II
Skip duplicates
Move to next node if not skip
0083 - Remove duplicates from sorted list 0084 - Largest Rectangle in Histogram
Transform to histogram
Monotonic stack
Two lists contains low and high
Combine two lists
0088 - Merge sorted array 0092 - Reverse Linked List II
Define root point to head
func reverse(head *ListNode, tail *ListNode) *ListNode revert list[head:tail]
0093 - Restore IP Addresses
Deep First Search
Not remove number 0: 010010 -> [0.10.0.10, 0.100.1.0]
[Golang]: strconv.ParseUint, strconv.FormatUint
0094 - Binary tree inorder traversal
Deep First Search
Recursion
Stack and loops
0095 - Uniqute Binary Search Tree II
Dynamic programming
$Cache(x, y)$ means BST with length y starting at x
$Cache(x, 0)$ is ${ nil }$
0096 - Unique Binary Search Trees
Dynamic programming
$F_{n+1}=\sum_{i=0}^{n} F_i \times F_{n-i}$
0097 - Interleaving String 0098 - Validate Binary Search Tree 0099 - Recover Binary Search Tree
Scan twice: from head, from tail
0102 - Binary Tree Level Order Traversal 0103 - Binary Tree Zigzag Level Order Traversal 0104 - Maximum Depth of Binary Tree 0105 - Construct Binary Tree from Preorder and Inorder Traversal
Recursion
preorder[0] is rootFind the root in array inorder, inorder[:root] is left tree, inorder[root+1:] is right tree
0106 - Construct Binary Tree from Inorder and Postorder Traversal
Recursion
postorder[len(postorder)-1] is rootFind the root in array inorder, inorder[:root] is left tree, inorder[root+1:] is right tree
0107 - Binary Tree Level Order Traversal II 0108 - Convert Sorted Array to Binary Search Tree 0109 - Convert Sorted List to Binary Search Tree 0110 - Balanced Binary Tree 0111 - Minimum Depth of Binary Tree
Recursion
NOTICE: Tree with null is not 1
0114 - Flatten Binary Tree to Linked List 0115 - Distinct Subsequences 0116 - Populating Next Right Pointers in Each Node
Recursion
Connect right of left subtree to the left of right subtree
Continue recursivly to left and right subtree, util tree is nil
0117 - Populating Next Right Pointers in Each Node II
Recursion
Calculate subtrees
Get the rightest point from root.Left via .Next
0119 - Pascal's Triangle II 0121 - Best Time to Buy and Sell Stock
Dynamtic Programing
$f_i$ means the minimum in the frist i days
0122 - Best Time to Buy and Sell Stock II 0123 - Best Time to Buy and Sell Stock III
Define two slice
$F_i$ : Maximum profit when selling on day i
$F_0 = 0$ $F_i = \max(P_i - P_{i-1} + F_{i-1}, 0)$
$B_i$ : Maximum profit when buying on day i
$B_{len(P) - 1} = 0$ $B_i = \max(P_{i+1} + F_{i+1} - P_i, 0)$
Change two slice
$F_i$ : The maximum profit of transactions in the previous i days
$F_i = \max(F_{i-1}, F_i), i > 0$
$B_i$ : The maximum profit of transactions in the next i days
$B_i = \max(B_{i+1}, B_i), i < len(P) - 1$
Max profit: $\max \limits_{i=0}^{len(P)-1} F_i + B_i$
0124 - Binary Tree Maximum Path Sum
Recursion
Update Node.Val to the maximum path starting from Node
maxPathSum(Node) is the maximum of:
maxPathSum(Node.Left)maxPathSum(Node.Right)Node.ValNode.Val + Node.Left.ValNode.Val + Node.Right.ValNode.Val + Node.Left.Val + Node.Right.Val
0128 - Longest Consecutive Sequence
Use map to store endpoint and phase to the other endpoint
0129 - Sum Root to Leaf Numbers 0130 - Surrounded Regions
Deep First Search
Mark 'O' from bounds
Change unmarked 'O' to 'X'
0131 - Palindrome Partitioning
Breadth First Search
Use Squeue store nodes to be copied
Use Map to store old node to new node
Generate array R, $R_i$ means relative gas in tank when the car arrive next gas station
R[i] = R[i] + R[i - 1], means the i th gas station is last, relative gas in tank against starting.
Traversal once
Two points, traversal equal, increase and decrease then loop
The peek is the max of increase and decrease parts
Exclusive Or
Twice = nothing
It is not necessary to record what numbers not single
Use 2 bit record the number of occurrences of 1: 00, 01, 10
Use Karnaugh map to facilitate the simplification of Boolean algebra
0138 - Copy List with Random Pointer
Use Map to store old node to new node
Dynamic Programming
Store cache
Two points: slow and fast
0142 - Linked List Cycle II
Three points: x1, x2, x3 speed
When x2 == x3, The distance x1 travelsal is equal to the length of the cycle
Create another point st from head, move st and x1 until st == x1
Traversal once
Use Stack record second half
0144 - Binary Tree Preorder Traversal 0145 - Binary Tree Postorder Traversal 0147 - Insertion Sort List
Use point cur.Next traversal list
if cur.Val less than or equal to cur.Next.Val, move cur to next.
If cur.Next.Val is less than or equal to head.Val, move cur.Next to the head of list.
Use point pos.Next traversal list until cur.Next
if pos.Next.Val is less than cur.Next.Val, move pos to next, else insert cur.Next after pos.
0149 - Max Points on a Line
Compare lines between two points
Use 2 int number instead 1 float to store slope
Two differ 180 degree are same
Calculate same points
0150 - Evaluate Reverse Polish Notation 0151 - Reverse Words in a String
Use slice store words
Use bytes.Buffer store string
[Golang]: strings.Fields, strings.Join
0152 - Maximum Product Subarray
Dynamic Programming
Record maximum and minimum
0153 - Find Minimum in Rotated Sorted Array 0154 - Find Minimum in Rotated Sorted Array II
Binary Search: pivot
Head is equal to tail
Use sorted list store elements
0160 - Intersection of Two Linked Lists 0165 - Compare Version Numbers 0166 - Fraction to Recurring Decimal
Integer
Finite decimal
Recurring decimal
Nagtive
0167 - Two Sum II - Input array is sorted 0168 - Excel Sheet Column Title 0171 - Excel Sheet Column Number 0172 - Factorial Trailing Zeroes 0173 - Binary Search Tree Iterator
Dynamic Programming
Check health point is over 0 all the time
Sort numbers
Generate two numbers ab and ba from a and b
Compare ab and ba
If ab is less than or equal to ba, a less b
Revers numbers
Combine numbers to string
If string only contains 0, return 0
0187 - Repeated DNA Sequences
Use map to store sequence status
0: not exists
1: unique
2: duplicated
Hash function, string -> uint32
'A': 0
'C': 1
'G': 2
'T': 3
Rotate hash function, caluate hash of s[i+1:i+11] from s[i:i+10]
Rotate k elements, one time
Dynamic Programming
$F(x) = max(F(x-2) + nums_x, F(x-1))$
0199 - Binary Tree Right Side View
Full adder
[Golang] Create array via make([]int, n)
[Golang] Combine bytes to string via types.Buffer
Buffer.WriteByte: Write byte to endBuffer.String: Get as string