Algorithm Problems Practices


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

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:

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

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

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
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.

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)

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 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
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
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
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;

Google interview - max vacation days


X. Slide Window
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)

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

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
Binary search/BiSection
- 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

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
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 smallCount;
    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
mid = low + (high - low) / 2;
Compare num[mid] with num[high]

LeetCode 33 - Searching an Element in a Rotated Sorted Array

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
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


TreeMap
LeetCode 456 - 132 Pattern
Use TreeMap/TreeSet instead of PriorityQueue if it works and you need remove item from them

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

Graph
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

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.
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

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
class Wrapper{
    int size;
    int lower, upper;
    boolean isBST;
}

LeetCode 95 - Unique Binary Search Trees II
DFS - divide and conquer

X. Bit trick
- 23n, loop and check very bit
LeetCode 287 - Find the Duplicate Number
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. 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]

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 148 - Sort List
http://www.jiuzhang.com/solutions/sort-list/
merge and quick sort on linkedlist

LCA
-- Node to Node Binary Tree Path

Posted by at

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)