Tips on Using Eclipse Effectively

Tips on Using Eclipse Effectively

Useful Eclipse Shortcut Keys

ALT + Left/Right Arrow	Move backward/forward in the editor navigation history
CTRL+O	Show the quick outline for the editor input
CTRL+K	Find next item, no need to ctrl+f, type some words, then search
CTRL+1	Activates the quick fix
CTRL+SHIFT+T	Open Type
CTRL+SPACE	Content Assist
ALT+/	Word completion
ALR+SHIFT+R	Rename the selected element
ALT+SHIFT+M	Extract statements into a new method and use the new method
Ctrl + L	Go To Line
CTRL+T	Show quick hierarchy of the selected element
CTRL + SHIFT + F	Format code
CTRL+SHIFT+O	Organize imports
Ctrl+Shift+X	Change the selection to upper case, useful in declare final variable
Ctrl+Shift+Y	Change the selection to lower case
Ctrl+Shift+H	Open a type in the type hierarchy view
Ctrl+Shift+S	Save all current contents
Ctrl+Shift+W	Close all editors
Ctrl+Shift+G	Search for references to the selected element in the workspace
CTRL+E	Show a list of all open editors
CTRL + D	Delete row
CTRL+M	Toggle maximize/restore state of active view or editor

Others:
CTRL+SHIFT+U    Shows the Occurrences in File quick menu
Ctrl+Shift+R        Open Resources
CTRL + I               Corrects indentation
Ctrl+M                  Maximize Active View or Editor

Ctrl+Shift+Space

Context Information, If typing a method call with several parameters use this to show the applicable parameter types.
Alt+Left/Right Backward/Forward History

CTRL + I         Corrects indentation

CTL + N            Open new type wizard
CTRL + J           Incremental search
CTRL + SHIFT + L Shows you a list of your currently defined shortcut keys
CTRL+F6          Use to move between open editors
CTRL+F7          Move between views
CTRL+F8          Move between perspectives
To configure the shortcut key, click Window --> Preferences --> General --> Keys


Associate editors with file types:
Window -> Preferences -> General -> Editors -> File Associations

Delete blank line

Find: ^\s*\n
Replace with: (empty)



Eclipse plugins:
Code quality:
Checkstyle: http://eclipse-cs.sourceforge.net/update
It is used to enforce Coding Standards in Java Project, such as Naming conventions, Coding problems, Best Practices.


PMD http://pmd.sf.net/eclipse
PMD focuses more on preemptive defect detection.


FindBugs http://findbugs.cs.umd.edu/eclipse/
FindBugs concentrates on detecting potential bugs and performance issues.
Klocwork: http://developer.klocwork.com
Klocwork is aimed at improving software security, quality, and reliability. It is not free, but we can get 30 days free trail. And it is really very cool.


Mylyn: http://www.eclipse.org/mylyn/
Mylyn can integrate with issue management systems such as Bugzilla, and it also provides context management, which can hide much of the detail of projects that is irrelevant to the task at hand.
Mylyn is very helpful, especially your main job is to fix defects, or focus on one component of a big project.


ShellEd: http://sourceforge.net/projects/shelled/
EPIC - Perl Editor and IDE for Eclipse http://e-p-i-c.sf.net/updates
The PyDev Update Site http://pydev.sourceforge.net/updates/
Groovy Eclipse plugin http://dist.codehaus.org/groovy/distributions/update/
Aptana Studio http://update.aptana.com/install/studio/3.2/
http://www.aptana.com


Problem：

Recently, I re-downloaded and reinstalled jdk, and Eclipse always shows this error:
'UnsupportedEncodingException: GBK'. After google search, on http://dev.eclipse.org/newslists/news.eclipse.tools/msg30710.html,
I found out this is because I installed a JRE only for US English, and I should choose to download and install Multi-language JRE.

Problem:

When we save file, it may print out the error "Some characters can not be mapped using GBK character encoding".
The solution is to change file encoding to 'utf-8':
Select Window -> Preferences ->General
Select  Workspace , set Text file encoding to 'utf-8'.
Select Content Types, set Default encoding to 'utf-8'

Ignore white space when compare two files in Eclipse IDE
When compare two files in Eclipse, many times lines differ only in white spaces, and we don't want to notice this minor difference.
Solution:
Select Window -> Preference -> Compare/Path, and in 'General' tab, select the checkbox --'Ignore white space'.


Reference:
http://www.javaprogrammingforums.com/eclipse/19-useful-eclipse-shortcut-keys.html
http://www.rossenstoyanchev.org/write/prog/eclipse/eclipse3.html
http://tkramar.blogspot.com/search/label/eclipse
Java Power tools safari online book

Advanced Data Structures

PriorityQueue
- Related with greedy algorithm
- Use minQueue to get kth max, maxQueue to get kth min
- merge sort with PQ

Misc
- Remove is O(n)

LeetCode 414 - Third Maximum Number
- Use PriorityQueue with HashSet to check duplicate
https://discuss.leetcode.com/topic/63086/java-priorityqueue-o-n-o-1
- TreeSet (not PQ as need call contains)
set.add(num);
if(set.size() > 3) {set.remove(set.first());}
- Maitain state: first, second, third

LeetCode 502 - IPO
find a project with max profit and within current capital capability
- 2 PriorityQueue

        PriorityQueue<int[]> pqCap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        PriorityQueue<int[]> pqPro  = new PriorityQueue<>((a, b) -> (b[1] - a[1]));        
        for (int i = 0; i < k; i++) {
            while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
                pqPro.add(pqCap.poll());
            }
            W += pqPro.poll()[1];
        }

LeetCode 632 - Smallest Range


LeetCode 630 - Course Schedule III
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dthday. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses,(a,b)->a[1]-b[1]); //Sort the courses by their deadlines (Greedy! We have to deal with courses with early deadlines first)
        PriorityQueue pq=new PriorityQueue<>((a,b)->b-a);
        int time=0;
        for (int[] c:courses) 
        {
            time+=c[0]; // add current course to a priority queue
            pq.add(c[0]);
            if (time>c[1]) time-=pq.poll(); //If time exceeds, drop the previous course which costs the most time. (That must be the best choice!)
        }        
        return pq.size();
    }

LeetCode 378 - Kth Smallest Element in a Sorted Matrix
- Bisection O(nlogm) while m = max - min
https://discuss.leetcode.com/topic/52868/java-heap-klog-k

    public int kthSmallest(final int[][] matrix, int k) {
        int c = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>(
            k, (o1, o2) -> matrix[o1[0]][o1[1]] - matrix[o2[0]][o2[1]]);
        queue.offer(new int[] {0, 0});
        while (true) {
            int[] pair = queue.poll();
            if (++c == k) {
                return matrix[pair[0]][pair[1]];
            }
            if (pair[0] == 0 && pair[1] + 1 < matrix[0].length) {
                queue.offer(new int[] {0, pair[1] + 1});
            }
            if (pair[0] + 1 < matrix.length) {
                queue.offer(new int[] {pair[0] + 1, pair[1]});
            }
        }

LeetCode 373 - Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Find elements more than K times
Given m sorted lists, find out the elements more than k times. If an element appear more than once in a list, count it only once.
- Use PriorityQueue instead of HashMap to save space

POJ 4302 Holedox Eating
- 2 PriorityQueue

LeetCode 621 - Task Scheduler
- Use Priority Queue
- Calculating Idle slots
LeetCode 358 - Rearrange String k Distance Apart

Rearrange Characters in String With No Adjacent Duplicate Characters

LeetCode 632 - Smallest Range
You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the klists.
- Merge k sorted list

LeetCode 407 - Trapping Rain Water II

Queue
Double Monotonic Queue

Deque q = new ArrayDeque<>();
Deque doubleQueue = new LinkedList<>();

LeetCode 239 - Sliding Window Maximum
- Store index instead of the value
- Only keep promising elements in the deque

LeetCode 102 - Binary Tree Level Order Traversal
queue.offer(root);
while(!queue.isEmpty()){
  for(int i=0; i}

LeetCode 127 - Word Ladder I
- BFS, Two-end BFS
Deque queue = new ArrayDeque();
queue.offer(start);
Set visited

LeetCode 111 - Minimum Depth of Binary Tree

Interval tree
http://www.davismol.net/2016/02/07/data-structures-augmented-interval-tree-to-search-for-interval-overlapping/
- augmented self-balancing bst: low, high, max
- logn: add/Remove(interval), overlapping(x)

Google – Toggle Problem
https://reeestart.wordpress.com/2016/06/24/google-toggle-problem/

Using Multiple Data Structures 
Google – Manager Peer Problem
- Tree + Hash Table
Map nodeMap
private class TNode {
  int val;
  TNode parent;
  List neighbors;
}

Design a data structure that supports insert, delete, search and getRandom in constant time
//A hash where keys are array elements and vlaues are ndexes in arr[]
HashMap  hash;
ArrayList arr;

LeetCode 432 - All O`one Data Structure
Inc(Key), Dec(Key), GetMaxKey(), GetMinKey()

    private Bucket head;
    private Bucket tail;
    // for accessing a specific Bucket among the Bucket list in O(1) time
    private Map countBucketMap;
    // keep track of count of keys
    private Map keyCountMap; or the value can be Bucket
    // each Bucket contains all the keys with the same count
    private class Bucket {
        int count;
        Set keySet;
        Bucket next, prev;
    }

LeetCode - LRU Cache

    private int capacity;
    private HashMap hs = new HashMap();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        if( !hs.containsKey(key)) {
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);

        return hs.get(key).value;
    }

    public void set(int key, int value) {
        // this internal `get` method will update the key's position in the linked list.
        if (get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {
            hs.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);
        hs.put(key, insert);
        move_to_tail(insert);
    }

    private void move_to_tail(Node current) {
        current.prev = tail.prev;
        tail.prev = current;
        current.prev.next = current;
        current.next = tail;
    }

LeetCode 460 - LFU Cache
when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
- Doubly Linked List + HashMap

    private Node head = null;
    private int cap = 0;
    private HashMap valueHash = null;
    private HashMap nodeHash = null;

Design Phone Directory
isTaken(String phone) takeNumber(String phone) giveMeANumber()
- Trie

Stock Ticker

1. void addOrUpdate(String stock, double price) add or update the price of a stock to the data structure.
2. List return the top k price stocks and their current prices.

- HashMap contains all elements, MinHeap or TreeSet contains top(k)

Sparse Matrix
Implementing Stack using priority queue.
- assign priority to the elements that are being pushed

TimeTravelingHashTable
* insert(key, value, timestamp)
* get(key, timestamp)
//> = =
HashMap> map = new HashMap<>();


Design a stack with operations on middle element
- push, pop
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element.
- Doubly Linked List

Min Stack

Algorithm Problems Practices

logn
- bisection
- divide and conquer

X. DP
O(1) space - in place, reuse the input
-- multiple dp relations
- find sub-problems and relations

- dp: [i, j]; or dp[len-1] just start/or end

always think whether there is dp solution
dp[i] dp[i-1]
dp[i]  dp[j] 0<j<i
[], [][], or map

X. Kadane's algorithm

- dp, two pointers, scan, track and update local that includes a[i]

LeetCode 53 - Maximum Subarray

1. https://discuss.leetcode.com/topic/5000/accepted-o-n-solution-in-java

2. dp: dp(A, i) = dp(A, i - 1) > 0 ? dp(A, i - 1) : 0 + A[i];

https://discuss.leetcode.com/topic/6413/dp-solution-some-thoughts/2

the maxSubArray for A[0:i ] which must has A[i] as the end element

3. Divide and Conquer - nlogn

https://discuss.leetcode.com/topic/42213/my-divide-and-conquer-solution-in-java-under-instruction-of-clrs-o-nlogn

Maximum circular subarray sum

- one pass https://discuss.leetcode.com/topic/42213/my-divide-and-conquer-solution-in-java-under-instruction-of-clrs-o-nlogn

Max sum subsequence with non-consecutive elements

http://www.zrzahid.com/max-sum-subsequqnce-with-non-consecutive-elements/

max_including(i) = max{max_excluding(i-1)+a[i], a[i]}

max_excluding(i) = max{max_including(i-1), max_excluding(i-1)}

Maximum Product Subarray

localMax, localMin, if(a[i] > 0) else

http://www.geeksforgeeks.org/maximize-number-0s-flipping-subarray/

find the maximum number zeros in an array with one flip of a subarray allowed. A flip operation switches all 0s to 1s and 1s to 0s.

http://www.geeksforgeeks.org/maximize-number-0s-flipping-subarray

find maximum number of set bits after flipping a single contagious segment of bits

https://miafish.wordpress.com/2015/08/10/find-number-of-bits-to-be-flipped-to-get-maximum-1s-in-array/

X. Knapsack
LeetCode 416 - Partition Equal Subset Sum
1. dp[target+1] or [nums.length+1][target+1]
dp[j] = dp[j] || dp[j - nums[i]]
https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand

X. DP

LintCode - Copy Books

LeetCode 474 - Ones and Zeroes
dp = new int[m + 1][n + 1];
dp[i][j] = Math.max(1 + dp[i-count[0]][j-count[1]], dp[i][j]);

LeetCode 446 - Arithmetic Slices II - Subsequence
- HashMap<Integer, Integer>[] dp
map[i].put(diff, map[i].get(diff)) + map[j].get(diff)) + 1);

LeetCode 375 - Wiggle Subsequence - link
return the length of the longest subsequence that is a wiggle sequence
up[i] - considering i​th element as the last element of the wiggle subsequence and ending with a rising wiggle.
down[i]
if nums[i] > nums[i-1] up[i] = down[i-1]+1 down[i]=down[i-1]
else if nums[i] < nums[i-1]  down[i]=up[i-1]+1 up[i] = up[i-1]
else down[i]= down[i-1] up[i] = up[i-1]
-- space optimization, only use up and down
2. Greedy

Leetcode 44 - Wildcard Matching

with support for '?' and '*'.
dp[s.length() + 1][p.length() + 1]
dp[i[j]: the first i characters in string s matches the first characters of string p.
dp[0][0] = true;
dp[i][0] = false;
dp[0][j] = dp [0][j - 1] if p.charAt(j - 1) == '*'
-- If p.charAt(j - 1) != '*', then dp[i][j] = dp[i - 1][j - 1] if s.charAt(i) == p.charAt(j) || p.charAt(j) == '?' (else false)
-- If p.charAt(j - 1) == '*', then
-- dp[i][j]
     = dp[i][j - 1] || // Match 0 character
     = dp[i - 1][j] // Match any sequence of characters
O(n) space - https://discuss.leetcode.com/topic/10794/my-java-dp-solution

LeetCode 10 - Regular Expression Matching: . and *
'*' Matches zero or more of the preceding element.
- DFS+Cache: dp[i][j] or DP
https://discuss.leetcode.com/topic/40371/easy-dp-java-solution-with-detailed-explanation
https://discuss.leetcode.com/topic/31974/java-4ms-dp-solution-with-o-n-2-time-and-o-n-space-beats-95

1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:
               1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
               2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                              dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
                           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty

Leetcode 139 - Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
1. DP: O(n^2)
Get words minLen, maxLen
boolean [] dp = new boolean[n+1];
dp[0] = true ;
dp[i] = dp[j] && dict.contains(sentences.subString(j,i)) 0<j<i

// Use trie to check whether subString is a word
2. DFS + Cache
3. BFS:

Word Break II
https://leetcode.com/discuss/91894/java-6ms-simple-solution-beating-88%25
http://www.jiuzhang.com/solutions/word-break-ii/
- avoid to use substring
boolean[][] isWord
boolean[] possible

LeetCode 287 - Perfect Squares
dp(i) = min{1+dp(i-j*j)}
https://discuss.leetcode.com/topic/26400/an-easy-understanding-dp-solution-in-java
bfs -  q.offer(0); visited.add(0);
https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics

https://discuss.leetcode.com/topic/2545/a-solution-using-bfs/6
The vertices of the graph are simply the positions of the first characters of the words and each edge actually represents a word

Lintcode: K Sum I
http://www.cnblogs.com/yuzhangcmu/p/4279676.html
int[][][] D = new int[len + 1][k + 1][target + 1];
D[i][j][t] = D[i - 1][j][t];
if (t - A[i - 1] >= 0) {
    D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]];
}

space op: int[][] D = new int[k + 1][target + 1];

Lintcode: k Sum II
- DFS

LeetCode 97 - Interleaving String
dp[i][j]  =
str3.charAt(i + j) == str1.charAt(i) && dp[ i - 1][j] ||
str3.charAt(i + j) == str2.charAt(j) && dp[i][j - 1]

LeetCode 132 - Palindrome Partitioning II
http://happycoding2010.blogspot.com/2015/10/leetcode-132-palindrome-partitioning-ii.html
Return the minimum cuts needed for a palindrome partitioning of s
isPal[i][j] store if s[i..j] is palindrome or not. res[j] is the min cut of s[0..j].

LeetCode 241 - Different Ways to Add Parentheses
DP: https://discuss.leetcode.com/topic/26076/java-recursive-9ms-and-dp-4ms-solution
- split string first
- dp[i][j] stores all possible results from the i-th integer to the j-th integer (inclusive)
- ArrayList<Integer>[][] dp
DFS: divide and conquer + cache
https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms/12

LeetCode 446 - Arithmetic Slices II - Subsequence

https://discuss.leetcode.com/topic/67413/detailed-explanation-for-java-o-n-2-solution

T(i, d) = summation of (1 + T(j, d)) as long as 0 <= j < i && d == A[i] - A[j]

Map<Integer, Integer>[] map = new Map[A.length];

LintCode 395 - Coins in a Line II

dp[i] means the largest value you(the first player) can get when you start from values[i]

dp[i] = values[i] + Math.min(dp[i+2], dp[i+3]);

dp[i] = Math.max(dp[i], values[i] + values[i+1] + Math.min(dp[i+3], dp[i+4]));

LeetCode 73 - Unique Paths II
if some obstacles are added to the grids. How many unique paths would there be
dp[i][j] = dp[i−1][j]+dp[i][j−1] if grid[i][j]=0
O(1) space - in place, reuse the input
https://discuss.leetcode.com/topic/4987/java-solution-using-dynamic-programming-o-1-space
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
if(obstacleGrid[i][j] == 1)
    obstacleGrid[i][j] = 0;

LeetCode 72 - Edit Distance
f(i, j) = f(i - 1, j - 1)
f(i, j) = 1 + min { f(i, j - 1), f(i - 1, j), f(i - 1, j - 1) }

LeetCode - 403 Frog Jump
DP https://discuss.leetcode.com/topic/59423/simple-easy-to-understand-java-solution
map = new HashMap≪Integer, HashSet≪Integer>>(stones.length);
List≪HashSet≪Integer>> dp
DFS + cache
https://discuss.leetcode.com/topic/59439/straight-forward-9ms-7-line-c-solution-with-explanation

LeetCode 97 - Interleaving String
1. DP:
dp[0][0] = true;
dp[0][j] = str3.charAt(j) == str2.charAt(j)
dp[i][0] = str3.charAt(i) == str1.charAt(i)
2. BFS
https://discuss.leetcode.com/topic/6562/8ms-c-solution-using-bfs-with-explanation

X. BFS
When to use?
- to find minimum steps
- two-end BFS, multi-end bfs
- BFS + PriorityQueue

LeetCode 417 - Pacific Atlantic Water Flow
bfs or dfs
https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean
if (pacific[i][j] && atlantic[i][j]) res.add(new int[] {i, j});

LeetCode - Word Ladder I
find the length of shortest transformation sequence from start to end
Two-end BFS
https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms
beginSet.add(beginWord);
endSet.add(endWord);
HashSet≪String> visited
if (beginSet.size() > endSet.size()) beginSet, endSet = endSet, beginSet;
if (endSet.contains(target)) return len + 1;

LeetCode Word Ladder II
https://discuss.leetcode.com/topic/17975/super-fast-java-solution-two-end-bfs
http://www.jiuzhang.com/solutions/word-ladder-ii/
http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/
LinkedList≪WordNode> queue
https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj
Map≪String,List≪String>> map: key is a word, the list is the word's pre words.
or:
unvisited = new HashSet≪String>(dict);
visited = new HashSet≪String>();

unvisited.removeAll(visited);
visited.clear();

LeetCode 407 - Trapping Rain Water II
https://discuss.leetcode.com/topic/60418/java-solution-using-priorityqueue
BFS + PriorityQueue

LeetCode [317] Shortest Distance from All Buildings

- do not go into a land, if it is not accessible by at least one of previous buildings.

https://discuss.leetcode.com/topic/32391/share-a-java-implement

https://discuss.leetcode.com/topic/31925/java-solution-with-explanation-and-time-complexity-analysis

LeetCode 286 - Walls and Gates

Fill each empty room with the distance to its nearest gate.

- Multi end bfs - O(n^2)

- Naive BFS or dfs - O(n^4)

https://leetcode.com/discuss/82264/benchmarks-of-dfs-and-bfs

LeetCode 433 - Minimum Genetic Mutation
https://discuss.leetcode.com/topic/65780/java-solution-using-bfs

Leetcode 200: Find the number of islands
- bfs, dfs, union-find
- number of lakes
- different shapes of number Island
http://www.1point3acres.com/bbs/thread-175393-1-1.html

LeetCode 247 - Strobogrammatic Number II
Find all strobogrammatic numbers that are of length = n.
- Use char[] to avoid string concatenation
iterative, bfs - https://discuss.leetcode.com/topic/28990/simple-java-solution-without-recursion
dfs - https://discuss.leetcode.com/topic/21579/accepted-java-solution-using-recursion
https://discuss.leetcode.com/topic/20733/my-concise-java-solution-using-dfs
public void findStrobogrammaticHelper(List res, char[] a, int l, int r)

LeetCode 248 - Strobogrammatic Number III
Count the total strobogrammatic numbers that exist in the range of low <= num <= high
https://discuss.leetcode.com/topic/44718/java-1ms-solution-with-comments-in-the-code

X. DFS
- Backtrack: don't forget to clear state
- dfs+cache
LeetCode 247 - Strobogrammatic Number II
Find all strobogrammatic numbers that are of length = n.
iterative, bfs - https://discuss.leetcode.com/topic/28990/simple-java-solution-without-recursion
Use char[] to avoid string concatenation
dfs - https://discuss.leetcode.com/topic/21579/accepted-java-solution-using-recursion
https://discuss.leetcode.com/topic/20733/my-concise-java-solution-using-dfs
public void findStrobogrammaticHelper(List<String> res, char[] a, int l, int r)

LeetCode 248 - Strobogrammatic Number III
Count the total strobogrammatic numbers that exist in the range of low <= num <= high
https://discuss.leetcode.com/topic/44718/java-1ms-solution-with-comments-in-the-code
if (i== low_len || i== high_len) strobogrammaticInRangeSameDigits(i, 0, i-1, 0); else strobogrammaticDigit+=counts(i,i);

LeetCode 212 - Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

- dfs + trie
https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00/
- pass TrieNode

LeetCode 395 - Longest Substring with At Least K Repeating Characters
- split by badChars and dfs
https://tech.liuchao.me/2016/09/leetcode-solution-395/
https://discuss.leetcode.com/topic/57265/java-d-c-solution

Leetcode 291 Word Pattern II
Map<Character, String> forwardMap, invertedMap

LeetCode124 - Word Search
find if the word exists in the grid
https://discuss.leetcode.com/topic/7907/accepted-very-short-java-solution-no-additional-space/39

LeetCode 22 – Generate Parentheses
generate all combinations of well-formed parentheses.
helper(List res, StringBuilder sb, int open, int close, int n)
DFS: https://discuss.leetcode.com/topic/5866/my-accepted-java-solution
-- dfs(ArrayList<String> result, String s, int left, int right)
DFS+cache
https://discuss.leetcode.com/topic/33127/java-easy-to-understand-recursive-dp-method-with-explanations/
helper(int n, List<String>[] lists)

BSF, DP
f(n) = (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0)
https://discuss.leetcode.com/topic/3474/an-iterative-method

LeetCode 320 - Generalized Abbreviation
DFS/Backtracking
https://discuss.leetcode.com/topic/32765/java-14ms-beats-100
Divide &Conquer
Bit String/Mark
- 2^n combinations

LeetCode 329. Longest Increasing Path in a Matrix

- DFS+Cache: dfs(int[][] matrix, int i, int j, int[][] memo)

LeetCode 267 - Palindrome Permutation II

https://discuss.leetcode.com/topic/22214/ac-java-solution-with-explanation

void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> res)

private void helper(char[] array, List<String> result, Map<Character, Integer> map, int left, int right)

LeetCode - Subsets

DFS: https://discuss.leetcode.com/topic/10885/java-subsets-solution

2. BFS: https://discuss.leetcode.com/topic/30867/simple-iteration-no-recursion-no-twiddling-explanation/2

res = new ArrayList<List>();

3. bit string

Math.pow(2, n)

if (((1 << j) & i) != 0) subset.add(nums[j]);

LeetCode 46 - Permutations

LeetCode 47 - Permutations II

if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;

https://discuss.leetcode.com/topic/37030/java-iterative-solution-no-set-needed

Google interview - max vacation days
Google – Get Some Beer
https://reeestart.wordpress.com/2016/06/28/google-get-some-beer/

X. Divide and Conquer
- subproblems
LeetCode 50 - Pow(x, n)
Google – Power Sum
return sum of n^0 + n^1 + … + n^n.
https://reeestart.wordpress.com/2016/06/10/google-power-sum/

X. merge sort
need one extra array - no need to create tmp array every time
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/code/MergeSort.java
void merge(Comparable[ ] a, Comparable[ ] tmp, int left, int right, int rightEnd )

LeetCode 218 - The Skyline Problem
LeetCode 315 - Count of Smaller Numbers After Self
LeetCode 327 - Count of Range Sum

Count Inversions in an array

https://github.com/epibook/epibook.github.io/blob/master/static/solutions/java/src/main/java/com/epi/CountInversions.java

Number of swaps to sort when only adjacent swapping allowed

http://www.geeksforgeeks.org/number-swaps-sort-adjacent-swapping-allowed/

Maximum Sum Path in Two Arrays

http://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/

result += max(sum1, sum2); sum1=sum2=0;

Merge k sorted array

Find a permutation that causes worst case of Merge Sort

http://www.geeksforgeeks.org/find-a-permutation-that-causes-worst-case-of-merge-sort/

X. Quick sort/select
LeetCode 215 - Kth Largest Element in an Array
LeetCode 148 - Sort List
quick sort - partition, sort, concat
merge sort - findMiddle sort left/right, merge
http://www.chenguanghe.com/quicksort-for-linklist/

X. Slide Window
LeetCode 424 - Longest Repeating Character Replacement
you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters
https://discuss.leetcode.com/topic/63494/java-12-lines-o-n-sliding-window-solution-with-explanation
https://discuss.leetcode.com/topic/63471/java-sliding-window-easy-to-understand
(length of substring - number of times of the maximum occurring character in the substring) <= k
if(count(ch) > k){  ch[str[j] - 'A']--; break; }

LeetCode 30 - Substring with Concatenation of All Words
https://discuss.leetcode.com/topic/6617/an-o-n-solution-with-detailed-explanation/11
countMap, curMap, foundCount,
toFindMap, foundMap
O(KN)
2. trie

LeetCode 3 - Longest Substring Without Repeating Characters
https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation/
HashMap<Character, Integer> map - chracter -> last position
if (map.containsKey(s.charAt(i))) start = Math.max(start,map.get(s.charAt(i))+1);

LeetCode 340 - Longest Substring with At Most K Distinct Characters
https://discuss.leetcode.com/topic/41671/15-lines-java-solution-using-slide-window
follow up - stream
https://discuss.leetcode.com/topic/48827/java-o-nlogk-using-treemap-to-keep-last-occurrence-interview-follow-up-question

LeetCode 438 - Find All Anagrams in a String
- map = new int[256]; int count

LeetCode 67 - Minimum Window Substring
Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n).
https://leetcode.com/discuss/90376/o-n-5ms-java-solution-beats-93-18%25
Map<Character, Integer> needToFill, hasFound

http://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized


X. Two pointers
3Sum
- presort, O(N^2)
- how to avoid duplicate results
https://discuss.leetcode.com/topic/28857/easiest-java-solution

3Sum Smaller
https://discuss.leetcode.com/topic/23421/simple-and-easy-understanding-o-n-2-java-solution
nums[i] + nums[j] + nums[k] < target
count += right-left;

3Sum Closest
if (sum <= target) j++; else k--;

X. Trie
- use trie so no need to scan every candidate(O(n))
LeetCode 421 - Maximum XOR of Two Numbers in an Array
- use bit trie for int
- children = new Trie[2];
https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
2. 32n
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
if(set.contains(tmp ^ prefix)) max = tmp;

LeetCode 212 - Word Search II

logN related
X. Binary search/BiSection
- use bisection when it's difficult to find correct value, but easy to verify whether a value is correct
- split to half
LeetCode 222 -  Count Complete Tree Nodes
O(log(n)^2) https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2

LeetCode 287 - Find the Duplicate Number
1. nlogn - binary search/bisection
https://discuss.leetcode.com/topic/25580/two-solutions-with-explanation-o-nlog-n-and-o-n-time-o-1-space-without-changing-the-input-array/2
2. O(n)
- graph: index -> as graph
- find cycle in linkedlist
http://keithschwarz.com/interesting/code/?dir=find-duplicate
https://discuss.leetcode.com/topic/18864/simple-java-solution-in-o-n-without-extra-space
3. 32n
https://discuss.leetcode.com/topic/38493/o-32-n-solution-using-bit-manipulation-in-10-lines

LeetCode 410 - Split Array Largest Sum
minimize the largest sum among these m subarrays.
bisection - https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java

LeetCode 287 - Find the Duplicate Number
1. bisection - long*n
https://discuss.leetcode.com/topic/25580/two-solutions-with-explanation-o-nlog-n-and-o-n-time-o-1-space-without-changing-the-input-array
2. O(n)
- index->value graph subproblem
- find cycle in linkedlist
http://keithschwarz.com/interesting/code/?dir=find-duplicate
https://discuss.leetcode.com/topic/25685/java-o-n-time-and-o-1-space-solution-similar-to-find-loop-in-linkedlist

LintCode - Copy Books
Divide A into k or fewer partitions, such that the maximum sum over all the partitions is minimized.
http://sidbai.github.io/2015/07/25/Copy-Books/
http://www.geeksforgeeks.org/find-minimum-time-to-finish-all-jobs-with-given-constraints/
K people to copy books with different pages, return the number of smallest minutes need to copy all the books.
1. dp - minutes[i][j] = min( max( minutes[i-1][t], sum(t+1, j) )
- O(n^2 * k)
2. dp - O(n * k)
3. bisection - nlg(sum/k)
https://github.com/iFighting/Lintcode/blob/master/Java/Copy-Books.java

Codility: Lesson 12 Min Max Division
https://codility.com/programmers/lessons/14-binary_search_algorithm/
int left = max, right = sum;

Jobdu-1534
kth sum pairs from array a and b
http://www.acmerblog.com/offer-google-2-1173.html

X. Using Binary search tree
LeetCode 327 - Count of Range Sum
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.

1. Merge Sort

2. Binary search tree

https://discuss.leetcode.com/topic/34107/java-bst-solution-averagely-o-nlogn

private class TreeNode {

    long val = 0;

    int count = 1;

    int leftSize = 0;

    int rightSize = 0;

    TreeNode left = null;

    TreeNode right = null;

    countSmaller(TreeNode root, long val)

    countLarger(TreeNode root, long val)

    private int rangeSize(TreeNode root, long lower, long upper) {

        int total = root.count + root.leftSize + root.rightSize;

        int smaller = countSmaller(root, lower);    // Exclude everything smaller than lower

        int larger = countLarger(root, upper);      // Exclude everything larger than upper

        return total - smaller - larger;

    }

}

for(int i = 1; i < sums.length; i++) {

    output += rangeSize(root, sums[i] - upper, sums[i] - lower);

    insert(root, sums[i]);

}

LeetCode 315 - Count of Smaller Numbers After Self
1. Binary search tree
https://leetcode.com/discuss/73762/9ms-short-java-bst-solution-get-answer-when-building-bst
class TreeNode{
    int smallerCount;
    int val;
    TreeNode left;
    TreeNode right;
}
2. Merge sort
http://algobox.org/count-of-smaller-numbers-after-self/
class Tuple {
    public int val;
    public int idx;
}
3. Use TreeSet
https://discuss.leetcode.com/topic/31422/easiest-java-solution/12

Binary search
LeetCode 153 - Find the minimum element in a sorted and rotated array

https://leetcode.com/discuss/32675/very-simple-java-binary-search

https://leetcode.com/discuss/45611/7-line-o-logn-solution

mid = low + (high - low) / 2;

Compare num[mid] with num[high]

LeetCode 33 - Searching an Element in a Rotated Sorted Array

https://discuss.leetcode.com/topic/7711/revised-binary-search

LeetCode 162 - Find Peak Element: num[i] ≠ num[i+1]
- Compare mid with mid+1
nums[left - 1] < nums[left] && nums[right] > nums[right + 1]
while (right - left > 1) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < nums[mid + 1]) {
        left = mid + 1;
    } else {
        right = mid;
    }
}
return (left == N - 1 || nums[left] > nums[left + 1]) ? left : right;

Bisection
Given a result, it is easy to test whether it is valid or not.
LeetCode 410 - Split Array Largest Sum

- binary(nums, m, sum, max);

LeetCode 367 - Valid Perfect Square

X. Interval
- First sort these intervals somehow
- Think as different events - start, end
- sort interval + greedy
- merge interval

LeetCode 218 - The Skyline Problem
- (start/end, height) tuple, set the start segment as negative height or Edge:(x, height, isStart)
- sort interval
- TreeMap<Integer, Integer> heightMap: key is the height, value is the count
- prevHeight, currHeight = heightMap.firstKey();
heightMap = new TreeMap<>(Collections.reverseOrder());
heightMap.put(0,1);
pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
https://discuss.leetcode.com/topic/38065/java-solution-using-priority-queue-and-sweepline/
http://www.programcreek.com/2014/06/leetcode-the-skyline-problem-java/
https://discuss.leetcode.com/topic/22482/short-java-solution

LeetCode 56 - Merge Intervals
- Sort the intervals based on increasing order of starting time
- if prev.end >= curr.start  prev = merged else result.add(prev); prev = curr;

LeetCode 253 - Meeting Rooms II
https://discuss.leetcode.com/topic/35253/explanation-of-super-easy-java-solution-beats-98-8-from-pinkfloyda
- int[] starts, ends

Use TreeMap to store intervals
LeetCode 352 - Data Stream as Disjoint Intervals
- TreeMap<Integer, Interval> treeMap: key is the start point
- lowerKey(), higherKey()

LettCode 452 - Minimum Number of Arrows to Burst Balloons
- sort interval and greedy
https://discuss.leetcode.com/topic/66709/c-easy-understood-solution-sort/

LeetCode 435 - Non-overlapping Intervals
- sort interval by end
https://discuss.leetcode.com/topic/65828/java-solution-with-clear-explain

LeetCode 436 - Find Right Interval
TreeMap<Integer, Integer> intervalMap: key is the start, value is the index
- first put all intervals to the map: sorted by start
- intervalMap.ceilingEntry(intervals[i].end);

Google – Maximum Time Range Overlaps
https://reeestart.wordpress.com/2016/07/02/google-maximum-time-range-overlaps/

Google - remove alarm
https://reeestart.wordpress.com/2016/06/30/google-remove-alarm/
hash map - map priority to set of alarm id
max priority heap - PriorityQueue<Integer>

Google – Find a Path Among Circles
O(n^2) - https://reeestart.wordpress.com/2016/07/02/google-find-a-path-among-circles/


Bucket
LeetCode - 220 Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
slide window + bucket
https://leetcode.com/discuss/38206/ac-o-n-solution-in-java-using-buckets-with-explanation
https://discuss.leetcode.com/topic/27608/java-python-one-pass-solution-o-n-time-o-n-space-using-buckets/
https://leetcode.com/discuss/68090/easy-ac-solution-using-treeset-long-in-java

X. Ordered Stack

LeetCode 42 - Trapping Rain Water

1. Two Pointers

comapre height[left] and height[right]

2. Left and right array

int[] leftMax, rightMax

3. Ordered Stack - decreasing

https://discuss.leetcode.com/topic/4939/a-stack-based-solution-for-reference-inspired-by-histogram/2

s.push(i++); - store index

result += stack.isEmpty()? 0:(Math.min(A[stack.peek()],A[i])-A[bot])*(i-stack.peek()-1);

Next Greater Element
http://www.ideserve.co.in/learn/next-great-element-in-an-array

X. Stack
LeetCode 456 - 132 Pattern
Stack to maintain min-max: max after min till current element
https://discuss.leetcode.com/topic/68193/java-o-n-solution-using-stack-in-detail-explanation

TreeMap
Use TreeMap/TreeSet instead of PriorityQueue if it works and you need remove item from them

X. Union Find
http://algs4.cs.princeton.edu/15uf/UF.java.html

need know size of the nodes to init union-find
- Weighted Quick-Union and path compression
- O(1) ops: union, find, count, maxUnionCount, getHighestRank
- flattened parent tree
- no need to build/store graph (from edges array)

LeetCode 261 - Graph Valid Tree
1. uf
2. dfs
  boolean hasCycle(List<List<Integer>> adjList, int currentId, boolean[] visited, int parentId)
  if ((visited[v] && parentId != v) || (!visited[v] && hasCycle(adjList, neighborId, visited, currentId))) return hasCycle=true
3. bfs

LeetCode 130 - Surrounded Regions
1. dfs, bfs
find all 'O' not surrounded by 'X' (at or connected to the edge of the board ) and changed to '#'
flip the remain 'O' into X
flip the '#' back to 'O'
2. uf - union all the 'O' nodes on the boundry to a dummy node

LeetCode 128 - Longest Consecutive Sequence
1. use hashset, then check left and right
- but doesn't work for stream
https://discuss.leetcode.com/topic/17980/another-accepted-java-o-n-solution
2. https://discuss.leetcode.com/topic/9088/o-n-hashmap-java-solution
Map<Integer, Integer> map:  keep track of the sequence length and store that in the boundary points of the sequence.
3. uf: maxUnion or getHighestRank
https://discuss.leetcode.com/topic/29286/my-java-solution-using-unionfound
Map<Integer,Integer> map: value -> index
if(map.containsKey(nums[i]+1)) uf.union(i,map.get(nums[i]+1));

Detect Cycle in a an Undirected Graph
Number of Islands
LeetCode 323 - Number of Connected Components in an Undirected Graph
LeetCode 261 - Graph Valid Tree
LeetCode 305 - Number of Islands II
Group Contacts

X. Graph algorithm - O(V+E)
- Map<Integer, List<Integer>> map
- List<List<Integer>> adjList

topological sort
-- Put indegree=0 nodes to queue, iterate queue,  and decrease indegree of the node's neighbors by 1, if indegree is now 0, put into queue
- time complexity O(V+E), space O(V)
Leetcode 310 - Minimum Height Trees
List<Set<Integer>> adj
LeetCode 210 - Course Schedule II
LeetCode 269 -  Alien Dictionary
https://discuss.leetcode.com/topic/32900/java-bfs-solution
- build graph
dfs
https://discuss.leetcode.com/topic/33565/3ms-clean-java-solution-dfs
visited[i] = -1. Not even exist.
visited[i] = 0. Exist. Non-visited.
visited[i] = 1. Visiting.
visited[i] = 2. Visited.

LeetCode 444 - Sequence Reconstruction
https://discuss.leetcode.com/topic/65948/java-solution-using-bfs-topological-sort/5
- build the edge for adjacent ints in the array
Map<Integer, List<Integer>> graph
Map<Integer, Integer> indegree

Eulerian path/circuit
LeetCode 332 - Reconstruct Itinerary
https://discuss.leetcode.com/topic/36370/short-ruby-python-java-c
public List<String> findItinerary(String[][] tickets) {
    for (String[] ticket : tickets)
        targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
    visit("JFK");
    return route;
}
Map<String, PriorityQueue<String>> targets = new HashMap<>();
List<String> route = new LinkedList();
void visit(String airport) {
    while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
        visit(targets.get(airport).poll());
    route.add(0, airport);
}

X. Binary tree
- usually expected runtime for tree is O(n)
- PreOrder/InOrder/PostOrder/LevelOrder traverse
- Use PostOrder Traverse

Leetcode 124 - Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.

https://discuss.leetcode.com/topic/4407/accepted-short-solution-in-java

private int maxPathDown(TreeNode node) {

    if (node == null) return 0;

    int left = Math.max(0, maxPathDown(node.left));

    int right = Math.max(0, maxPathDown(node.right));

    maxValue = Math.max(maxValue, left + right + node.val);

    return Math.max(left, right) + node.val;

}
LeetCode 437 - Path Sum III
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards
https://discuss.leetcode.com/topic/64526/17-ms-o-n-java-prefix-sum-method
- preorder tree traverse
- use hashmap to track: the prefix sum -> how many ways get to this prefix sum
- map.put(sum, map.get(sum)-1); // Remove the current node so it wont affect other path

LeetCode 250: Count Univalue Subtrees

- post order

Remove the paths from root to leaf whose sum is not equal to given K.
http://algorithmsandme.in/2014/03/remove-all-nodes-in-binary-tree-which-dont-lie-in-path/

LeetCode 230 - Find k-th smallest element in BST
- inorder search, return when count decrease to 0 from k
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently?

LeetCode 298 - Binary Tree Longest Consecutive Sequence
- preorder: count = (root.val - val == 1)?count+1:1;

LeetCode 107 - Binary Tree Level Order Traversal II
- bottom-up level order

LeetCode 103 - Printing a Binary Tree in Zig Zag Level-Order
If we only need print, it's easier to first get all level nodes in correct order then print
X. bfs https://discuss.leetcode.com/topic/42184/java-easy-understand-recursive-methods-beats-96-attach-easy-bfs-methods
Queue<TreeNode>, boolean leftToRight = !leftToRight;
if(leftToRight) levelNodes.add(n.val); else levelNodes.addFirst(n.val);
x. dfs - https://discuss.leetcode.com/topic/3413/my-accepted-java-solution
ArrayList<LinkedList<Integer>> result
x. 2 stacks
https://discuss.leetcode.com/topic/3318/my-ac-java-code
https://discuss.leetcode.com/topic/32427/java-double-stack-solution
Stack<TreeNode> oddSt, evenSt

X. Binary search tree

LeetCode 333 - Largest BST Subtree

http://buttercola.blogspot.com/2016/02/leetcode-largest-bst-subtree.html

class Wrapper{

    int size;

    int lower, upper;

    boolean isBST;

}

LeetCode 95 - Unique Binary Search Trees II

http://n00tc0d3r.blogspot.com/2013/07/unique-binary-search-trees_6.html

DFS - divide and conquer

X. Tree with only parent node
Google – Sum of Subtree with Only Parent Pointer
https://reeestart.wordpress.com/2016/06/23/google-sum-of-subtree-with-only-parent-pointer/
- reconstruct parent -> child
Map<TNode, List<TNode>> tree

X. Bit trick
- 23n, loop and check very bit
LeetCode 287 - Find the Duplicate Number

32n - https://discuss.leetcode.com/topic/38493/o-32-n-solution-using-bit-manipulation-in-10-lines

LeetCode 421 - Maximum XOR of Two Numbers in an Array

X. Game theory
If a player is able to move to a losing position then he is in a winning position.
If a player is able to move only to the winning positions then he is in a losing position.
LeetCode flip game II
DFS + Cache (top-down)
- use it's dp(bottom-up) to time complexity
- Map<String, Boolean> winMap
- if(!canWin(opponent, map))

Google – Initialize Board
radom + backtrack - https://reeestart.wordpress.com/2016/07/01/google-initialize-board/

Math

LeetCode 60 - Permutation Sequence

Given n and k, return the kth permutation sequence.

k--;

mod = mod / (n - i);

int curIndex = k / mod;

k = k % mod;

builder.append(list.remove(groupIndex));

X. Random
LeetCode 398 - Random Pick Index
https://discuss.leetcode.com/topic/58301/simple-reservoir-sampling-solution
if (rnd.nextInt(++count) == 0) result = i;

X. Misc

LeetCode 158 - Read N Characters Given Read4 II
https://discuss.leetcode.com/topic/6402/clean-accepted-java-solution

char[] buffer, int offset, remaining, boolean isEndOfFile

LeetCode 289 - Game of Life

use 2 bits: [2nd bit, 1st bit] = [next state, current state]

https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation

LeetCode 361 - Bomb Enemy

1. v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]

2.

rowhits, colhits[n]

for (int k=j; k<n && grid[i][k] != 'W'; k++)

    rowhits += grid[i][k] == 'E';

for (int k=i; k<m && grid[k][j] != 'W'; k++)

    colhits[j] += grid[k][j] == 'E';

result = max(result, rowhits + colhits[j]);

LeetCode 300 - Longest Increasing Subsequence

1.

int i = Collections.binarySearch(dp, num);

dp.set((i<0) ? -i-1 : i, num);

-- O(nlogn)

2. DP O(N^2)

4Sum
https://discuss.leetcode.com/topic/12368/clean-accepted-java-o-n-3-solution-based-on-3sum
http://www.lifeincode.net/programming/leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java/
O(N^3)
HashMap<Integer, ArrayList<Pair>> hashMap

LeetCode 454 - 4Sum II
https://discuss.leetcode.com/topic/67593/clean-java-solution-o-n-2

Leetcode 370 - Range Addition
https://discuss.leetcode.com/topic/49691/java-o-k-n-time-complexity-solution
res[start] += value;
res[end+1] -= value;

LeetCode 406 - Queue Reconstruction by Height
1. sort + insert: by height then index
https://discuss.leetcode.com/topic/60394/easy-concept-with-python-c-java-solution

Rearrange Positive and Negative Numbers of Array On Each Side with­out chang­ing their respec­tive order

http://algorithms.tutorialhorizon.com/rearrange-positive-and-negative-numbers-of-array-on-each-side-in-onlogn/

- use reverse to avoid extra tmp array

Google – Shortest Words Contain Input String
- Inverted Index
Map<Character, List<String>> invertedIndex
set.retainAll(invertedIndex.get(c));

Hash - feature key
Google – Plate and Dictionary
- prime product as string key

LCA

-- Node to Node Binary Tree Path