Monday, April 17, 2017

LeetCode 552 - Student Attendance Record II


https://leetcode.com/problems/student-attendance-record-ii
Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7.
A student attendance record is a string that only contains the following three characters:
  1. 'A' : Absent.
  2. 'L' : Late.
  3. 'P' : Present.
A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
Example 1:
Input: n = 2
Output: 8 
Explanation:
There are 8 records with length 2 will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times. 
Note: The value of n won't exceed 100,000.
X.
定义了三个DP数组P, L, A,其中P[i]表示数组[0,i]范围内以P结尾的所有排列方式,L[i]表示数组[0,i]范围内以L结尾的所有排列方式,A[i]表示数组[0,i]范围内以A结尾的所有排列方式。那么最终我们所求的就是P[n-1] + L[n-1] + A[n-1]了。那么难点就是分别求出P, L, A数组的递推公式了。
首先来看P数组的,P字符没有任何限制条件,可以跟在任何一个字符后面,所以有 P[i] = A[i-1] + P[i-1] + L[i-1]
再来看L数组的,L字符唯一的限制条件是不能有超过两个连续的L,那么在P和L字符后面可以加1一个L,如果前一个字符是L,我们要看再前面的一位是什么字符,如果是P或着A的话,可以加L,如果是L的话,就不能再加了,否则就连续3个了,所以有 L[i] = A[i-1] + P[i-1] + A[i-2] + P[i-2]
最后来看A数组的,这个比较麻烦,字符A的限制条件是整个字符串最多只能有1个A,那么当前一个字符是A的话,就不能再加A来,当前一个字符是P或者L的话,要确定之前从没有A出现过,才能加上A。那么实际上我们还需要定义两个数组P1, L1, 其中P1[i]表示数组[0,i]范围内以P结尾的不包含A的所有排列方式,L1[i]表示数组[0,i]范围内以L结尾的不包含A的所有排列方式,根据前两种情况我们不难推出P1和L1的递推公式,再加上A的递推公式如下:
A[i] = P1[i-1] + L1[i-1]
P1[i] = P1[i-1] + L1[i-1]
L1[i] = P1[i-1] + P1[i-2]
将第二第三个等式多次带入第一个等式,就可以将P1和L1消掉,可以化简为:
A[i] = A[i-1] + A[i-2] + A[i-3]
这样就可以少定义两个数组了,递推公式有了
https://discuss.leetcode.com/topic/86696/share-my-o-n-c-dp-solution-with-thinking-process-and-explanation
Before introducing the way to calculate the number of all possible attendance records with length n, we divide the problem into 3 parts.

As the attendance records is made by 3 charactors ('P', 'L', 'A'), the total number can be divided into

Total = ended with P + ended with L + ended with A.


If we define following series

T(n) is the total number of all possible attendance records with length n.

P(n) is the total number of all possible attendance records ended with 'P' with length n.

L(n) is the total number of all possible attendance records ended with 'L' with length n.

A(n) is the total number of all possible attendance records ended with 'A' with length n.


It can be inferred that

T(n) = A(n) + P(n) + L(n), n ≥ 1.


2.2 Solve the sub-problems by dynamic programming


As I use dynamic programming, I need to find out the recursive relation in 3 sub-problems.

2.2.1 CALCULATE P(N)

It can be inferred that

If we add a 'P' to an attendance records with length n - 1, we will get an attendance records ended with 'P' with length n.


For an attendance record with length n - 1,
  • If its (n - 1)th charactor is 'P' ---- CAN add 'P'. ("PP")

  • If its (n - 1)th charactor is 'A' ---- CAN add 'P'. ("AP")

  • If its (n - 1)th charactor is 'L' ---- CAN add 'P'. ("LP")


which means

P(n) = A(n - 1) + P(n - 1) + L(n - 1), n ≥ 2.


and we have initial value for the recursive relation

A(1) = P(1) = L(1) = 1.


2.2.2 CALCULATE L(N)

Similarly,

If we add a 'L' to an attendance records with length n - 1, we will get an attendance records ended with 'L' with length n.

But the resulting attendance records must be regared as rewardable!

As the rule is that a record is regarded as rewardable if it doesn't contain

more than two continuous 'L' (late).


We need to consider the situations when we can add 'L' to an attendance record with length n - 1 and it's still regared as rewardable.

For an attendance record with length n - 1,
  • If its (n - 1)th charactor is 'P' ---- CAN add 'L'. ("PL")

  • If its (n - 1)th charactor is 'A' ---- CAN add 'L'. ("AL")


  • If its (n - 1)th charactor is 'L':

    • If its (n - 2)th charactor is 'A' ---- CAN add 'L'. ("ALL")

    • If its (n - 2)th charactor is 'P' ---- CAN add 'L'. ("PLL")

    • If its (n - 2)th charactor is 'L' ---- CAN NOT add 'L'. ("LLL" breaks the rule)


which means

L(n) = A(n - 1) + P(n - 1) + A(n - 2) + P(n - 2), n ≥ 3


and we have initial value for the recursive relation

A(1) = P(1) = 1.

A(2) = 2, P(2) = 3.

and

L(1) = 1, L(2) = 3.


2.2.3 CALCULATE A(N)

Similarly,

If we add a 'A' to an attendance records with length n - 1, we will get an attendance records ended with 'A' with length n.

But the resulting attendance records must be regared as rewardable!

As the rule is that a record is regarded as rewardable if it doesn't contain

more than one 'A' (absent).


We need to consider the situations when we can add 'A' to an attendance record with length n - 1 and it's still regared as rewardable.

For an attendance record with length n - 1,
  • If its (n - 1)th charactor is 'A' ---- CAN NOT add 'A'. ("AA" breaks the rule)
  • If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'A'.
  • If its (n - 1)th charactor is 'L' and has no 'A' ---- CAN add 'A'.

If we define series

noAP(n) is the total number of all possible attendance records ended with 'P' with length n and with no 'A'.

noAL(n) is the total number of all possible attendance records ended with 'L' with length n and with no 'A'.


It can be infered that

A(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

and we have initial value for the recursive relation

A(1) = 1.

noAP(1) = noAL(1) = 1.


2.2.4 CALCULATE NOAP(N) AND NOAL(N)

In 2.2.3, 2 new series noAP(n) and noAL(n) is introduced. Now, we focus on the recursive relation in noAP(n) and noAL(n).

For noAP(n), we need to consider the situations when we can add 'P' to an attendance record with length n - 1 and no 'A' and it's still regared as rewardable.

Since noAP(n) has no 'A', we don't need to consider the situation when its (n - 1)th charactor is 'A'.

For an attendance record with length n - 1, we can get only 2 situations
  • If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'P'.
  • If its (n - 1)th charactor is 'L' and has no 'A' ---- CAN add 'P'.

which means

noAP(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

and we have initial value for the recursive relation

noAP(1) = noAL(1) = 1.


For noAL(n), we need to consider the situations when we can add 'L' to an attendance record with length n - 1 and no 'A' and it's still regared as rewardable.

Since noAL(n) has no 'A', we don't need to consider the situation when its (n - 1)th charactor is 'A'.

For an attendance record with length n - 1, we can get
  • If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'L'.("PL")
  • If its (n - 1)th charactor is 'L' and has no 'A'.
    • If its (n - 2)th charactor is 'P' and has no 'A' ---- CAN add 'L'.("PLL")
    • If its (n - 2)th charactor is 'L' and has no 'A' ---- CAN NOT add 'L'.("LLL" breaks the rule.)

which means

noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

and we have initial value for the recursive relation

noAP(1) = noAL(1) = 1.

and

noAL(2) = 2.


2.3 Recursive relationship summarization


The answer to the whole problem is T(n), and

T(n) = A(n) + P(n) + L(n), n ≥ 1.


Recursive formula:

P(n) = A(n - 1) + P(n - 1) + L(n - 1), n ≥ 2.

A(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

noAP(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

L(n) = A(n - 1) + P(n - 1) + A(n - 2) + P(n - 2), n ≥ 3.

noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

with Initial value

A(1) = P(1) = L(1) = 1.

noAP(1) = noAL(1) = 1.

L(2) = 3.

noAL(2) = 2.


2.4 Simplifying


When n ≥ 4, the 3 formulas

A(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

noAP(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

can be simplified to

A(n) = A(n - 1) + A(n - 2) + A(n - 3), n ≥ 4.


Finally, the recursive formula group becomes

P(n) = A(n - 1) + P(n - 1) + L(n - 1), n ≥ 2.

L(n) = A(n - 1) + P(n - 1) + A(n - 2) + P(n - 2), n ≥ 3.

A(n) = A(n - 1) + A(n - 2) + A(n - 3), n ≥ 4.

Here, noAP(n) and noAL(n) disappeared.

with Initial value

P(1) = 1.

L(1) = 1, L(2) = 3.

A(1) = 1, A(2) = 2, A(3) = 4.


2.5 Do modulus


The result need to be returned after mod 10⁹ + 7.
Since the result is generated by adding a lot of middle results together, in order to make sure that every middle result and the final result won't exceed INT_MAX, we need to do mod for every middle result, and for every 2-middle-result-addition.

3. Complexity Analyse


3.1 Time complexity


Since the algothrim is one-pass from 1 to n.

The time complexity is O(n).


3.2 Space complexity


Since 3 arrays are used to save P(n), L(n), A(n), the total size is 3n.

The space complexity is O(n).

http://blog.csdn.net/zshouyi/article/details/71157585
    int checkRecord(int n) {
        int m = 1000000007;
        int *A = new int [n];
        int *P = new int [n];
        int *L = new int [n];
        
        P[0] = 1;
        L[0] = 1;
        L[1] = 3;
        A[0] = 1;
        A[1] = 2;
        A[2] = 4;
        
        if(n == 1) return 3;
        
        for(int i = 1; i < n; i++)
        {
            A[i - 1] %= m;
            P[i - 1] %= m;
            L[i - 1] %= m;
            
            P[i] = ((A[i - 1] + P[i - 1]) % m + L[i - 1]) % m;
            
            if(i > 1) L[i] = ((A[i - 1] + P[i - 1]) % m + (A[i - 2] + P[i - 2]) % m) % m;
            
            if(i > 2) A[i] = ((A[i - 1] + A[i - 2]) % m + A[i - 3]) % m;
        }
        
        return ((A[n - 1] % m + P[n - 1] % m) % m + L[n - 1] % m) % m;
    }


X.
http://www.cnblogs.com/grandyang/p/6866756.html
这道题是之前那道Student Attendance Record I的拓展,但是比那道题难度要大的多。从题目中说结果要对一个很大的数取余,说明结果是一个很大很大的数。那么一般来说这种情况不能用递归来求解,可能会爆栈,所以要考虑利用数学方法或者DP来做
我们定义一个三维的dp数组,其中dp[i][j][k] 表示数组前i个数字中,最多有j个A,最多有k个连续L的组合方式,那么我们最终要求的结果就保存在dp[n][1][2]中。然后我们来考虑如何求dp[i][j][k],首先我们来取出前一个状态下的值,就是前i-1个数的值,dp[i-1][j][2],即数组前i-1个数中,最多有j个A,最多有2个连续L的排列方式,然后如果j>0,那么再加上dp[i-1][j-1][2],即加上了最多有j-1个A的情况,并对超大数取余;如果k>0,则再加上dp[i-1][j][k-1],即加上了最多有j个A,最多有k-1个连续L的排列方式,其实博主并没有完全理解为什么要这么更新
https://discuss.leetcode.com/topic/86526/improving-the-runtime-from-o-n-to-o-log-n
Let f[i][j][k] denote the # of valid sequences of length i where:
  1. There can be at most j A's in the entire sequence.
  2. There can be at most k trailing L's.
We give the recurrence in the following code, which should be self-explanatory, and the final answer is f[n][1][2].
public int checkRecord(int n) {
    final int MOD = 1000000007;
    int[][][] f = new int[n + 1][2][3];

    f[0] = new int[][]{{1, 1, 1}, {1, 1, 1}};
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 3; k++) {
                int val = f[i - 1][j][2]; // ...P
                if (j > 0) val = (val + f[i - 1][j - 1][2]) % MOD; // ...A
                if (k > 0) val = (val + f[i - 1][j][k - 1]) % MOD; // ...L
                f[i][j][k] = val;
            }
    return f[n][1][2];
}
The runtime of this solution is clearly O(n), using linear space (which can be easily optimized to O(1) though). Now, let's see how to further improve the runtime.
In fact, if we treat f[i][][] and f[i-1][][] as two vectors, we can represent the recurrence of f[i][j][k] as follows:
f[i][0][0]   | 0 0 1 0 0 0 |   f[i-1][0][0]
f[i][0][1]   | 1 0 1 0 0 0 |   f[i-1][0][1]
f[i][0][2] = | 0 1 1 0 0 0 | * f[i-1][0][2]
f[i][1][0]   | 0 0 1 0 0 1 |   f[i-1][1][0]
f[i][1][1]   | 0 0 1 1 0 1 |   f[i-1][1][1]
f[i][1][2]   | 0 0 1 0 1 1 |   f[i-1][1][2]
Let A be the matrix above, then f[n][][] = A^n * f[0][][], where f[0][][] = [1 1 1 1 1 1]. The point of this approach is that we can compute A^n using exponentiating by squaring (thanks to @StefanPochmann for the name correction), which will take O(6^3 * log n) = O(log n) time. Therefore, the runtime improves to O(log n), which suffices to handle the case for much larger n, say 10^18.
Update: The final answer is f[n][1][2], which involves multiplying the last row of A^n and the column vector [1 1 1 1 1 1]. Interestingly, it is also equal to A^(n+1)[5][2] as the third column of A is just that vector

final int MOD = 1000000007;
final int M = 6;

int[][] mul(int[][] A, int[][] B) {
    int[][] C = new int[M][M];
    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            for (int k = 0; k < M; k++)
                C[i][j] = (int) ((C[i][j] + (long) A[i][k] * B[k][j]) % MOD);
    return C;
}


int[][] pow(int[][] A, int n) {
    int[][] res = new int[M][M];
    for (int i = 0; i < M; i++)
        res[i][i] = 1;
    while (n > 0) {
        if (n % 2 == 1)
            res = mul(res, A);
        A = mul(A, A);
        n /= 2;
    }
    return res;
}

public int checkRecord(int n) {
    int[][] A = {
            {0, 0, 1, 0, 0, 0},
            {1, 0, 1, 0, 0, 0},
            {0, 1, 1, 0, 0, 0},
            {0, 0, 1, 0, 0, 1},
            {0, 0, 1, 1, 0, 1},
            {0, 0, 1, 0, 1, 1},
    };
    return pow(A, n + 1)[5][2];
}
https://discuss.leetcode.com/topic/86479/o-n-time-o-1-space-solution

http://code.bitjoy.net/2017/04/26/leetcode-student-attendance-record-ii/
显然是DP问题,不过是三维DP。令dp[n][i][j]表示长度为n的字符串,包含i个'A'并且以j个'L'结尾的字符串个数。那么有如下的递推公式:
dp[n][0][0]=sum(dp[n-1][0]):要求长度为n、包含0个'A',且以0个'L'结尾的字符串个数;所以前n-1肯定也只包含0个'A',但是前n-1可以以0、1或2个'L'结尾,因为我第n个字符不放'L'就能保证前n以0个'L'结尾。所以dp[n][0][0]=sum(dp[n-1][0])。其他的类似分析有:
  • dp[n][0][1]=dp[n-1][0][0]
  • dp[n][0][2]=dp[n-1][0][1]
  • dp[n][1][0]=sum(dp[n-1][0])+sum(dp[n-1][1])
  • dp[n][1][1]=dp[n-1][1][0]
  • dp[n][1][2]=dp[n-1][1][1]
    long long getSum(vector<int>& v) {
        long long ans = 0;
        for(const int &i : v) ans += i;
        return ans % kMOD;
    }
 
    int checkRecord(int n) {
        vector<vector<int>> dp = {{1, 1, 0}, {1, 0, 0}};
        for(int i = 2; i <= n; ++i){
            vector<vector<int>> ndp = {{0, 0, 0}, {0, 0, 0}};
            ndp[0][0] = getSum(dp[0]);
            ndp[0][1] = dp[0][0];
            ndp[0][2] = dp[0][1];
            ndp[1][0] = (getSum(dp[1]) + getSum(dp[0])) % kMOD;
            ndp[1][1] = dp[1][0];
            ndp[1][2] = dp[1][1];
            dp = ndp;
        }
        return (getSum(dp[0]) + getSum(dp[1])) % kMOD;
    }
X. DP
http://bookshadow.com/weblog/2017/04/16/leetcode-student-attendance-record-ii/
动态规划(Dynamic Programming)
利用dp[n][A][L]表示长度为n,包含A个字符'A',以L个连续的'L'结尾的字符串的个数。
状态转移方程:
dp[n][0][0] = sum(dp[n - 1][0])
dp[n][0][1] = dp[n - 1][0][0]
dp[n][0][2] = dp[n - 1][0][1]
dp[n][1][0] = sum(dp[n - 1][0]) + sum(dp[n - 1][1])
dp[n][1][1] = dp[n - 1][1][0]
dp[n][1][2] = dp[n - 1][1][1]

初始令dp[1] = [[1, 1, 0], [1, 0, 0]]
由于dp[n]只和dp[n - 1]有关,因此上述转移方程可以使用滚动数组,将空间复杂度降低一维。
private final int MOD = 1000000007; public long sum(int[] nums) { long ans = 0; for (int n : nums) ans += n; return ans % MOD; } public int checkRecord(int n) { int dp[][] = {{1, 1, 0}, {1, 0, 0}}; for (int i = 2; i <= n; i++) { int ndp[][] = {{0, 0, 0}, {0, 0, 0}}; ndp[0][0] = (int)sum(dp[0]); ndp[0][1] = dp[0][0]; ndp[0][2] = dp[0][1]; ndp[1][0] = (int)((sum(dp[0]) + sum(dp[1])) % MOD); ndp[1][1] = dp[1][0]; ndp[1][2] = dp[1][1]; dp = ndp; } return (int)((sum(dp[0]) + sum(dp[1])) % MOD); }

X.
http://www.cnblogs.com/grandyang/p/6866756.html
这里面定义了两个数组P和PorL,其中P[i]表示数组前i个数字中已P结尾的排列个数,PorL[i]表示数组前i个数字中已P或者L结尾的排列个数。这个解法的精髓是我们先不考虑字符A的情况,而是先把定义的这个数组先求出来,由于P字符可以再任意字符后面加上,所以 P[i] = PorL[i-1];而PorL[i]由两部分组成,P[i] + L[i],其中P[i]已经更新了,L[i]只能当前一个字符是P,或者前一个字符是L且再前一个字符是P的时候加上,即为P[i-1] + P[i-2],所以PorL[i] = P[i] + P[i-1] + P[i-2]。
那么我们就已经把不包含A的情况求出来了,存在了PorL[n]中,下面就是要求包含一个A的情况,那么我们就得去除一个字符,从而给A留出位置。那么就相当于在数组的任意一个位置上加上A,那么数组就被分成左右两个部分了,而这两个部分当然就不能再有A了,实际上所有不包含A的情况都已经在数组PorL中计算过了,而分成的子数组的长度又不会大于原数组的长度,所以我们直接在PorL中取值就行了,两个子数组的排列个数相乘,然后再把所有分割的情况累加起来就是最终结果啦

https://discuss.leetcode.com/topic/86507/simple-java-o-n-solution
P[i] = PorL[i - 1]; //this line means ending with P, just appending P in PorL
PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M; //P[i] end with P, P[i-1], end with one L(or PL), P[i-2], end with two L(or LL).
and last logic ,res init value with PorL without A, and add one A to the sequence.
long res = PorL[n];
for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
long s = (PorL[i] * PorL[n - i - 1]) % M;
res = (res + s) % M;
}
static final int M = 1000000007;

public int checkRecord(int n) {
    long[] PorL = new long[n + 1]; // ending with P or L, no A
    long[] P = new long[n + 1]; // ending with P, no A
    PorL[0] = P[0] = 1; PorL[1] = 2; P[1] = 1;

    for (int i = 2; i <= n; i++) {
        P[i] = PorL[i - 1];
        PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M;
    }
    
    long res = PorL[n];
    for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
     long s = (PorL[i] * PorL[n - i - 1]) % M;
        res = (res + s) % M;
    }
    
    return (int) res;
}



No comments:

Post a Comment

Labels

GeeksforGeeks (1109) LeetCode (1095) Review (846) Algorithm (795) to-do (633) LeetCode - Review (574) Classic Algorithm (324) Dynamic Programming (294) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (120) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (108) HackerRank (89) Binary Search (83) Binary Tree (82) Graph Algorithm (76) Greedy Algorithm (73) DFS (71) Stack (65) LeetCode - Extended (62) Interview Corner (61) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (49) Trie (49) Binary Search Tree (47) USACO (46) Interval (45) LeetCode Hard (42) Mathematical Algorithm (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) Matrix (39) Recursive Algorithm (39) String Algorithm (38) Union-Find (37) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) Data Structure Design (33) Segment Tree (33) Sliding Window (33) prismoskills (33) HDU (31) Priority Queue (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Microsoft 100 - July (28) Palindrome (28) to-do-must (28) Graph (27) Random (27) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Post-Order Traverse (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Binary Indexed Trees (22) Bisection Method (22) Hash (22) DFS + Review (21) Lintcode - Review (21) Two Pointers (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) LeetCode - DP (20) Merge Sort (20) O(N) (20) Follow Up (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Long Increasing Sequence(LIS) (13) Majority (13) Reverse Thinking (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) Miscs (11) Princeton (11) Proof (11) Rolling Hash (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) Facebook Hacker Cup (10) HackerRank Easy (10) O(1) Space (10) SPOJ (10) Theory (10) TreeMap (10) Tutorialhorizon (10) DP-Multiple Relation (9) DP-Space Optimization (9) Divide and Conquer (9) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stack Overflow (9) Stock (9) System Design (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) Interval Tree (8) Left and Right Array (8) Linked List (8) Longest Common Subsequence(LCS) (8) Prime (8) Suffix Tree (8) Tech-Queries (8) Traversal Once (8) 穷竭搜索 (8) Algorithm Problem List (7) Expression (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) TreeSet (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) DP-Print Solution (6) Dijkstra (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Manacher (6) Minimum Spanning Tree (6) Morris Traversal (6) Multiple Data Structures (6) One Pass (6) Programming Pearls (6) Pruning (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) Xpost (6) reddit (6) AI (5) Algorithm - Brain Teaser (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) Cycle (5) DP-Include vs Exclude (5) Fast Slow Pointers (5) Find Rule (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LeetCode - TODO (5) Matrix Chain Multiplication (5) Maze (5) Microsoft Interview (5) Pre-Sum (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) LeetCode - Recursive (4) MST (4) MinMax (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Probability (4) Programcreek (4) Spell Checker (4) Stock Maximize (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Algorithm - How To (3) Algorithm Design (3) B Tree (3) Big Data Algorithm (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Finite Automata (3) Github (3) GoLang (3) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) K (3) Knapsack-多重背包 (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) O(N) Hard (3) Online Algorithm (3) Parser (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Skyline (3) Stack - Smart (3) State Machine (3) Subtree (3) Transform Tree (3) Trie + DFS (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Ladder (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binary Search - Smart (2) Binomial Coefficient (2) Bit Counting (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Company-Snapchat (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) Edit Distance (2) Factor (2) Forward && Backward Scan (2) GoHired (2) Graham Scan (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Power (2) Median (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Parentheses (2) Peak (2) Programming (2) Range Minimum Query (2) Regular Expression (2) Return Multiple Values (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) SimHash (2) Simple Algorithm (2) Spatial Index (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Tree Without Tree Predefined (2) Word Break (2) Word Graph (2) Word Trie (2) Yahoo Interview (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Augmented BST (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Sarch Tree (1) Binary String (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Clean Code (1) Cloest (1) Clone (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Yelp (1) Compression Algorithm (1) Concise (1) Concurrency (1) Cont Improvement (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Diagonal (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Construction (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode - Thinking (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Machine Learning (1) Maintain State (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-End BFS (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Element (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) PreProcess (1) Probabilistic Data Structure (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) Square (1) Streaming Algorithm (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) Two-End-BFS (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Virtual Matrix (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts