xuyan.nus: Coding Strategy of Leetcode

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

Max Points on a Line

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

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)

Candy

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;

Sum Root to Leaf Numbers

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