Reverse Words in a String
Idea: Double Reverse
Evaluate Reverse Polish Notation
Idea: Typical Last-in-First-out problem, so should use Stack
Word Break I
Idea: DP
CanBreak[i] = CanBreak[k] && word.substr(k+1, i) in the Dictionary
Word Break II
Idea: DP
Redundancy: Repeated checking all possibilities in a place
Solution: Pre-Calculate the list
Idea: Slope -> HashMap
Careful: Vertical - Same x location;
Careful: Same Location: Repeated node;
Sort List
Idea: Merge Sort O(nlgn) and Constant Space
Careful: define new head node when merging;
Insertion Sort List
Idea: find the location from the head and always keep its previous node;
LRU Cache
Idea: hashmap + list
get: O(1) need a Hashmap<key, Object*>
Also, need to insert to front of the list;
set: O(1) need a Hashmap and then add to top or re-insert to top;
Binary Tree Postorder Traversal
Idea: Magic two-stacks version
Or
Idea: one-Stack-prev-curr version
Binary Tree Preorder Traversal
Idea: Stack + Right-First-In-Stack
Binary Tree Inorder Traversal
Idea: Code attached.
while(current != NULL || mystack.empty() == false) {
if(current != NULL) {
mystack.push(current);
current = current -> left;
}
else {
printf("%d,", mystack.top()->key);
current = mystack.top() -> right;
mystack.pop();
}
}
Reorder List
Idea: partial re-order and then merge lists
Linked List Cycle I && II
Idea: fast-slow traversal algorithms
Copy List with Random Pointer
Idea: std::unordered_map<RandomListNode*, RandomListNode*> a_hash_map
Single Number I
Idea: Feature of bitwise operation XOR: cancel each other
Single Number II
Idea: Count and check the sum of each bit % 3, is 0 or not?
If Yes, the missing number has 0 in the location, If No, set the location as 1. like: n = n | (1 << l)
Idea: Two-round Scanning and Double-check correctness
Gas Station
Idea: Greedy Search the first location until the sum to end is always positive
Clone Graph
Idea: std::unordered_map<RandomListNode*, RandomListNode*> a_hash_map
Palindrome Partitioning
Idea: DP & Pre-Calculating Post-ward Palindrome Array
Palindrome Partitioning II
Idea: Same with I but keep a updated parameter
Surrounded Regions
Idea: Queue & O -> Y firstly and then O -> X && Y -> O;
Idea: Recursive Method
Longest Consecutive Sequence
Idea: std::unordered_set & check surrounding
Word Ladder
Idea: shortest path
Word Ladder II
Idea: output all paths (loops processing) + std::unordered_set<bool> processed
Valid Palindrome
Idea: Clean String and Scan
Best Time to Buy and Sell Stock
Idea: maintain the min value and max profit
Best Time to Buy and Sell Stock II
Idea: Aggregate all benefits
Best Time to Buy and Sell Stock III
Idea: DP and two-round scan
Triangle
Idea: Recursive Algorithm and re-used vector (Too Costly)
Idea: Post-Order Scan
Pascal's Triangle I & II
Idea: Purely Logic, no complex algorithm
Populating Next Right Pointers in Each Node I & II
Idea: BFS, level by level processing; Instead of using transitional queues, use pointers and next;
Flatten Binary Tree to Linked List
Idea: Post-order processing and connect left to right
Path Sum I & II
Idea: Recursive Algorithm
Minimum Depth of Binary Tree
Idea: Recursive Algorithm and Cut Branch
Balanced Binary Tree
Idea: Recursive Get Height and Compare. (BFS, DFS [P/I/P-order] are mostly enough)
Convert Sorted Array to Binary Search Tree
Idea: Recursively find the middle and new a node;
Convert Sorted List to Binary Search Tree
Idea: Build a BSF with N nodes and then set the value using In-order traversal method
Binary Tree Level Order Traversal I && II
Idea: use two-queue method; Reverse the vector in the end;
Construct Binary Tree from Inorder and Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
Idea: Recursive Method and HashTable for seaching locations
Construct Binary Tree from given preorder and postorder traversals
No unique tree if no more constraints.
Maximum Depth of Binary Tree
Idea: Recursive method
Binary Tree Zigzag Level Order Traversal
Idea: Two stacks + Flag: leftToRight
Symmetric Tree
Idea: Level by Level + Check Symmetric
Same Tree
Idea: Post-Order Scan
Recover Binary Search Tree
Idea:
1: In-Order Traversal -> Find the first node violating ascending order
2: Reversed In-Order Traversal -> Find the first node violating descending order
3: Swap
Interleaving String
Idea: Recursive Algorithm is too costly, for cases like:s1=aa*, b=aa*, c=aaaa**;
Idea: Use 2-D Dynamic Programming;
M[i][j] = (M[i][j-1] && b[j] == c[i+j]) || (M[i-1][j] && a[i] == c[i+j]);
Unique Binary Search Trees I && II
Idea: Recursively pick the middle node; For II, copy for each branch;
Restore IP Addresses
idea: BFS and cut branch
Reverse Linked List II
Idea: Find and Reverse, careful the border cases
Subsets I && II
Idea: Sort and then 2-level Scan
Decode Ways
Idea: BFS but careful on the special cases, 0
Merge Sorted Array
Idea: Scan the array from the back to the front
Scramble String
Idea: DFS and cut branch
Partition List
Idea: maintain a pointer to the next place to insert, like quick sort.
Maximal Rectangle
Idea: Pre-Process 2-D Matrix to keep the number of 1s in the same row before it.
Largest Rectangle in Histogram
Idea 1: Surrounding Search O(n^2)
Idea 2: Divide and Conquer O(nlgn);
Idea 3: Stack O(n)
Remove Duplicates from Sorted List I && II
Idea: Logic, no algorithms
Sort Colors
Idea 1: Counting Sort
Idea 2: Swap, but be careful on the left side and right side (different)
Search a 2D Matrix
Idea: Two Binary Search, care special cases.
Set Matrix Zeroes
Idea: Two vectors to keep the rows and cols that need to set to 0.
Climbing Stairs
Idea 1: BFS, but costly, O(2^n)
Idea 2: DP. N[n] = N[n-1] + N[n2], O(n)
Idea 3: Fibonacci Optimization Algorithm, O(lgn)
Sqrt(x)
Idea: Binary Check (min, max), careful overflow.
Plus One
Idea: addition (a, b, carry_bit), no algorithm
Add Binary
Idea: Similar to Plus One
Merge Two Sorted Lists
Idea: Logic, no algorithm
Spiral Matrix II
Idea: Spiral Scan Matrix, Each Time Scan 4 Border
Pow(x, n)
Idea: Recursive and Re-use
Rotate Image
Idea: Spiral Scan Matrix, Each Time Scan 4 Border
Permutations
Idea: swap for each possibility
First Missing Positive
idea: swap, careful special cases, duplicate values.
Count and Say
Idea: Logic, no algorithm
Remove Element
Idea: Logic, no algorithm
Remove Duplicates from Sorted Array
Idea: Similar with Remove Element
Valid Parentheses
Idea: Stack
Remove Nth Node From End of List
Idea: two-index method
3Sum & 3Sum Closest
Idea: Sort and Hash; Sort and 2-Index Scan
Longest Common Prefix
Idea: Logic, No Algorithm
Roman to Integer
Idea: Logic, No Algorithm
Regular Expression Matching
Idea: Star or not
Palindrome Number
Idea: First (%(10^Bits)) == Last (&1)
String to Integer (atoi)
Idea: Logic, Many Special Cases
Reverse Integer
Idea: Logic, care special cases, overflow and 0.
Longest Palindromic Substring
Idea: Pick any element as a center
Add Two Numbers
Idea: Logic, no algorithm
Longest Substring Without Repeating Characters
Idea: hash_map and maintain the max_length
Median of Two Sorted Arrays
Idea: Recursive Algorithm
