Heap Sort

Heap Sort
The running complexity of BuildHeap is O(n)
http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
"Thus the lesson to be learned is that when designing algorithms that operate on trees, it is important to be most efficient on the bottommost levels of the tree (as BuildHeap is) since that is where most of the weight of the tree resides"

Another simple analysis:
we can skip half of the nodes at the height 0, which has n / 2 nodes
at height 1: n / 4 * 1
at height 2: n / 8 * 2
at height 3: n / 16 * 3
...
at height lgn: 1 * lgn

for bottom 3 levels: n / 4 + n / 8 * 2 + n / 16 * 3 = 11 / 16 * n
for bottom 4 levels: 11 / 16 + 4 / 32 = 13 / 16 * n
for bottom 5 levels: 13 / 16 + 5 / 64 = 47 / 64 * n
for bottom 6 levels: 47 / 64 + 6 / 128 = 100 / 128 * n
...
you can see that it will never be greater than n. That's why it is linear

Day 85, #97, Interleaving String

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
------------------------------------------------------
Solution #1, straight forward recursion 

class Solution {
public:
    bool isInter(string s1, int i1, string s2, int i2, string s3, int i3) {
        if (i3 == s3.length()) {
            return true;
        }
        
        if (i1 < s1.length() && s1[i1] == s3[i3] && isInter(s1,i1 + 1,s2,i2,s3,i3 + 1)) {
            return true;
        }
        
        if (i2 < s2.length() && s2[i2] == s3[i3] && isInter(s1,i1,s2,i2 + 1,s3,i3 + 1)) {
            return true;
        }
        
        return false;
        
    }

    bool isInterleave(string s1, string s2, string s3) {
        return isInter(s1,0,s2,0,s3,0);
    }
};

Solution #2 DP, similar logi. dp[i][j] means if s1[0 : i] and s2[0 : j] can match s3[0 : i + j + 1]
不用检查s3[0]是因为，只有在s1或s2长度为0时，s3[0]才有被检查的必要，这我们已经在initialization的时候已经做过 
***一定要想清楚 dp[i][j] 所代表的意思***

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 + len2 != s3.length()) return false;
        
        // check empty strings
        if (len1 == 0) {
            if (s2 == s3) {
                return true;
            }else {
                return false;
            }
        }
        if (len2 == 0) {
            if (s1 == s3) {
                return true;
            }else {
                return false;
            }
        }
        
        vector<vector<bool> > dp(len1 + 1,vector<bool>(len2 + 1,false));
        
        // initialize dp
        dp[0][0] = true;
        for (int i = 1; i <= len1; i++) {
            if (s1[i - 1] == s3[i - 1]) {
                dp[i][0] = true;
            }else {
                break;
            }
        }
        
        for (int i = 1; i <= len2; i++) {
            if (s2[i - 1] == s3[i - 1]) {
                dp[0][i] = true;
            }else {
                break;
            }
        }
        
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (s1[i] == s3[i + j + 1] && dp[i][j + 1]) {
                    dp[i + 1][j + 1] = true;
                }
                
                if (s2[j] == s3[i + j + 1] && dp[i + 1][j]) {
                    dp[i + 1][j + 1] = true;
                }
            }
        }
        
        return dp[len1][len2];
    }
};

可以简化为O(n) space, 就不写了

Day 84, #87, Scramble String

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
-------------------------------------------------------------
Solution #1 recursive

bool scramble(string s1,string s2) {
    if (s1 == s2) return true;    
    string t1 = s1,t2 = s2;
    sort(t1.begin(),t1.end());
    sort(t2.begin(),t2.end());
    if (t1 != t2) return false;
    
    for (int i = 1; i < s1.length(); i++) {
        string p1 = s1.substr(0,i), p2 = s1.substr(i);
        string q1 = s2.substr(0,i), q2 = s2.substr(i); 
        string q3 = s2.substr(s2.length() - i), q4 = s2.substr(0,s2.length() - i);
        
        if ((scramble(p1,q1) && scramble(p2,q2)) || (scramble(p1,q3) && scramble(p2,q4))) return true;
    }
    return false;
}

Solution #2 recursive + memo
找出s1所有的scrambled strings，然后一一对比

class Solution {
public:
    unordered_map<string,vector<string>> dic;
    void combine(vector<string> &rt,vector<string> &v1,vector<string> &v2) {
        for (string s1 : v1) {
            for (string s2 : v2) {
                rt.push_back(s1 + s2);
                rt.push_back(s2 + s1);
            }
        }
    }

    vector<string> permutation(string s) {
        vector<string> rt;
        if (s.length() == 1) {
            rt.push_back(s);
        }
    
        for (int i = 1; i < s.length(); i++) {
            string s0 = s.substr(0,i);
            string s1 = s.substr(i);
            vector<string> v1,v2; 
            if (dic.find(s0) != dic.end()) {
                v1 = dic[s0];
            }else {
                v1 = permutation(s0);
                dic[s0] = v1;   
            }
            
            if (dic.find(s1) != dic.end()) {
                v2 = dic[s1];
            }else {
                v2 = permutation(s1);
                dic[s1] = v2;
            }
            combine(rt,v1,v2);
        }
        
        return rt;
    }

    bool isScramble(string s1, string s2) {
        vector<string> rt = permutation(s1);
        for (string s : rt) {
            if (s == s2) return true;
        }
        
        return false;
    }
};

Solution #3 3-dimensional DP
dp[length][index at s1][index at s2]
int the most inner loop, delimiter breaks string in k - 1 different ways. same logic as recursive
注意loop里的终止条件

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len = s1.length();
        
        vector<vector<vector<bool> > > dp(len,vector<vector<bool> >(len,vector<bool>(len,false)));
        
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (s1[i] == s2[j]) {
                    dp[0][i][j] = true;
                } 
            }
        }
        
        for (int k = 2; k <= len; k++) {
            for (int i = 0; i <= len - k; i++) {
                
                for (int j = 0; j <= len - k; j++) {

                    for (int delimiter = 1; delimiter < k; delimiter++) {
                        
                        if (dp[delimiter - 1][i][j] && dp[k - delimiter - 1][i + delimiter][j + delimiter]) {
                            dp[k - 1][i][j] = true;
                            break;
                        }
                            
                        if (dp[delimiter - 1][i][j + k - delimiter] && dp[k - delimiter - 1][i + delimiter][j]) {
                            dp[k - 1][i][j] = true;
                            break;
                        }
                        
                    }
                }
                
            }
            
        }
    
        return dp[len - 1][0][0];
    }
};

Day 83, #85, Maximal Rectangle

Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

--------------------------------------------
方法1：O(m * n) 解法来自google，借用了上一题Largest Rectangle Area的代码
将每一行都看做x轴，在每一个列上的连续1的个数则为当前列的y值，计算出当前行的最大矩形面积

class Solution {
public:
    // from the question Largest Rectangle Area
    int largestRectangleArea(vector<int> &height) {
        stack<int> st;
        int largest = 0;
        height.push_back(0);
        
        for (int i = 0; i < height.size(); i++) {
            
            if (st.empty() || height[i] >= height[st.top()]) {
                st.push(i);
            }else {
                int topBar = st.top();
                st.pop();
                if (st.empty()) {
                    largest = max(largest,height[topBar] * i);
                }else {
                    largest = max(largest,height[topBar] * (i - st.top() - 1));
                }
                
                i--;
            }
        }

        return largest;
    }

    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.size() == 0) return 0;
        vector<int> heights(matrix[0].size(),0);
        int largest = 0;
        
        for (int row = 0; row < matrix.size(); row++) {
            for (int col = 0; col < matrix[0].size(); col++) {
                if (matrix[row][col] == '1') {
                    heights[col]++;
                }else {
                    heights[col] = 0;
                }
            }
            largest = max(largest, largestRectangleArea(heights));
        }
        
        return largest;
    }
};

方法2：O(m * n * m)
dp[i][j]存的是以（i,j）为起点往右，在该行上连续的1的个数

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n + 1,0));
        
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = dp[i][j + 1] + 1;
                }
            }
        }
        
        int largest = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int width = dp[i][j];
                for (int k = i; k < m && width > 0; k++) {
                    width = min(dp[k][j],width);
                    largest = max(largest,width * (k - i + 1));
                }
            }
        }
        
        return largest;
    }
};

方法3：COME_BACK
height[i]是在（i, j）上1的高度，如果matrix[i][j] = 0，则height[i] = 0
left[i]是底边包含(i, j)，高度为height[i]矩阵的最左边的index，right[i]类似
（找个例子，走一边就信服了）

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<int> left(n,0);
        vector<int> right(n,n - 1);
        vector<int> height(n,0);
        int largest = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    height[j]++;
                }else {
                    height[j] = 0;
                }
            }
            
            int furLeft = 0;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[j] = max(furLeft,left[j]);
                }else {
                    furLeft = j + 1;
                    left[j] = 0;
                }
            }
            
            int furRight = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = min(furRight,right[j]);
                }else {
                    furRight = j - 1;
                    right[j] = n - 1;
                }
            }
            
            for (int j = 0; j < n; j++) {
                largest = max(largest,height[j] * (right[j] - left[j] + 1));
            }
        }
        
        return largest;
    }
};

Day 82, #84, Largest Rectangle in Histogram

Largest Rectangle in Histogram

 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

----------------------------------------------------------
for each single bar, calculate the largest rectangle that has the same height as the bar,
OJ Time Limit Exceeded

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int largest = 0;
        
        for (int i = 0; i < height.size(); i++) {
            int left = i - 1, right = i + 1;
            int length = 1;
            while (left >= 0 && height[left] >= height[i]) {
                length++;
                left--;
            }
            
            while (right < height.size() && height[right] >= height[i]) {
                length++;
                right++;
            }
            
            largest = max(largest,length * height[i]);
        }
        
        return largest;
    }
};

Solution #2
网上讲解很多，请google
要点
#1 原数组末尾插入0是为了清空并计算stack内所剩的数
#2 第18行: (topBar - st.top() - 1) + (i - topBar) = i - st.top() -  1
- topBar左边：因为从st.top（）到topBar之间的长方形都高于topBar，当计算以topBar为高度的面积时得包含之前的长方形
- topBar右边：到当前的i为止，所有的长方形都大于或等于topBar
#3 当stack为空时，说明之前所有经历过的长方形都高于topBar. 因为在某一个index时，stack里面比当前小的永远不会被pop出去
#4 stack所存的是index
#5 stack里的高度永远为递增
例子：{4,2,0,3,2,5}
情况1：

情况2：

情况3：

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> st;
        int largest = 0;
        height.push_back(0);
        
        for (int i = 0; i < height.size(); i++) {
            
            if (st.empty() || height[i] >= height[st.top()]) {
                st.push(i);
            }else {
                int topBar = st.top();
                st.pop();
                if (st.empty()) {
                    largest = max(largest,height[topBar] * i);
                }else {
                    largest = max(largest,height[topBar] * (i - st.top() - 1));
                }
                
                i--;
            }
        }

        return largest;
    }
};

Day 81, #81, Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
--------------------------------------------------------------------------
与I同样的思路，不同点是增加了1个if判断来解决重复的问题
重复的情况#1： start，mid，end 3处都相等，如111111111111112111。此时左右两半都需要检测，worst cast O(n)
重复的情况#2：仅start或者end跟mid相等，如4444123，此时原有代码也可解决

class Solution {
public:
    bool searchInRotated(int A[], int start, int end, int target) {
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;
        if (A[mid] == target) {
            return true;
        }
        
        // ------ to handle duplicates ---- 
        if (A[start] == A[mid] && A[start] == A[end]) {
            return searchInRotated(A,start,mid - 1,target) || searchInRotated(A,mid + 1,end,target);
        }
        
        if (A[start] <= A[mid]) {
            if (A[start] <= target && target <= A[mid]) {
                return searchInRotated(A,start,mid - 1,target);
            }else {
                return searchInRotated(A,mid + 1,end,target);
            }
        }else {
            if (A[mid] <= target && target <= A[end]) {
                return searchInRotated(A,mid + 1,end,target);
            }else {
                return searchInRotated(A,start,mid - 1,target);
            }
        }
        
    }

    bool search(int A[], int n, int target) {
        return searchInRotated(A,0,n - 1,target);
    }
};

Solution #2, iterative(to do)

Day 80, #60, Permutation Sequence

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
-----------------------------------------------------------------------------
Factorial. Lay out permutations, you will see the pattern
将k设为0-base

class Solution {
public:
    int getFactorial(int n) {
        int rt = 1;
        for (int i = 1; i <= n; i++) {
            rt *= i;
        }
        
        return rt;
    }

    int getNextNumber(vector<bool> &nums, int section) {
        for (int i = 0; i < nums.size(); i++) {
            if (section == 0 && nums[i] == false) {
                nums[i] = true;
                return i;
            }
            if (nums[i] == false) {
                section--;
            }
        }
    }

    string getPermutation(int n, int k) {
        int factorial = getFactorial(n);
        string rt = "";
        vector<bool> nums(n,false);
        k--;
        for (int i = n; i > 0; i--) {
            factorial /= i;
            int section = k / factorial;
            k = k % factorial;
            char c = getNextNumber(nums,section) + '1';
            rt += c;
        }
        
        return rt;
    }
};

Day 79, #44, Wildcard Matching

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

---------------------------------------------------------------
Solution #1 recursion, OJ time limit exceeded

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') {
            return *s == '\0';
        }
        
        if (*p == *s || *p == '?') {
            return isMatch(s + 1, p + 1);
        }
        
        if (*p == '*') {
            while (*s != '\0') {
                if(isMatch(s,p + 1)) {
                    return true;
                }
                s++;
            }
        }
        
        return false;
    }
};

Solution #2, dp with 2d arrays,

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = p.length(), n = s.length();
        vector<vector<bool> > dp(m + 1,vector<bool>(n + 1,false));
        
        dp[0][0] = true;
        for (int i = 0; i < m; i++) {
         if (p[i] != '*') break;
            dp[i + 1][0] = true;
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] && (p[i] == s[j] || p[i] == '?')) {
                    dp[i + 1][j + 1] = true;
                }else if (p[i] == '*') {
                    if (dp[i][j + 1] || dp[i + 1][j]) {
                        dp[i + 1][j + 1] = true;
                    }
                }
            }
        }
        return dp[m][n];
    }
};

改良版DP，用了一个一维数组，当*p == '*',dp[j]只取决于dp[j - 1]，过不了最后一个test case

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = p.length(), n = s.length();
        vector<bool> dp(n + 1,false);
        bool diag = true;
        dp[0] = true;
        
        for (int i = 0; i < m; i++) {
            diag = dp[0];
            for (int j = 0; j < n; j++) {
                if (diag && (p[i] == s[j] || p[i] == '?')) {
                    diag = dp[j + 1];
                    dp[j + 1] = true;
                }else if (p[i] == '*') {
                    diag = dp[j + 1];
                    if (dp[j] || dp[j + 1]) {
                        dp[j + 1] = true;
                    }
                }else {
                    diag = dp[j + 1];
                    dp[j + 1] = false;
                }
            }
            if (p[i] == '*' && dp[0]) {
                dp[0] = true;
            }else {
                dp[0] = false;
            }
            
        }
        
        return dp[n];
    }
};

Solution #3, constant space
star用来记录最近*的位置，index用来记录当前*匹配成功后s的位置。*之前全部匹配成功，不用再重复检测。*之后如果匹配失败，回头从star + 1 和 index重新匹配，每匹配失败一次，index增加一位。

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char *star = NULL;
        const char *index = s;
        
        while (*s != '\0') {
            if (*s == *p || *p == '?') {
                s++;
                p++;
            }else if (*p == '*') {
                star = p;
                p++;
                index = s;
            }else if (star != NULL) {
                p = star + 1;
                index++;
                s = index;
            }else return false;
        }
        
        while (*p == '*') {
            p++;
        }
        
        return *p == '\0';
    }
};

Java,2维dp

class Solution {
    public boolean isMatch(String s, String p) {
        List<List<Boolean>> dp = getDP(s, p);
            
        for (int i = 0; i < p.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (dp.get(i).get(j) && (s.charAt(j) == p.charAt(i) || p.charAt(i) == '?')) {
                    dp.get(i + 1).set(j + 1, true);
                } else if (p.charAt(i) == '*' && (dp.get(i).get(j + 1) || dp.get(i + 1).get(j))) {
                    dp.get(i + 1).set(j + 1, true);
                }
            }
        }
        
        return dp.get(p.length()).get(s.length());
    }
    
    private List<List<Boolean>> getDP(String s, String p) {
        int m = s.length();
        int n = p.length();
        List<List<Boolean>> dp = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            List<Boolean> inner = new ArrayList<>();
            if (i == 0 || (i > 0 && dp.get(i - 1).get(0) && p.charAt(i - 1) == '*')) inner.add(true);
            else inner.add(false);
            for (int j = 0; j < m; j++) {
                inner.add(false);
            }
            dp.add(inner);
        }
        
        return dp;

    }
}

Day 78, #41, First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
----------------------------------------------------------------

# Pass 1, move every value to the position of its value

因为找的是第一个非0，所以把1存在0,2存在1

while里的条件是检测下一个位置是否已经匹配好，如果检查当前位置的话，会进入死循环，因为会有重复的数字如[1,1]

# Pass 2, find first location where the index doesn't match the value

reference  

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for (int i = 0; i < n; i++) {
            int target = A[i];
            while (target > 0 && target <= n && A[target - 1] != target) {
                int temp = A[target - 1];
                A[target - 1] = target;
                A[i] = temp;
                target = A[i];
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (i + 1 != A[i]) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};

Day 77, #31, Next Permutation

Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
--------------------------------------------------------------------------
Solution #1
Find the last peak number i, swap [i - 1] and the number that follows [i - 1] in ascending order, then reverse all numbers from peak to end

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if (num.size() == 0 || num.size() == 1) return;
        int peak = -1;
        int swapIndex = 0;
        
        for (int i = 0; i < num.size(); i++) {
            if (i + 1 < num.size() && num[i] < num[i + 1]) {
                peak = i + 1;
                swapIndex = peak;
            }else if (peak != -1) {
                if (num[i] > num[peak - 1]) {
                    swapIndex = i;
                }
            }    
        }
        
        if (peak == -1) {
            reverse(num.begin(),num.end());
        }else {
            int temp = num[swapIndex];
            num[swapIndex] = num[peak - 1];
            num[peak - 1] = temp;
            
            reverse(num.begin() + peak,num.end());
        }
    }
};

Java, updated on Aug-6th-2018
6 9 7 3 2 -> 7 2 3 6 9 可以看出规律

注意数字有重复的时候，比如2 3 1 3 3 -> 2 3 3 1 3. 所有第36行对比时要加等号

class Solution {
    public void nextPermutation(int[] nums) {
        int drop = getFirstDrop(nums);
        if (drop == -1) {
            reverseArray(nums, 0);
            return;
        }
        
        int nextInOrder = getNextInOrder(nums, drop);
        swap(nums, drop, nextInOrder);
        reverseArray(nums, drop + 1);
    }
    
    private void reverseArray(int[] nums, int index) {
        int right = nums.length - 1;
        
        while (index < right) {
            swap(nums, index, right);    
            index++;
            right--;
        }
    }
    
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    
    private int getNextInOrder(int[] nums, int drop) {
        
        int index = drop + 1;
        int min = nums[index];
        
        for (int i = index; i < nums.length; i++) {
            if (min >= nums[i] && nums[i] > nums[drop]) { // 注意“>=”
                min = nums[i];
                index = i;
            }
        }
        
        return index;
    }
    
    private int getFirstDrop(int[] nums) {
        
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                return i;
            }
        }
        
        return -1;
    }
}

Day 76, #10, Regular Expression Matching

Regular Expression Matching
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

 ------------------------------------------------------------------------------
Solution #1, recursion

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') {
            return *s == '\0';
        }
        
        if (*(p + 1) != '*') {
            return (*s == *p || (*p == '.' && *s != '\0')) && isMatch(s + 1, p + 1);
        }

        while (*p == *s || (*p == '.' && *s != '\0')) {
            if (isMatch(s,p + 2)) {
                return true;
            }
            s++;
        }
        return isMatch(s,p + 2);
    }
};

Solution #2, DP
dp[i][j] has the boolean value whether p[0 : i] can match s[0 : j], dp[0][0] is set to true since empty string matches empty pattern

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(p);
        int n = strlen(s);
        
        vector<vector<bool> > dp(m + 1,vector<bool>(n + 1,false));
        dp[0][0] = true;
        
        for (int i = 2; i <= m; i++) {
            if (p[i - 1] == '*' && dp[i - 2][0]) {
                dp[i][0] = true;
            }
        }
        
        for (int i = 1; i <= m; i++) {
            
            for (int j = 1; j <= n; j++) {
                if (p[i - 1] == s[j - 1] || p[i - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }else if (p[i - 1] == '*') {
                    // 1 or more char
                    if (dp[i][j - 1] && (p[i - 2] == s[j - 1] || p[i - 2] == '.')) {
                        dp[i][j] = true;
                    }
                    // zero char
                    else if (i - 2 >= 0 && dp[i - 2][j]) {
                        dp[i][j] = true;
                    }
                }
            }
            
        }
        
        return dp[m][n];
    }
};

class Solution {
public:
    bool helper(string s,string p,int i,int j) {
        if (j == p.length()) return i == s.length();
        
        if (j == p.length() - 1 || (j + 1 < p.length() && p[j + 1] != '*')) {
            if (i < s.length() && (p[j] == s[i] || p[j] == '.')) {
                return helper(s,p,i + 1,j + 1);
            }
            return false;
        }
        
        while (i < s.length() && (p[j] == s[i] || p[j] == '.')) {
            if (helper(s,p,i,j + 2)) {
                return true;
            }
            i++;
        }
        return helper(s,p,i,j + 2);
    }
    
    bool isMatch(string s, string p) {
        return helper(s,p,0,0);
    }
};

Java
关键：把下一个 == '*' 和 != '*' 两种情况分开处理

class Solution {
    public boolean isMatch(String s, String p) {
        return rec(s,p,0,0);
    }
    
    private boolean rec(String s, String p, int i, int j) {
        if (i == s.length() && j == p.length()) {
            return true;
        }
        
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            int temp = i;
            while (temp < s.length() && (s.charAt(temp) == p.charAt(j) || p.charAt(j) == '.')) {
                if (rec(s, p, temp + 1, j + 2)) return true;
                temp++;
            }
            return rec(s,p,i,j + 2); // '*' matches zero chars
        }
        
        if (i < s.length() && j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
            return rec(s, p, i + 1, j + 1);
        }
    
        return false;
    }
}

预处理的时候要回头看2位之前的位置。
主函数中还要考虑'*' match 0个的情况

class Solution {
    public boolean isMatch(String s, String p) {
        List<List<Boolean>> dp = getDP(s, p);
        int m = p.length();
        int n = s.length();
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <=n; j++) {
                if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '.') {
                    dp.get(i).add(j, dp.get(i - 1).get(j - 1));
                } else if (p.charAt(i - 1) == '*') {
                    if (i - 2 >= 0 && dp.get(i - 2).get(j)) {
                        dp.get(i).add(j, true);
                    }else if (dp.get(i).get(j - 1) && (p.charAt(i - 2) == s.charAt(j - 1) || p.charAt(i - 2) == '.')) {
                        dp.get(i).add(j, true);
                    }
                }
            }
        }
        
        return dp.get(m).get(n);
    }
    
    private List<List<Boolean>> getDP(String s, String p) {
        int m = p.length();
        int n = s.length();
        List<List<Boolean>> dp = new ArrayList<>();
        
        for (int i = 0; i <= m; i++) {
            List<Boolean> list = new ArrayList<>();
            if (i == 0 || (p.charAt(i - 1) == '*' && dp.get(i - 2).get(0))) list.add(true);
            else list.add(false);
            for (int j = 0; j < n; j++) {
                list.add(false);
            }
            dp.add(list);
        }
        
        return dp;
    }
}

Day 75, #5, Median of Two Sorted Arrays

Median of Two Sorted Arrays
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

------------------------------------------------------------------------------------------
a special case of find kth smallest
reference:
http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/
http://blog.csdn.net/yutianzuijin/article/details/11499917
un-solved:
#1 how to determine k's value: int kA = k * lenA / (lenB + lenA)
#2 why is this inclusive: endA = kA

class Solution {
public:
    double findKth (int A[], int startA,int endA, int B[], int startB,int endB, int k) {
        int lenA = endA - startA + 1;
        int lenB = endB - startB + 1;
        if (lenA == 0) {
            return B[startB + k];
        }
        if (lenB == 0) {
            return A[startA + k];
        }
        
        if (k == 0) {
            return min(A[startA],B[startB]);
        }
        
        int kA = k * lenA / (lenB + lenA); // ???
        int kB = k - kA - 1;
        kA += startA;
        kB += startB;
        
        if (A[kA] == B[kB]) {
            return A[kA];
        }
        
        if (A[kA] > B[kB]) {
            k = k - (kB - startB + 1);
            endA = kA; // inclusive, why?
            startB = kB + 1;
            
        }else {
            k = k - (kA - startA + 1);
            startA = kA + 1; 
            endB = kB; // inclusive
        }
        
        return findKth(A,startA,endA,B,startB,endB,k);
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if ((m + n) % 2 == 1) {
            return findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2);
        }else {
            return (findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2) + findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2 - 1)) / 2.0;
        }
    }
};

Solution #2, reference:  http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
如果A[i]是中位数，则A[i]比A里i 个数都大， 比B里（m+n）/2 - i 个数都大
j = (m+n)/2 - i - 1
B[j] < A[i] < B[j + 1]
反之，A在B[j]和B[j + 1]的左侧或者右侧

class Solution {
public:
    double findMedian (int A[],int B[],int m,int n,int left,int right) {
        if (left > right) {
            return findMedian(B,A,n,m,max(0,(m+n)/2 - m),min(n,(m+n)/2));
        }
        
        int i = (left + right) / 2;
        int j = (m + n) / 2 - i - 1;
        
        if (j >= 0 && A[i] < B[j]) {
            return findMedian(A,B,m,n,i + 1, right);
        }
        
        if (j < n - 1 && A[i] > B[j + 1]) {
            return findMedian(A,B,m,n,left,i - 1);
        }
        
        if ((m + n) % 2 == 1) {
            return A[i];
        }
        if (i > 0) {
            return (A[i] + max(B[j],A[i - 1])) / 2.0;
        }
        return (A[i] + B[j]) / 2.0;
        
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if (m > n) {
            return findMedian(A,B,m,n,max(0,(m+n)/2 - n),min(m,(m+n)/2));
        }
        return findMedian(B,A,n,m,max(0,(m+n)/2 - m),min(n,(m+n)/2));
    }
};

Another one, takes half of k at each call, key us (k + 1) / 2
#1 当A里的元素不足 k / 2 个时，可以砍掉B的前 k / 2
#2 当 A[k/2] < B[k/2], 可以砍掉A的前 k / 2
以上都可以用反证法证明

k为0-based

1. return B[BStart + k]意思为返回第 k + 1（1-based）小的elem
2. AK = (k + 1) / 2, 为个数，所以 k 需要 + 1
3. AStart + AK - 1, 同样道理，AK是个数（1-based），需要转换为 0-based
4. return findKth(,....AStart + AK), AK是要被砍掉的个数，所以不用 - 1

base condition以下，k和AK，BK不可能为0，所以需要 - 1，不然AStart永远取不到

http://www.ninechapter.com/solutions/median-of-two-sorted-arrays/

class Solution {
public:
    double findKth(int A[],int m, int AStart, int B[], int n, int BStart, int k) {
        if (AStart == m) return B[BStart + k];
        if (BStart == n) return A[AStart + k];
        
        if (k == 0) return min(A[AStart],B[BStart]); 
        
        int AKey = INT_MAX;
        int BKey = INT_MAX;
        int AK = (k + 1) / 2;
        int BK = (k + 1) / 2;
        
        if (AStart + AK - 1 < m) {
            AKey = A[AStart + AK - 1];
        }
        if (BStart + BK - 1 < n) {
            BKey = B[BStart + BK - 1];
        }
        
        if (AKey < BKey) {
            return findKth(A,m,AStart + AK,B,n,BStart,k - AK);
        }else {
            return findKth(A,m,AStart,B,n,BStart + BK,k - BK);
        }
        
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int k = n + m;
        if (k % 2 == 0) {
            return (findKth(A,m, 0, B,n, 0, k / 2 - 1) + findKth(A,m,0, B, n, 0, k / 2)) / 2.0 ;
        } else {
            return findKth(A,m,0, B, n, 0, k / 2);
        }
    }
};

Notes: sorting

select algorithm, quickselect. median of medians

find the k-th smallest in an un-sorted array

median of two sorted array,k-th of two sorted array
http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

Notes for Leetcode's blog

Sliding window（已看，已理解，未写）
http://leetcode.com/2011/01/sliding-window-maximum.html

方法1：暴力解
方法2：for 循环内每一步计算的都是上一步的window的最大值，所以最后一个window得单独计算
注意： priority_queue每次push或者pop都会重新生成最大/小值在开头
方法3：用双向链表，queue里存的是element的index。当前的最大值永远在最前，不用考虑比最大值小的值。每当插入一个新的值，pop掉所有比它小的值。之后在对比当前最大值是否在范围（window）内

Notes on Notes -- Chapter 2, 3, 4*

chapter 2
设定dummy

----------

chapter 3

Tower of Hanoi

iterative solution

http://en.wikipedia.org/wiki/Tower_of_Hanoi
--------

chapter4

trie -- implementation
http://en.wikipedia.org/wiki/Trie

heap

priority queue

graph -- implementation
http://www.cs.bu.edu/teaching/c/graph/linked/

Dijkstra's algorithm

greedy

Check if a graph has a cycle
undirected: use DFS

directed: use Topological sorting

lowest common ancestor
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

Find the immediate right neighbor of the given node, with parent links given, but without root node.( Ebay interview question)

Word Ladder II 

Notes: Distributed System -- Chubby, Zookeeper

Use of Chubby or Zookeeper

• Group membership and name services
  By having each node register an ephemeral znode for itself (and any roles it might be fulfilling), you can use ZooKeeper as a replacement for DNS within your cluster. Nodes that go down are automatically removed from the list, and your cluster always has an up-to-date directory of the active nodes.
• Distributed mutexes and master election
  We discussed these potential uses for ZooKeeper above in connection with sequential nodes. These features can help you implement automatic fail-over within your cluster, coordinate concurrent access to resources, and make other decisions in your cluster safely.
• Asynchronous message passing and event broadcasting
  Although other tools are better suited to message passing when throughput is the main concern, I’ve found ZooKeeper to be quite useful for building a simple pub/sub system when needed. In one case, a cluster needed a long sequence of actions to be performed in the hours after a node was added or removed in the cluster. On demand, the sequence of actions was loaded into ZooKeeper as a group of sequential nodes, forming a queue. The “master” node processed each action at the designated time and in the correct order. The process took several hours and there was a chance that the master node might crash or be decommissioned during that time. Because ZooKeeper recorded the progress on each action, another node could pick up where the master left off in the event of any problem.
• Centralized configuration management
  Using ZooKeeper to store your configuration information has two main benefits. First, new nodes only need to be told how to connect to ZooKeeper and can then download all other configuration information and determine the role they should play in the cluster for themselves. Second, your application can subscribe to changes in the configuration, allowing you to tweak the configuration through a ZooKeeper client and modify the cluster’s behavior at run-time.

Reference:
http://blog.cloudera.com/blog/2013/02/how-to-use-apache-zookeeper-to-build-distributed-apps-and-why/

http://www.ibm.com/developerworks/library/bd-zookeeper/

awesome read:  https://developer.yahoo.com/hadoop/tutorial/module6.html#intro
-------------------------------------------
group membership:
example

The Group Membership Service (GMS) uses self-defined system membership. Processes can join or leave the distributed system at any time. The GMS communicates this information to every other member in the system, with certain consistency guarantees. Each member in the group participates in membership decisions, which ensures that either all members see a new member or no members see it.

The membership coordinator, a key component of the GMS, handles "join" and "leave" requests, and also handles members that are suspected of having left the system. The system automatically elects the oldest member of the distributed system to act as the coordinator, and it elects a new one if the member fails or is unreachable. The coordinator's basic purpose is to relay the current membership view to each member of the distributed system and to ensure the consistency of the view at all times.

Because the SQLFire distributed system is dynamic, you can add or remove members in a very short time period. This makes it easy to reconfigure the system to handle added demand (load).The GMS permits the distributed system to progress under conditions in which a statically-defined membership system could not. A static model defines members by host and identity, which makes it difficult to add or remove members in an active distributed 

------------------------------------
Note:
write: only through master
read: any nodes can handle it

use: leader election, lock, consensus/voting?
more uses: http://ksjeyabarani.blogspot.com/2012/11/zookeeper-as-distributed-consensus.html
zookeeper recipe: http://zookeeper.apache.org/doc/current/recipes.html

Notes: Distributed System -- Paxos

what is instance

• An instance is the algorithm for choosing one value.
• A round refers to a proposer's single attempt of a Phase 1 + Phase 2. A node can have multiple rounds in an instance of Paxos. A round id is globaly unique per instance across all nodes. This is sometimes called proposal number.
• A node may take on several roles; most notably Proposer and Acceptor. In my answers, I'll assume each node takes on both roles.

A naive implementation of Paxos is not guaranteed to terminate because multiple nodes can leap-frog Prepare phases. There are two ways of getting around this. One is to have a random backoff before starting new Prepare phases. The second is to route all requests to a designated leader, that acts as proposer (The leader is chosen by a Paxos instance. See also Multi-paxos) 

roundId = i*M + index[node]where i is the ith round this node is starting (that is i is unique per node per paxos instance, and is monotonically increasing).

reference:  http://stackoverflow.com/questions/5850487/questions-about-paxos-implementation/10151660#10151660
----------------------

more paxos: Michael Deardeuff on stackoverflow

pseudo code

http://stackoverflow.com/questions/14435646/paxos-value-choice/14472334#14472334
 --------------------
Round ids (aka proposal numbers) should be increasing and must be unique per instance across all nodes.

-------------------------------
Paxos notes in Chinese
http://blog.csdn.net/m_vptr/article/details/8014220
 -------------------------------------------
No timeout in Paxos???? see below
----------------------------------
finish How to Build a Highly Available System, from section 6.4

------------------------------------------------------
lessons-learned-from-paxos: http://blog.willportnoy.com/2012/06/lessons-learned-from-paxos.html
explained a more practical Paxos

You may even choose to introduce nondeterminism: for example, I use randomized exponential backoff as a response to timeouts to allow a set of Paxos replicas to settle on a persistent leader allowing for faster consensus.

To make code deterministic for repeatable tests, it must have the same inputs. And the same inputs means the same network i/o, thread scheduling, random number generation - effectively all interaction with the outside world.

about timeout in Paxos

1. Many theoretical algorithms from distributed systems use the Asynchronous Model of time, where there is no shared notion of time across different nodes. One technique used to reduce these methods to practice is to introduce timeouts on certain operations. There would be a timeout for the replica trying to become leader, a timeout for the non-leader replicas watching for a leader replica that has gone offline, and a timeout for the phase 2 rounds of voting. There is an important detail in the last timeout though - the better implementations of Paxos allow multiple instances to reach consensus in parallel (without picking a fixed factor of concurrency, as Stoppable Paxosdescribes). But it simply takes longer, even if purely by network latency, to drive more instances to consensus. So in the end, you either vary your timeout in proportion to the number of requests or you limit the number of concurrent requests so that the timeout is sufficient.

#11 how to avoid massive amount of messages passing in phase1
#15 queue with timeout can work as batching

----------------------------------------

Hashing

hash function
page 264, clrs
h.k/ D bm.kA mod 1/c

Division Method:
h(k) = k mod m
where m is ideally prime

Multiplication Method:
h(k) = [(a k) mod 2w] (w >> r)
where a is a random odd integer between 2^(w-1) and 2^w, k is given by w bits, and m = table
size = 2r.

universal hashing

----------------------------------
Karp Rabin_wiki, Rolling Hash_wiki

However, there are two problems with this. First, because there are so many different strings, to keep the hash values small we have to assign some strings the same number. This means that if the hash values match, the strings might not match; we have to verify that they do, which can take a long time for long substrings. Luckily, a good hash function promises us that on most reasonable inputs, this won't happen too often, which keeps the average search time within an acceptable range.

hash functions used for karp rabin, go to wiki hash function
The key to the Rabin–Karp algorithm's performance is the efficient computation of hash values of the successive substrings of the text. One popular and effective rolling hash function treats every substring as a number in some base, the base being usually a large prime. For example, if the substring is "hi" and the base is 101, the hash value would be 104 × 101¹ + 105 × 101⁰ = 10609 (ASCII of 'h' is 104 and of 'i' is 105)

multiple pattern search
The Rabin–Karp algorithm is inferior for single pattern searching to Knuth–Morris–Pratt algorithm, Boyer–Moore string search algorithm and other faster single pattern string searching algorithms because of its slow worst case behavior. However, it is an algorithm of choice for multiple pattern search.

------------------------------------------
Probing 
Liner probing
quadratic probing 
Double hashing
h(k, i) = (h1(k) + i * h2(k) mod m

BST - General BST, AVL, LCA

Successor node
#1, with parent pointer
From page 292, CLRS 
TREE-SUCCESSOR.(x)
  if x:right != NIL
  return TREE-MINIMUM.(x:right)
  y = x:p
  while y != NIL and x == y:right
  x = y
  y = y:p
  return y
No need to compare keys

#2, without parent pointer

struct node * inOrderSuccessor(struct node *root, struct node *n)
{
    // step 1 of the above algorithm
    if( n->right != NULL )
        return minValue(n->right);
 
    struct node *succ = NULL;
 
    // Start from root and search for successor down the tree
    while (root != NULL)
    {
        if (n->data < root->data)
        {
            succ = root;
            root = root->left;
        }
        else if (n->data > root->data)
            root = root->right;
        else
           break;
    }
 
    return succ;
}

--------------------------------------------
node insertion
TREE-INSERT.T; ´/
1 y D NIL
2 x D T:root
3 while x ¤ NIL
4 y D x
5 if ´:key < x:key
6 x D x:left
7 else x D x:right
8 ´:p D y
9 if y == NIL
10 T:root D ´ // tree T was empty
11 elseif ´:key < y:key
12 y:left D ´
13 else y:right D ´
node deletion, Page 295, CLRS
3 basic cases:
If ´ has no children, then we simply remove it by modifying its parent to replace ´ with NIL as its child.

If ´ has just one child, then we elevate that child to take ´’s position in the tree by modifying ´’s parent to replace ´ by ´’s child.


If ´ has two children, then we find ´’s successor y—which must be in ´’s right subtree—and have y take ´’s position in the tree. The rest of ´’s original right subtree becomes y’s new right subtree, and ´’s left subtree becomes y’s new left subtree. This case is the tricky one because, as we shall see, it matters whether y is ´’s right child.

Check Wiki for all all operations of BST
"Another way to explain insertion is that in order to insert a new node in the tree, its key is first compared with that of the root. If its key is less than the root's, it is then compared with the key of the root's left child. If its key is greater, it is compared with the root's right child. This process continues, until the new node is compared with a leaf node, and then it is added as this node's right or left child, depending on its key."

----------------------------------------------

AVL, from Wiki
rotation

 if (balance_factor(L) == 2) { //The left column
   let P=left_child(L)
   if (balance_factor(P) == -1) { //The "Left Right Case"
      rotate_left(P) //reduce to "Left Left Case"
   }
   //Left Left Case
   rotate_right(L);
 } else { // balance_factor(L) == -2, the right column
   let P=right_child(L)
   if (balance_factor(P) == 1) { //The "Right Left Case"
      rotate_right(P) //reduce to "Right Right Case"
   }
   //Right Right Case
   rotate_left(L);
 }

Deletion
Steps to consider when deleting a node in an AVL tree are the following:

1. If node X is a leaf or has only one child, skip to step 5. (node Z will be node X)
2. Otherwise, determine node Y by finding the largest node in node X's left sub tree (in-order predecessor) or the smallest in its right sub tree (in-order successor).
3. Replace node X with node Y (remember, tree structure doesn't change here, only the values). In this step, node X is essentially deleted when its internal values were overwritten with node Y's.
4. Choose node Z to be the old node Y.
5. Attach node Z's subtree to its parent (if it has a subtree). If node Z's parent is null, update root. (node Z is currently root)
6. Delete node Z.
7. Retrace the path back up the tree (starting with node Z's parent) to the root, adjusting the balance factors as needed.

The retracing can stop if the balance factor becomes −1 or +1 indicating that the height of that subtree has remained unchanged. If the balance factor becomes 0 then the height of the subtree has decreased by one and the retracing needs to continue. If the balance factor becomes −2 or +2 then the subtree is unbalanced and needs to be rotated to fix it. If the rotation leaves the subtree's balance factor at 0 then the retracing towards the root must continue since the height of this subtree has decreased by one. This is in contrast to an insertion where a rotation resulting in a balance factor of 0 indicated that the subtree's height has remained unchanged.

The time required is O(log n) for lookup, plus a maximum of O(log n) rotations on the way back to the root, so the operation can be completed in O(log n) time.

---------------------------------------------------------

Red black tree with size attribute in each node, page 341, CLRS

Retrieving an element with a given rank

OS-SELECT.x; i /

1 r D x:left:size C 1

2 if i == r

3 return x

4 elseif i < r

5 return OS-SELECT.x: left; i/

6 else return OS-SELECT.x:right; i r/

Determining the rank of an element

OS-RANK.T; x/

1 r D x:left:size C 1

2 y D x

3 while y ¢¥ T:root

4 if y == y:p:right

5 r D r C y:p: left:size C 1

6 y D y:p

7 return r

--------------------------------------------------
List all keys between two given keys in a bst

LIST(tree;l;h)
lca=LCA(tree;l;h)
result=[]
NODE-LIST(lca;l;h;result)
return result

NODE-LIST(node;l;h;result)
if node==NIL
return
if l <= node.key and node.key >= h
ADD-KEY(result;node:key)
if node.key >= l
NODE-LIST(node.left;l;h;result)
if node.key <= h
NODE-LIST(node.right;l;h;result)

LCA(tree;l;h)
node=tree:root
until node==NIL or (l <= node.key and h >= node.key)
if l < node.key
node = node.left
else
node = node.right
return node

Day 75, ##, Max Points on a Line

Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
---------------------------------------------------------------------------------
O(n^2)

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int maxP = 2;
        if (points.size() == 0 || points.size() == 1) return points.size();
 
        for (int i = 0; i < points.size(); i++) {
            unordered_map<double,int> slopes;
            int samex = 1;
            int samePoints = 0;
            int curMax = 0;
             
            for (int j = i + 1; j < points.size(); j++) {
                double xdistance = points[i].x - points[j].x;
                double ydistance = points[i].y - points[j].y;
                if (xdistance == 0 && ydistance == 0) {
                    samePoints++;
                    continue;
                }else if (xdistance == 0) {
                    samex++;
                    continue;
                }
                 
                double slope = ydistance / xdistance;
                 
                if (slopes.find(slope) == slopes.end()) {
                    slopes[slope] = 2;
                }else {
                    slopes[slope]++;
                }
             
                curMax = max(curMax,max(samex,slopes[slope]));
            }

            curMax = max(samex,curMax);
            maxP = max(maxP,curMax + samePoints);
        }
        return maxP;
    }
     
};

## other: Longest common subsequence

http://lintcode.com/en/problem/longest-common-subsequence/
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).

If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

--------------------------
print the length of the longest common sub-sequence
DP
The actual sequence can be generated by using backtrack.
Reference:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

int lcs (string a, string b) {
    int m = a.length();
    int n = b.length();
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i < m + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            if (a[i] == b[i]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            }else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
} 

-------------------------------------------------
Recursion

int lcs( char *X, char *Y, int m, int n )
{
   if (m == 0 || n == 0)
     return 0;
   if (X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

## Other: Check if a given Binary Tree is SumTree, Stack implementation

Check for SumTree

bool isLeaf (Node* root) {
    if (root->left == NULL && root->right == NULL) {
        return true;
    }
    else return false;
}


bool isSumTree (Node* root) {
    if (root == NULL || isLeaf(root)) {
        return true;
    }
    
    if (isSumTree(root->left) && isSumTree(root->right)) {
        int leftSum = 0, rightSum = 0;
        
        if (isLeaf(root->left)) {
            leftSum = left->val;
        }else if (root->left == NULL) {
            leftSum = 0;
        }else {
            leftSum = root->left->val * 2;
        }
        
        if (isLeaf(root->right)) {
            rightSum = right->val;
        }else if (root->right == NULL) {
            rightSum = 0;
        }else {
            rightSum = root->right->val * 2;
        }
        
        return root->val == (rightSum + leftSum);
    }
    
    return false;
}

The algorithm would be the same if we want to turn a tree to a valid sum tree ------------------------------------------------ Q: Implement a Stack class with O(1) min function. A: use an extra stack to contain all min values, O(n) space, use (push 2 * value - min to stack) to optimize space to O(1)

Notes on Notes -- Chapter 1

string search algorithm

rabin-karp, rolling hash

kmp

------------------

e.g. 1 Given input "Mr John Smith", output "Mr%20John%20Smith" (CtCI 1.4)

e.g. 2 Given input "Mr%20John%20Smith" , output "Mr John Smith" (Facebook interview)

e.g. 3 Given two sorted arrays, merge B into A in sorted order. (CtCI 11.1, Leetcode: Merge Sorted Array)

扫描2次 + 倒叙赋值

 -------------------------------------

what is / how to use stringstream in c++

-------------------------------------------------

If mat[i][j] is 0, then set the entire row and column to 0

use first row and first column to store the matrix's rows' and columns' turns

-------------------------------------------------

Implement a method rand7() given rand5().(CtCI:17.11)

  

unsigned long hashstring(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

-------------------------------------------------

 A hash function for the state of a chess game.(EPI: 12.2) 

fun to read:  

http://stackoverflow.com/questions/1831386/programmer-puzzle-encoding-a-chess-board-state-throughout-a-game 

Day 74, ##, Sort List, Evaluate Reverse Polish Notation

Sort List
Sort a linked list in O(n log n) time using constant space complexity.
-----------------------------------------------------------------
Solution #1, recursive merge sort
wiki page has iterative buttom-up method
http://en.wikipedia.org/wiki/Merge_sort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge (ListNode *&left, ListNode *&right) {
        ListNode* dummy = new ListNode(INT_MIN); // dummy
        ListNode* itr = dummy;
        while (left != NULL && right != NULL) {
            if (left->val <= right->val) {
                itr->next = left;
                itr = left;
                left = left->next;
            }else {
                itr->next = right;
                itr = right;
                right = right->next;
            }
        }
        if (right == NULL) itr->next = left;
        if (left == NULL) itr->next = right;
        return dummy->next;
    }

    ListNode *sortList(ListNode *head) {
        // divide
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        ListNode *slow = head, *fast = head->next;
        while (fast != NULL) {
            fast = fast->next;
            if (fast != NULL) {
                fast = fast->next;
                slow = slow->next;
            }
        }
        ListNode *second = slow->next;
        slow->next = NULL;
        
        head = sortList(head);
        second = sortList(second);
        
        // merge
        return merge(head,second);
    }
};

Update Jan-5-2015
dummy should be deleted in merge

Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

----------------------------------------------------
post order, using stack
注意从stack出来时的顺序，RPN是最先进stack的在前面。

class Solution {
public:
    int arith (int op1, int op2, string opt) {
        if (opt == "+") {
            return op1 + op2;
        }else if (opt == "-") {
            return op1 - op2;
        }else if (opt == "*") {
            return op1 * op2;
        }else if (opt == "/") {
            return op1 / op2;
        }
    }

    int evalRPN(vector<string> &tokens) {
        stack<int> s;
        int num = 0;
        for (int i = 0; i < tokens.size(); i++) {
            if (isdigit(tokens[i][0]) || (tokens[i].length() > 1 && isdigit(tokens[i][1]))) {
                num = atoi(tokens[i].c_str());
            }else {
                int operand1 = s.top();
                s.pop();
                int operand2 = s.top();
                s.pop();
                num = arith(operand2,operand1,tokens[i]);
            }
            s.push(num);
        }
        return num;
    }
};

Day 73, ##, Reorder List, Binary Tree Preorder Traversal, Binary Tree Postorder Traversal, Insertion Sort List

Reorder List
Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
------------------------------------------------------------
3 steps:
1) divide list in half
2) reverse the second half
3) merge/reorder

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList (ListNode *head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *itr = head;
        head = NULL;
        while (itr != NULL) {
            ListNode *tmp = itr->next;
            itr->next = head;
            head = itr;
            itr = tmp;
        }
        return head;
    }

    void reorderList(ListNode *head) {
        // find the second half
        if (head == NULL || head->next == NULL) return;
        ListNode *slow = head, *fast = head;
        
        while (fast != NULL) {
            fast = fast->next;
            if (fast!= NULL) {
                slow = slow->next;
                fast = fast->next;
            }
        }
        
        // reverse
        ListNode *head2 = slow->next;
        slow->next = NULL;
        head2 = reverseList(head2);
        
        // merge
        ListNode *cur = head;
        while (head2 != NULL) {
            ListNode *temp = cur->next;
            ListNode *temp2 = head2->next;
            cur->next = head2;
            cur = temp;
            head2->next = cur;
            head2 = temp2;            
        }
    }
};

Solution#2, recursive
(to do)

Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
------------------------------------------------------------
Similar to #94 Binary Tree Inorder Traversal
using stack, push right node first, then left node

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> ret;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            if (node == NULL) continue;
            ret.push_back(node->val);
            s.push(node->right);
            s.push(node->left);
        }
        return ret;
    }
};

Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
----------------------------------------------------
Solution #1, with visited flag
Similar to #94 Binary Tree Inorder Traversal

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> ret;
        stack<pair<TreeNode*,bool> > s;
        s.push(make_pair(root,false));
         
        while (!s.empty()) {
            pair<TreeNode*,bool> p = s.top();
            if (p.first != NULL) {
                if (p.second == false) {
                    s.top().second = true;
                    s.push(make_pair(p.first->right,false));
                    s.push(make_pair(p.first->left,false));
                }else {
                    ret.push_back(p.first->val);
                    s.pop();
                }
            }else {
                s.pop();
            }
        }
        return ret;
    }
};

Solution #2, without visited flag

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> ret;
        if (root == NULL) return ret;
        stack<TreeNode*> s;
        s.push(root);
        TreeNode* pre = NULL;
        
        while (!s.empty()) {
            TreeNode* cur = s.top();
            // traverse down the tree
            if (!pre || pre->left == cur || pre->right == cur) {
                if (cur->left != NULL) {
                    s.push(cur->left);
                }else if (cur->right != NULL) {
                    s.push(cur->right);
                }else {
                    // reach a leaf node
                    ret.push_back(cur->val);
                    s.pop();
                }
            }
            else if (cur->left == pre) {
                // traverse from the left
                if (cur->right != NULL) {
                    s.push(cur->right);
                }else {
                    ret.push_back(cur->val);
                    s.pop();
                }
            }else if (cur->right == pre) {
                // from the right
                ret.push_back(cur->val);
                s.pop();
            }
            
            pre = cur;
        }
        
        return ret;
    }
};

Solution#3, using two stacks
Further reading
http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode*> roots;
        stack<TreeNode*> rights;
        vector<int> rt;
        
        while (root != NULL || !roots.empty() || !rights.empty()) {
            if (root != NULL) {
                roots.push(root);
                if (root->right != NULL) {
                    rights.push(root->right);
                }
                root = root->left;
                
            }else {
                if (!rights.empty() && roots.top()->right == rights.top()) {
                    root = rights.top();
                    rights.pop();
                    
                }else {
                    rt.push_back(roots.top()->val);
                    roots.pop();
                }
            }
        }
        
        return rt;
    }
};

Update on Feb-1st-2015
post-order is left -> right -> root, we can traverse the tree backwards: root -> right -> left, then reverse the result 

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vector<int> rt;
        if (root == NULL) return rt;
        
        st.push(root);
        while (!st.empty()) {
            TreeNode *node = st.top();
            st.pop();
            rt.push_back(node->val);
            if (node->left != NULL) {
                st.push(node->left);
            }
            if (node->right != NULL) {
                st.push(node->right);
            }
        }
        
        reverse(rt.begin(),rt.end());
        return rt;
    }
};

Insertion Sort List
Sort a linked list using insertion sort.
---------------------------------------------------
wiki
http://en.wikipedia.org/wiki/Insertion_sort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode *itr = head, *sorted = dummy;
        
        while (itr != NULL) {
            if (itr->val >= sorted->val) {
                itr = itr->next;
                sorted = sorted->next;
            }else {
                ListNode *n = dummy;
                while (n->next->val <= itr->val) {
                    n = n->next;
                }
                
                ListNode *tmp = itr->next;
                ListNode *tmp2 = n->next;
                n->next = itr;
                itr->next = tmp2;
                sorted->next = tmp;
                
                itr = tmp;
            }
        }
        return dummy->next;
    }
};