LeetCode 51 - N-Queens


LeetCode - N-Queens | Darren's Blog
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:


[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Recursive Version:


private void solve(char[][] curr, int idx, int n, List<List<String>> ret, boolean[] col, boolean[] diag1, boolean[] diag2) { if (idx == n) { List<String> toAdd = new ArrayList<>(); for (int i = 0; i < n; i ++) { toAdd.add(String.valueOf(curr[i])); } ret.add(toAdd); return; } for (int j = 0; j < n; j ++) { if (col[j] || diag1[idx + n - j - 1] || diag2[idx + j]) { continue; } col[j] = true; diag1[idx + n - j - 1] = true; diag2[idx + j] = true; curr[idx][j] = 'Q'; solve(curr, idx + 1, n, ret, col, diag1, diag2); curr[idx][j] = '.'; col[j] = false; diag1[idx + n - j - 1] = false; diag2[idx + j] = false; } } public List<List<String>> solveNQueens(int n) { List<List<String>> ret = new ArrayList<>(); char[][] curr = new char[n][n]; for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { curr[i][j] = '.'; } } boolean[] col = new boolean[n]; boolean[] diag1 = new boolean[2 * n - 1]; boolean[] diag2 = new boolean[2 * n - 1]; solve(curr, 0, n, ret, col, diag1, diag2); return ret; }

https://segmentfault.com/a/1190000003762668
时间 O(N^2) 空间 O(N)
该方法的思路和暴力法一样，区别在于，之前我们判断一个皇后是否冲突，是遍历一遍当前皇后排列的列表，看每一个皇后是否冲突。这里，我们用三个集合来保存之前皇后的信息，就可以O(1)时间判断出皇后是否冲突。三个集合分别是行集合，用于存放有哪些行被占了，主对角线集合，用于存放哪个右上到左下的对角线被占了，副对角线集合，用于存放哪个左上到右下的对角线被占了。如何唯一的判断某个点所在的主对角线和副对角线呢？我们发现，两个点的行号加列号的和相同，则两个点在同一条主对角线上。两个点的行号减列号的差相同，则两个点再同一条副对角线上。
主对角线row + col，副对角线row - col
    List<List<String>> res = new LinkedList<List<String>>();;
    Set<Integer> rowSet = new HashSet<Integer>();
    Set<Integer> diag1Set = new HashSet<Integer>();
    Set<Integer> diag2Set = new HashSet<Integer>();
    
    public List<List<String>> solveNQueens(int n) {
        helper(new LinkedList<Integer>(), n, 0);
        return res;
    }
    
    public void helper(LinkedList<Integer> tmp, int n, int col){
        if(col == n){
            List<String> one = new LinkedList<String>();
            for(Integer num : tmp){
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append('.');
                }
                sb.append('Q');
                for(int j = num + 1; j < n; j++){
                    sb.append('.');
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            // 对于列col，看皇后应该放在第几行
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                // 如果三条线上已经有占据的皇后了，则跳过该种摆法
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                // 用回溯法递归求解
                tmp.add(row);
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(tmp, n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
                tmp.removeLast();
            }
        }
    }
However, I suggest that let's use 3 boolean arrays instead. Let's compare the run time:
  1. HashSet: 15ms, beats 17.85%
  2. Boolean Array: 5ms, beats 91.44%
More Efficient? - Seems so. - List<String>
    private Set<Integer> col = new HashSet<Integer>();
    private Set<Integer> diag1 = new HashSet<Integer>();
    private Set<Integer> diag2 = new HashSet<Integer>();
    
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        dfs(res,new ArrayList<String>(), 0, n);
        return res;
    }
    private void dfs(List<List<String>> res, List<String> list, int row, int n){
        if (row == n){
            res.add(new ArrayList<String>(list));
            return;
        }
        for (int i = 0; i < n; i++){
            if (col.contains(i) || diag1.contains(row + i) || diag2.contains(row - i)) continue;
            
            char[] charArray = new char[n];
            Arrays.fill(charArray, '.');
            charArray[i] = 'Q';
            String rowString = new String(charArray);
            
            list.add(rowString);
            col.add(i);
            diag1.add(row + i);
            diag2.add(row - i);
            
            dfs(res, list, row + 1, n);
            
            list.remove(list.size() - 1);
            col.remove(i);
            diag1.remove(row + i);
            diag2.remove(row - i);
        }
    }
https://leetcode.com/discuss/24717/comparably-concise-java-code
    private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2, 
                        String[] board, List<String[]> res) {
        if (r == board.length) res.add(board.clone());
        else {
            for (int c = 0; c < board.length; c++) {
                int id1 = r - c + board.length, id2 = 2*board.length - r - c - 1;
                if (!cols[c] && !d1[id1] && !d2[id2]) {
                    char[] row = new char[board.length];
                    Arrays.fill(row, '.'); row[c] = 'Q';
                    board[r] = new String(row);
                    cols[c] = true; d1[id1] = true; d2[id2] = true;
                    helper(r+1, cols, d1, d2, board, res);
                    cols[c] = false; d1[id1] = false; d2[id2] = false;
                }
            }
        }
    }
    
    public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        helper(0, new boolean[n], new boolean[2*n], new boolean[2*n], 
            new String[n], res);
        return res;
    }

I use three boolean[] array to keep tracking of the position the Queen take in the helper method.
  1. boolean[] cols is for check if the certain column is taken.
  2. I use two boolean[2*n] array to keep tracking of two diagonals.
  3. for the diagonal in the \ direction (from left up corner to right down corner) the col - row will always be same e.g. (0,1), (1,2), (2,3) are on the same diagonal, the range of col - row can be (0-(n-1)) ~ ((n-1)-0), to make sure we can store the value in one array, we will add n to this, it will become to keep tracking of (col - row + n).
  4. for the diagonal in the / direction (from right up corner to left down corner) the col + row will always be same e.g. (0,4), (1,3), (2,2), (3,1), (4,0) are on the same diagonal, the range of row + col can be 0 ~ (2*n-2)
public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<List<String>>(); helper(result, new ArrayList<String>(), 0, new boolean[n], new boolean[2*n], new boolean[2*n], n); return result; } private void helper(List<List<String>> result, List<String> board, int row, boolean[] cols,
boolean[] d1, boolean[] d2, int n){ if (row == n) { result.add(new ArrayList<String>(board)); } for (int col=0; col<n; col++){ int id1 = col - row + n; int id2 = col + row; if (!cols[col] && !d1[id1] && !d2[id2]){ char[] r = new char[n]; Arrays.fill(r, '.'); r[col] = 'Q'; board.add(new String(r)); cols[col] = true; d1[id1] = true; d2[id2] = true; helper(result, board, row+1, cols, d1, d2, n); board.remove(board.size()-1); cols[col] = false; d1[id1] = false; d2[id2] = false; } } }

时间 O(N^3) 空间 O(N)
因为n皇后问题中，同一列不可能有两个皇后，所以我们可以用一个一维数组来表示二维棋盘上皇后的位置。一维数组中每一个值的下标代表着对应棋盘的列，每一个值则是那一列中皇后所在的行。这样我们可以只对一个一维数组进行深度优先搜索，来找出对于每一列，我们的皇后应该放在哪一行。在下一轮搜索之前，我们先检查一下新构成的数组是否是有效的，这样可以剪掉不必要的分支。检查的方法则是看之前排好的每一个皇后是否冲突。
    List<List<String>> res;
    
    public List<List<String>> solveNQueens(int n) {
        res = new LinkedList<List<String>>();
        int[] nqueens = new int[n];
        helper(nqueens, n, 0);
        return res;
    }
    
    public void helper(int[] nqueens, int n, int i){
        if(i == nqueens.length){
            List<String> one = new LinkedList<String>();
            // 构成表示整个棋盘的字符串
            for(int num : nqueens){
                // 构成一个形如....Q....的字符串
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append('.');
                }
                sb.append('Q');
                for(int j = num + 1; j < n; j++){
                    sb.append('.');
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            //选择下一列的数字
            // 比如之前已经选了13xxxxxx，下一列可以选6，形成136xxxxx
            for(int num = 0; num < n; num++){
                nqueens[i] = num;//
                // 如果是有效的，继续搜索
                if(isValid(nqueens, i)){//more readable: put here: nqueens[i] = num;
                    helper(nqueens, n, i+1);
                }
            }
        }
    }
    
    private boolean isValid(int[] nqueens, int i){
        for(int idx = 0; idx < i; idx++){
            // 检查对角线只要判断他们差的绝对值和坐标的差是否相等就行了
            if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) ==  i - idx){
                return false;
            }
        }
        return true;
    }
https://leetcode.com/discuss/67227/concise-java-solution-based-on-dfs
// Good variable name:
public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> result = new ArrayList<String[]>();
        recursiveNQueens(n, 0, new int[n], result);
        return result;
    }
    // If "currentRow" is n, we have reached a solution based on "queenInColumn",
    // and put it into "result"; Otherwise, we put a queen at each valid column
    // in Row "currentRow", and recursively work on the next row.
    private void recursiveNQueens(int n, int currentRow, int[] queenInColumn,
                                  ArrayList<String[]> result) {
        if (currentRow == n) {      // We have placed n queens
            // Construct a solution based on "queenInColumn"
            String[] solution = new String[n];
            for (int i = 0; i < n; i++) {
                StringBuilder row = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (queenInColumn[i] == j)  // There is a queen at Row i and Column j
                        row.append('Q');
                    else
                        row.append('.');
                }
                solution[i] = row.toString();
            }
            // Add the solution to "result"
            result.add(solution);
        } else {
            // Put a queen at each valid column in the current row, and recursively
            // work on the next row
            for (int j = 0; j < n; j++) {
                if (isValid(j, currentRow, queenInColumn)) {
                    // A queen at Column j in the currentRow is valid
                    queenInColumn[currentRow] = j;
                    recursiveNQueens(n, currentRow+1, queenInColumn, result);
                }
            }
        }
    }
    // Indicate whether a queen can be put at (workingRow, attemptedColumn)
    // without violating the rules
    private boolean isValid(int attemptedColumn, int workingRow, int[] queenInColumn) {
        // Verify all the rules
        // No row conflict automatically since we put only one queen in each row
        for (int i = 0; i < workingRow; i++) {
            if (attemptedColumn == queenInColumn[i] ||      // No column conflict
                    (workingRow-i == Math.abs(attemptedColumn-queenInColumn[i])))   // No diagnal conflict
                return false;
        }
        return true;
    }
1. 逐行放置皇后：排除在同一行的可能。
2. 记录之前所放皇后的列坐标：col[i]=j表示第i行的皇后在第j列。这样在放置第i+1行时，只要保证col[i+1] != col[k], k=0...i 即可。
3. 对角线判断：对于任意(i1, col[i1])和(i2, col[i2])，只有当abs(i1-i2) = abs(col[i1]-col[i2])时，两皇后才在同一对角线
在放置的时候，要保持当前的状态为合法，即当前放置位置的同一行、同一列、两条对角线上都不存在皇后。
http://www.cnblogs.com/springfor/p/3870944.html
难点大概就是用1个一维数组存皇后所在的坐标值。对于一个棋盘来说，每个点都有横纵坐标，用横纵坐标可以表示一个点。
而这道题巧就巧在，每一行只能有一个皇后，也就是说，对于一行只能有一个纵坐标值，所以用1维数组能提前帮助解决皇后不能在同一行的问题。
那么用一维数组表示的话，方法是：一维数组的下标表示横坐标（哪一行），而数组的值表示纵坐标（哪一列）。

例如：对于一个4皇后问题，声明一个长度为4的数组（因为行数为4）。
     A[] = [1,0,2,3]表达含义是：
     当前4个皇后所在坐标点为：[[0,1],[1,0],[2,2],[3,3]]（被我标蓝的正好是数组的下标，标粉的正好是数组的值）
     相当于：A[0] = 1, A[1] = 0, A[2] = 2, A[3] = 3 

这样以来，皇后所在的坐标值就能用一维数组表示了。
而正是这个一维数组，在回溯找结果的时候不需要进行remove重置操作了，因为回溯的话正好就回到上一行了，就可以再重新找下一个合法列坐标了。
http://rleetcode.blogspot.com/2014/02/leetcode-n-queens-puzzle-is-problem-of.html
Eight queens problem
public void solve(int size) {
012.boolean[][] array = new boolean[size][size];
013.solveQueensProblem(array, 0, 0, true, 0);
014.solveQueensProblem(array, 0, 0, false, 0);
015.}
021.* @param set true if the queen should be placed, false otherwise
022.
024.private void solveQueensProblem(boolean[][] array, int x, int y, boolean set, int queensCount) {
025.array[y][x] = set;
026.if (set && !checkConsistency(array, x, y)) {
027.return;
028.}
029.if (set) {
030.queensCount++;
031.}
032. 
033.if (queensCount == array.length) {
034.solutionsCount++;
035.printArray(array);
036.return; //solution found
037.}
038.x = x + 1; //increment x
039.int overflow = x == array[y].length ? 1 : 0;
040.if (overflow == 1) {//if x overflowed
041.x = 0; //set to 0
042.y += 1; //increment y
043.}
044. 
045.if (y >= array.length) {
046.return; //end of the problem, all decisions have been made
047.}
048.//lets make both decisions
049.solveQueensProblem(array, x, y, true, queensCount);
050.solveQueensProblem(array, x, y, false, queensCount);
051. 
052.}
  1. vector<vector<string> > solveNQueens(int n)   
  2.     {  
  3.         vector<string> board(n,string(n, '.'));  
  4.         vector<vector<string> > rs;  
  5.         solNQueens(rs, board);  
  6.         return rs;  
  7.     }  
  8.     void solNQueens(vector<vector<string> > &rs, vector<string> &board, int row=0)  
  9.     {  
  10.         if (row == board.size()) rs.push_back(board);  
  11.   
  12.         for (int col = 0; col < board.size(); col++)  
  13.         {  
  14.             if (isLegal(board, row, col))  
  15.             {  
  16.                 board[row][col] = 'Q';  
  17.                 solNQueens(rs, board, row+1);  
  18.                 board[row][col] = '.';  
  19.             }     
  20.         }  
  21.     }  
X. BitMap
https://leetcode.com/discuss/75588/a-concise-java-solution-using-bitmap-0-ms
For example, in 4 queens problem, row = "0110" means column 1 and 2 in this row is occupied by queens in above rows. ld means columns occupied by the left diagonal, and rd means columns occupied by the right diagonal.
int sum = 0, upperlimit = 1;

public int totalNQueens(int n) {
    upperlimit = (1 << n) - 1;//"11...11"
    totalNQueens(0, 0, 0);
    return sum;
}

void totalNQueens(int row, int ld, int rd) {
    int placeable = upperlimit & ~(row | ld | rd);//Get all placeable positions in this row

    if (row != upperlimit) {
        while (placeable != 0) {
            int pos = placeable & (~placeable + 1);//Get the right most placeable position
            placeable -= pos;//Remove position from placeable
            totalNQueens(row | pos, (ld | pos) << 1, (rd | pos) >> 1); //Get occupied columns of the next row and go to next
        }
    } else {
        sum++;
    }
}
https://github.com/iamzhaozheng/leetcode/blob/master/src/com/hisrv/leetcode/NQueens.java
private ArrayList<String[]> mRet;
private int mSize;
private int mMask;

public ArrayList<String[]> solveNQueens(int n) {
      // Start typing your Java solution below
      // DO NOT write main() function
      mRet = new ArrayList<String[]>();
      mSize = n;
      mMask = (1 << mSize) - 1;
      queen(0, 0, 0, 0, new int[n]);
      return mRet;
  }

private void queen(int y, int left, int down, int right, int[] status) {
  if (y == mSize) {
    out(status);
  } else {
    int bitmap = mMask & ~(left | down | right);
    while (bitmap != 0) {
      int bit = -bitmap & bitmap;
      status[y] = bit;
      bitmap ^= bit;
      queen(y + 1, (left | bit) << 1, down | bit, (right | bit) >> 1, status);
    }
  }
}

private void out(int[] status) {
  int n = status.length;
  String[] strs = new String[n];
  for (int i = 0; i < n; i ++) {
    char[] s = new char[n];
    for (int j = 0; j < n; j ++) {
      s[j] = '.';
    }
    int p = log2(status[i]);
    s[p] = 'Q';
    strs[i] = new String(s);
  }
  mRet.add(strs);
}

private int log2(int a) {
  int r = 0;
  while (a > 1) {
    a = a / 2;
    r ++;
  }
  return r;
}
http://www.cnblogs.com/TenosDoIt/p/3801621.html
算法4（解释在后面）这应该是最高效的算法了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
private:
    vector<vector<string> > res;
    int upperlim;
public:
    vector<vector<string> > solveNQueens(int n) {
        upperlim = (1 << n) - 1;//低n位全部置1
        vector<string> cur(n, string(n, '.'));
        helper(0,0,0,cur,0);
        return res;
    }
     
    void helper(const int row, const int ld, const int rd, vector<string>&cur, const int index)
    {
        int pos, p;
        if ( row != upperlim )
        {
            pos = upperlim & (~(row | ld | rd ));//pos中二进制为1的位，表示可以在当前行的对应列放皇后
            //和upperlim与运算，主要是ld在上一层是通过左移位得到的，它的高位可能有无效的1存在，这样会清除ld高位无效的1
            while ( pos )
            {
                p = pos & (~pos + 1);//获取pos最右边的1,例如pos = 010110，则p = 000010
                pos = pos - p;//pos最右边的1清0
                setQueen(cur, index, p, 'Q');//在当前行，p中1对应的列放置皇后
                helper(row | p, (ld | p) << 1, (rd | p) >> 1, cur, index+1);//设置下一行
                setQueen(cur, index, p, '.');
            }
        }
        else//找到一个解
            res.push_back(cur);
    }
     
    //第row行，第loc1(p)列的位置放置一个queen或者清空queen，loc1(p)表示p中二进制1的位置
    void setQueen(vector<string>&cur, const int row, int p, char val)
    {
        int col = 0;
        while(!(p & 1))
        {
            p >>= 1;
            col++;
        }
        cur[row][col] = val;
    }
};

这个算法主要参考博客N皇后问题的两个最高效的算法，主要看helper函数，参数row、ld、rd分别表示在列和两个对角线方向的限制条件下，当前行的哪些地方不能放置皇后。如下图
image 
前三行放置了皇后，他们对第3行（行从0开始）的影响如下：                               本文地址
（1）列限制条件下，第3行的0、2、4列（紫色线和第3行的交点）不能放皇后，因此row = 101010
（2）左对角线限制条件下，第3行的0、3列（蓝色线和第3行的交点）不能放皇后，因此ld = 100100
（3）右对角线限制条件下，第3行的3、4、5列（绿色线和第3行的交点）不能放皇后，因此rd = 000111

~(row | ld | rd) = 010000，即第三行只有第1列能放置皇后。
在3行1列这个位置放上皇后，row，ld，rd对下一行的影响为：
row的第一位置1，变为111010
ld的第一位置1，并且向左移1位（因为左对角线对行的影响是依次向左倾斜的），变为101000
rd的第一位置1，并且向右移1位（因为右对角线对行的影响是依次向右倾斜的），变为001011

第4行状态如下图
image 

Iterative Version from http://blog.csdn.net/kenden23/article/details/18136889
vector<vector<string> > solveNQueens(int n)
{
vector<string> board(n,string(n, '.'));
vector<vector<string> > rs;
int row = 0;
vector<int> backtrackCol(n, -1);
while (row >= 0)
{
int col = 0;
if (backtrackCol[row] != -1)
{
col = backtrackCol[row]+1;
board[row][col-1] = '.';
}
for (; col < n; col++)
{
if (isLegal(board, row, col))
{
board[row][col] = 'Q';
backtrackCol[row] = col;
if (row == n-1)
{
rs.push_back(board);
backtrackCol[row] = -1;
board[row][col] = '.';
row--;
break;
}
row++;
break;
}
}
if (col == n)
{
backtrackCol[row] = -1;
row--;
}
}
return rs;
}
bool isLegal(const vector<string> &board, int row, int col)
{
for (int i = 0; i < row; i++)
{
if (board[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i>=0 && j>=0; i--, j--)
{
if (board[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i>=0 && j<board.size(); i--, j++)
{
if (board[i][j] == 'Q') return false;
}
return true;
}
http://www.cnblogs.com/TenosDoIt/p/3801621.html

http://www.cnblogs.com/TenosDoIt/p/3801621.html


X. Inefficent
https://leetcode.com/discuss/47517/my-easy-understanding-java-solution
public List<List<String>> solveNQueens(int n) { char[][] board = new char[n][n]; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) board[i][j] = '.'; List<List<String>> res = new ArrayList<List<String>>(); dfs(board, 0, res); return res; } private void dfs(char[][] board, int colIndex, List<List<String>> res) { if(colIndex == board.length) { res.add(construct(board)); return; } for(int i = 0; i < board.length; i++) { if(validate(board, i, colIndex)) { board[i][colIndex] = 'Q'; dfs(board, colIndex + 1, res); board[i][colIndex] = '.'; } } } private boolean validate(char[][] board, int x, int y) { for(int i = 0; i < board.length; i++) { for(int j = 0; j < y; j++) { if(board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i)) return false; } } return true; } private List<String> construct(char[][] board) { List<String> res = new LinkedList<String>(); for(int i = 0; i < board.length; i++) { String s = new String(board[i]); res.add(s); } return res; }
List<String[]> list = new ArrayList<String[]>(); public List<String[]> solveNQueens(int n) { int[][] b = new int[n][n]; dfs(b, 0, n); return list; } public void dfs(int[][] b, int col, int n) { if (col == n) { list.add(printS(b, n)); return; } for (int row = 0; row < n; row ++) { if (isSafe(b, row, col, n)) { b[row][col] = 1; dfs(b, col + 1, n); b[row][col] = 0; } } }
ublic boolean isSafe (int[][]matrix, column, int row, int n){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==row && matrix[i][j]==1) return false; if(j==column&& matrix[i][j]==1) return false; if((Math.abs(row-i)==Math.abs(column-j))&&(matrix[i][j]==1)) return false; } } return true; }
Read full article from LeetCode - N-Queens | Darren's Blog
at
Labels: , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts