## Saturday, June 18, 2016

### LeetCode 361 - Bomb Enemy

https://discuss.leetcode.com/topic/10/bomb-enemy/
Given a 2D grid, each cell is either a wall `'W'`, an enemy `'E'` or empty `'0'` (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.
Example:
```For the given grid

0 E 0 0
E 0 W E
0 E 0 0

return 3. (Placing a bomb at (1,1) kills 3 enemies)```
Main goal is how to use less space
X. https://discuss.leetcode.com/topic/48565/short-o-mn-time-o-n-space-solution
Walk through the matrix. At the start of each non-wall-streak (row-wise or column-wise), count the number of hits in that streak and remember it. O(mn) time, O(n) space.
``````int maxKilledEnemies(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
int result = 0, rowhits, colhits[n];
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (!j || grid[i][j-1] == 'W') {
rowhits = 0;
for (int k=j; k<n && grid[i][k] != 'W'; k++)
rowhits += grid[i][k] == 'E';
}
if (!i || grid[i-1][j] == 'W') {
colhits[j] = 0;
for (int k=i; k<m && grid[k][j] != 'W'; k++)
colhits[j] += grid[k][j] == 'E';
}
if (grid[i][j] == '0')//
result = max(result, rowhits + colhits[j]);
}
}
return result;
}``````
https://discuss.leetcode.com/topic/48742/simple-dp-solution-in-java
only need to store one killed enemies value for a row and an array of each column;
if current grid value is W, this means previous stored value becomes invalid, you need to recalculate.
I think it is O(m * n). Although there is another for loop k inside for loops of i and j. It just calculates the enemies in advance. In the end, it will traverse this grid once to compute the enemies that are killed.

it is little a DP-like SOLUTION, the only place col[], which is storing col enemies count, is only updated once for consecutive enemies column, and reused for later calculation (when there is '0', where bomb can be planted)

`````` public int maxKilledEnemies(char[][] grid) {
if(grid == null || grid.length == 0 ||  grid[0].length == 0) return 0;
int max = 0;
int row = 0;
int[] col = new int[grid[0].length];
for(int i = 0; i<grid.length; i++){
for(int j = 0; j<grid[0].length;j++){
if(grid[i][j] == 'W') continue;
if(j == 0 || grid[i][j-1] == 'W'){
row = killedEnemiesRow(grid, i, j);
}
if(i == 0 || grid[i-1][j] == 'W'){
col[j] = killedEnemiesCol(grid,i,j);
}
if(grid[i][j] == '0'){//
max = (row + col[j] > max) ? row + col[j] : max;
}
}

}

return max;
}

//calculate killed enemies for row i from column j
private int killedEnemiesRow(char[][] grid, int i, int j){
int num = 0;
while(j <= grid[0].length-1 && grid[i][j] != 'W'){
if(grid[i][j] == 'E') num++;
j++;
}
return num;
}
//calculate killed enemies for  column j from row i
private int killedEnemiesCol(char[][] grid, int i, int j){
int num = 0;
while(i <= grid.length -1 && grid[i][j] != 'W'){
if(grid[i][j] == 'E') num++;
i++;
}
return num;
}``````
X. O(mn) space
https://discuss.leetcode.com/topic/48603/java-straightforward-solution-dp-o-mn-time-and-space
The code might be a little bit long and there should exist more elegant one.
However the idea of this very straightforward. We do simply two traversals. One from upper left to bottom right, for each spot we compute enemies to its left and up including itself. The other traversal is from bottom right to upper left, we compute enemies to its right and down and in the same time we add them up all to find the maxKill.
``````    public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
Spot[][] spots = new Spot[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
spots[i][j] = new Spot();
if (grid[i][j] == 'W') {
continue;
}
spots[i][j].up = (i == 0 ? 0 : spots[i - 1][j].up) + (grid[i][j] == 'E' ? 1 : 0);
spots[i][j].left = (j == 0 ? 0 : spots[i][j - 1].left) + (grid[i][j] == 'E' ? 1 : 0);
}
}

int maxKill = 0;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 'W') {
continue;
}
spots[i][j].bottom = (i == m - 1 ? 0 : spots[i + 1][j].bottom) + (grid[i][j] == 'E' ? 1 : 0);
spots[i][j].right = (j == n - 1 ? 0 : spots[i][j + 1].right) + (grid[i][j] == 'E' ? 1 : 0);

if (grid[i][j] == '0') {
maxKill = Math.max(maxKill, spots[i][j].up + spots[i][j].left + spots[i][j].bottom + spots[i][j].right);
}
}
}
return maxKill;
}
class Spot {
int up; // enemies to its up including itself
int left; // enemies to its left including itself
int bottom;
int right;
}``````
X.
https://discuss.leetcode.com/topic/49109/straightforward-o-mn-java-solution-49ms
``````public int maxKilledEnemies(char[][] grid) {
int rowNum = grid.length;
if (rowNum == 0) return 0;
int colNum = grid[0].length;

int[][] fromBottom = new int[rowNum][colNum];
int[][] fromRight = new int[rowNum][colNum];

for (int i = rowNum - 1; i >= 0; i--) {
for (int j = colNum - 1; j >= 0; j--) {
int enemy = grid[i][j] == 'E' ? 1 : 0;
if (grid[i][j] != 'W') {
fromBottom[i][j] = (i == rowNum - 1) ? enemy : fromBottom[i+1][j] + enemy;
fromRight[i][j] = (j == colNum - 1) ? enemy : fromRight[i][j+1] + enemy;
}
else {
fromBottom[i][j] = 0;
fromRight[i][j] = 0;
}
}
}

int[] fromTop = new int[colNum];
int[] fromLeft = new int[rowNum];
int max = 0;

for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
if (grid[i][j] != '0') {
fromTop[j] = grid[i][j] == 'W' ? 0 : fromTop[j] + 1;
fromLeft[i] = grid[i][j] == 'W' ? 0 : fromLeft[i] + 1;
}
else {
int num = fromTop[j] + fromLeft[i] + fromBottom[i][j] + fromRight[i][j];
max = Math.max(num, max);
}
}
}
return max;
}``````
http://www.cnblogs.com/grandyang/p/5599289.html

```    int maxKilledEnemies(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<int>> v1(m, vector<int>(n, 0)), v2 = v1, v3 = v1, v4 = v1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int t = (j == 0 || grid[i][j] == 'W') ? 0 : v1[i][j - 1];
v1[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
for (int j = n - 1; j >= 0; --j) {
int t = (j == n - 1 || grid[i][j] == 'W') ? 0 : v2[i][j + 1];
v2[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
}
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m; ++i) {
int t = (i == 0 || grid[i][j] == 'W') ? 0 : v3[i - 1][j];
v3[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
for (int i = m - 1; i >= 0; --i) {
int t = (i == m - 1 || grid[i][j] == 'W') ? 0 : v4[i + 1][j];
v4[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') {
res = max(res, v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]);
}
}
}
return res;
}```

https://discuss.leetcode.com/topic/52170/share-my-java-codes
X. https://leetcode.com/discuss/109116/short-o-mn-solution

https://discuss.leetcode.com/topic/48565/short-o-mn-solution
``````int maxKilledEnemies(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
int result = 0, rowhits, colhits[n];
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (!j || grid[i][j-1] == 'W') {
rowhits = 0;
for (int k=j; k<n && grid[i][k] != 'W'; k++)
rowhits += grid[i][k] == 'E';
}
if (!i || grid[i-1][j] == 'W') {
colhits[j] = 0;
for (int k=i; k<m && grid[k][j] != 'W'; k++)
colhits[j] += grid[k][j] == 'E';
}
if (grid[i][j] == '0')
result = max(result, rowhits + colhits[j]);
}
}
return result;
}``````
https://discuss.leetcode.com/topic/48577/short-java-accepted-solution-55ms
``````public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int ret = 0;
int row = grid.length;
int col = grid[0].length;
int rowCache = 0;
int[] colCache = new int[col];
for (int i = 0;i < row; i++) {
for (int j = 0; j < col; j++) {
if (j == 0 || grid[i][j-1] == 'W') {
rowCache = 0;
for (int k = j; k < col && grid[i][k] != 'W'; k++) {
rowCache += grid[i][k] == 'E' ? 1 : 0;
}
}
if (i == 0 || grid[i-1][j] == 'W') {
colCache[j] = 0;
for (int k = i;k < row && grid[k][j] != 'W'; k++) {
colCache[j] += grid[k][j] == 'E' ? 1 :0;
}
}
if (grid[i][j] == '0') {
ret = Math.max(ret, rowCache + colCache[j]);
}
}
}
return ret;
}``````

http://dartmooryao.blogspot.com/2016/06/leetcode-361-bomb-enemy.html
My idea is to create a 2D matrix, and go from Left, Right, Top, and Down to calculate the count. Then add the count into the 2D matrix.

This solution is better because the code looks much shorter.

Idea:
(1) Use a 1D array to store the current count of the previous cols, and another int variable to store the count from the left.
(2) Use two for loops to visit all elements in the matrix.
(3) When the left of current position is a wall, we reset the rowHit variable to 0. Then we use a for loop that start from current position to the right, adding the count of E to the rowHit. Until we hit a wall.
(4) When the top col is a wall, we reset the colHit to be zero. Then use the same way to calculate the colHit to the end of col.
(5) If the current position is a '0', we compare the rowHit+colHit with the max result.
public int maxKilledEnemies(char[][] grid) {
if(grid.length==0){ return 0; }
int rowNo = grid.length, colNo = grid[0].length;
int[] colHit = new int[colNo];
int rowHit = 0;
int result = 0;

for(int i=0; i<rowNo; i++){
for(int j=0; j<colNo; j++){
if(j==0 || grid[i][j-1]=='W'){
rowHit = 0;
for(int k=j; k<colNo && grid[i][k] != 'W'; k++){
if(grid[i][k]=='E'){ rowHit++; }
}
}

if(i==0 || grid[i-1][j]=='W'){
colHit[j] = 0;
for(int k=i; k<rowNo && grid[k][j] != 'W'; k++){
if(grid[k][j]=='E'){ colHit[j]++; }
}
}

if(grid[i][j]=='0'){
result = Math.max(result, rowHit+colHit[j]);
}
}
}

return result;
}

Walk through the matrix. At the start of each non-wall-streak (row-wise or column-wise), count the number of hits in that streak and remember it. O(mn) time, O(n) space.
``````int maxKilledEnemies(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
int result = 0, rowhits, colhits[n];
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (!j || grid[i][j-1] == 'W') {
rowhits = 0;
for (int k=j; k<n && grid[i][k] != 'W'; k++)
rowhits += grid[i][k] == 'E';
}
if (!i || grid[i-1][j] == 'W') {
colhits[j] = 0;
for (int k=i; k<m && grid[k][j] != 'W'; k++)
colhits[j] += grid[k][j] == 'E';
}
if (grid[i][j] == '0')
result = max(result, rowhits + colhits[j]);
}
}
return result;
}``````
https://leetcode.com/discuss/109134/short-java-accepted-solution-55ms
public int maxKilledEnemies(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int ret = 0; int row = grid.length; int col = grid[0].length; int rowCache = 0; int[] colCache = new int[col]; for (int i = 0;i < row; i++) { for (int j = 0; j < col; j++) { if (j == 0 || grid[i][j-1] == 'W') { rowCache = 0; for (int k = j; k < col && grid[i][k] != 'W'; k++) { rowCache += grid[i][k] == 'E' ? 1 : 0; } } if (i == 0 || grid[i-1][j] == 'W') { colCache[j] = 0; for (int k = i;k < row && grid[k][j] != 'W'; k++) { colCache[j] += grid[k][j] == 'E' ? 1 :0; } } if (grid[i][j] == '0') { ret = Math.max(ret, rowCache + colCache[j]); } } } return ret; }
X. Brute Force
https://discuss.leetcode.com/topic/51035/super-straightforward-java-solution/
Isn't this a Brute force way with Time complexity O(m^2 + n^2) ?
https://leetcode.com/discuss/109110/simple-java-solution-easy-to-understand
public int maxKilledEnemies(char[][] grid) { if (grid == null || grid.length == 0) return 0; int ret=0; for (int i=0; i<grid.length; i++) { for (int j=0; j<grid[0].length; j++) { if (grid[i][j] != '0') continue; ret = Math.max(ret, countKilled(i, j, grid)); } } return ret; } int countKilled(int row, int col, char[][] grid) { int ret=0; for (int i=row; i<grid.length && grid[i][col] != 'Y'; i++) { if (grid[i][col] == 'X') ret++; } for (int i=row; i>=0 && grid[i][col] != 'Y'; i--) { if (grid[i][col] == 'X') ret++; } for (int i=col; i<grid[0].length && grid[row][i] != 'Y'; i++) { if (grid[row][i] == 'X') ret++; } for (int i=col; i>=0 && grid[row][i] != 'Y'; i--) { if (grid[row][i] == 'X') ret++; } return ret; }

https://discuss.leetcode.com/topic/50374/java-dp-solultion-o-mn-time-o-mn-space-beats-90
Using only `O(mn)` memory for additional grid (not as perfect as (`O(m)` space solutions given by other users but anyway..) we can solve this problem through `O(4mn)` iterations. We just need to scan the grid from left to right and accumulate the sum of enemies by `dp[i][j]` from left since the last wall. Then we do the same from top to bottom, from right to left and finally from bottom to top. On each iteration we increase the `dp[i][j]` value by cumulative sum.
``````  public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];

// from left to right
for (int i = 0; i < m; i++) {
int current = 0;
for (int j = 0; j < n; j++)
current = process(grid, dp, i, current, j);
}
// from top to bottom
for (int j = 0; j < n; j++) {
int current = 0;
for (int i = 0; i < m; i++)
current = process(grid, dp, i, current, j);
}
// from right to left
for (int i = 0; i < m; i++) {
int current = 0;
for (int j = n - 1; j >= 0; j--)
current = process(grid, dp, i, current, j);
}
int ans = 0;
// from bottom to top
for (int j = 0; j < n; j++) {
int current = 0;
for (int i = m - 1; i >= 0; i--) {
current = process(grid, dp, i, current, j);
if (grid[i][j] == '0')  ans = Math.max(ans, dp[i][j]);
}
}

return ans;
}

private int process(char[][] c, int[][] dp, int i, int current, int j) {
if (c[i][j] == 'W') current = 0;
if (c[i][j] == 'E') current++;
dp[i][j] += current;
return current;
}``````

https://all4win78.wordpress.com/2016/07/24/leetcode-361-bomb-enemy/

`    ``public` `int` `maxKilledEnemies(``char``[][] grid) {`
`        ``if` `(grid == ``null` `|| grid.length == ``0``) {`
`            ``return` `0``;`
`        ``}`
`        `
`        ``int``[][] enemyCount = ``new` `int``[grid.length][``2``];`
`        ``for` `(``int` `i = ``0``; i < enemyCount.length; i++) {`
`            ``enemyCount[i][``0``] = -``1``;`
`        ``}`
`        `
`        ``int` `max = ``0``;`
`        ``for` `(``int` `j = ``0``; j < grid[``0``].length; j++) {`
`            ``int` `colEnemy = countColEnemy(grid, j, ``0``);`
`            ``for` `(``int` `i = ``0``; i < grid.length; i++) {`
`                ``if` `(grid[i][j] == ``'0'``) {`
`                    ``if` `(j > enemyCount[i][``0``]) {`
`                        ``update(enemyCount, grid, i, j);`
`                    ``}`
`                    ``max = Math.max(colEnemy + enemyCount[i][``1``], max);`
`                ``}`
`                ``if` `(grid[i][j] == ``'W'``) {`
`                    ``colEnemy = countColEnemy(grid, j, i + ``1``);`
`                ``}`
`            ``}`
`        ``}`
`        ``return` `max;`
`    ``}`
`    `
`    ``private` `void` `update(``int``[][] enemyCount, ``char``[][] grid, ``int` `i, ``int` `j) {`
`        ``int` `count = ``0``;`
`        ``int` `k = enemyCount[i][``0``] + ``1``;`
`        ``while` `(k < grid[``0``].length && (grid[i][k] != ``'W'` `|| k < j)) {`
`            ``if` `(grid[i][k] == ``'E'``) {`
`                ``count += ``1``;`
`            ``}`
`            ``if` `(grid[i][k] == ``'W'``) {`
`                ``count = ``0``;`
`            ``}`
`            ``k += ``1``;`
`        ``}`
`        ``enemyCount[i][``0``] = k;`
`        ``enemyCount[i][``1``] = count;`
`    ``}`
`    `
`    ``private` `int` `countColEnemy(``char``[][] grid, ``int` `j, ``int` `start) {`
`        ``int` `count = ``0``;`
`        ``int` `i = start;`
`        ``while` `(i < grid.length && grid[i][j] != ``'W'``) {`
`            ``if` `(grid[i][j] == ``'E'``) {`
`                ``count += ``1``;`
`            ``}`
`            ``i += ``1``;`
`        ``}`
`        ``return` `count;`
`    ``}`

X.
https://fishercoder.com/2016/07/12/bomb-enemy/
https://discuss.leetcode.com/topic/53511/straightforward-java-solution-with-space-complex-o-1
https://discuss.leetcode.com/topic/51035/super-straightforward-java-solution
``````public int maxKilledEnemies(char[][] grid) {
int m = grid.length;
if(grid == null || m == 0) return 0;
int n = grid[0].length;

int[][] max = new int[m][n];

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){

if(grid[i][j] == '0'){
int count = 0;

//count all possible hits in its upward direction
for(int k = j-1; k >= 0; k--){
if(grid[i][k] == 'E') {
count++;
} else if(grid[i][k] == 'W') {
break;
}
}

//count all possible hits in its downward direction
for(int k = j+1; k < n; k++){
if(grid[i][k] == 'E') {
count++;
} else if(grid[i][k] == 'W') {
break;
}
}

//count all possible hits in its right direction
for(int k = i+1; k < m; k++){
if(grid[k][j] == 'E') {
count++;
} else if(grid[k][j] == 'W') {
break;
}
}

//count all possible hits in its left direction
for(int k = i-1; k >= 0; k--){
if(grid[k][j] == 'E') {
count++;
} else if(grid[k][j] == 'W') {
break;
}
}

max[i][j] = count;

}
}
}

int result = 0;

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(max[i][j] > result) result = max[i][j];
}
}
return result;
}``````
follow up是如果这个地图很大，很多点都是空的没东西，你怎么优化你的算法。楼主想了下稀疏矩阵乘法那道题就说用一个二维矩阵矩阵来记录每一行中，各个位置中不为0的列数和其对应的值，然后遍历这个新矩阵

## Labels

GeeksforGeeks (1107) LeetCode (993) Algorithm (795) Review (766) to-do (633) LeetCode - Review (514) Classic Algorithm (324) Dynamic Programming (293) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Different Solutions (120) Bit Algorithms (118) Lintcode (113) Smart Algorithm (109) Math (107) HackerRank (89) Binary Tree (82) Binary Search (81) Graph Algorithm (74) Greedy Algorithm (72) DFS (67) Interview Corner (61) Stack (60) List (58) BFS (54) Codility (54) ComProGuide (52) USACO (46) Trie (45) ACM-ICPC (41) Interval (41) Data Structure (40) Knapsack (40) Jobdu (39) LeetCode Hard (39) Matrix (38) String Algorithm (38) Backtracking (36) Codeforces (36) Must Known (36) Sort (35) Union-Find (34) Array (33) prismoskills (33) Segment Tree (32) Sliding Window (32) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Palindrome (28) to-do-must (28) Priority Queue (27) Random (27) Graph (26) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) DFS + Review (21) Brain Teaser (20) CareerCup (20) Merge Sort (20) O(N) (20) Follow Up (19) Time Complexity (19) Two Pointers (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) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) KMP (13) Majority (13) mitbbs (13) Combination (12) Modify Tree (12) Reconstruct Tree (12) Reverse Thinking (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Miscs (11) Princeton (11) Proof (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) DFS+Cache (10) HackerRank Easy (10) O(1) Space (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stock (9) TreeMap (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DFS+BFS (8) Linked List (8) Prime (8) Suffix Tree (8) Tech-Queries (8) 穷竭搜索 (8) Expression (7) Game Nim (7) Graph BFS (7) Hackerearth (7) Inversion (7) Quick Select (7) Radix Sort (7) n00tc0d3r (7) 蓝桥杯 (7) DFS+DP (6) DP - Tree (6) Dijkstra (6) Dutch Flag (6) How To (6) Manacher (6) One Pass (6) Pruning (6) Rabin-Karp (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) TreeSet (6) Xpost (6) reddit (6) AI (5) Big Data (5) Brute Force (5) Code Kata (5) Coding (5) Convex Hull (5) Crazyforcode (5) Cycle (5) Find Rule (5) Graph Cycle (5) Immutability (5) Java (5) Maze (5) Pre-Sum (5) Quadtrees (5) Quora (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) Chess Game (4) Distributed (4) Flood fill (4) Histogram (4) MST (4) MinMax (4) N Queens (4) Probability (4) Programcreek (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) B Tree (3) Coins (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Github (3) GoLang (3) Joseph (3) Jump Game (3) K (3) LogN (3) Minesweeper (3) NP Hard (3) O(N) Hard (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Subtree (3) Trie + DFS (3) Word Ladder (3) bookkeeping (3) codebytes (3) Array Merge (2) BOJ (2) Bellman Ford (2) Bit Counting (2) Bit Mask (2) Bloom Filter (2) Clock (2) Codesays (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-i-k-j (2) DP-树形 (2) Factor (2) GoHired (2) Graham Scan (2) Huffman Tree (2) Invariant (2) Islands (2) Lucene-Solr (2) Matrix Power (2) Median (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Robot (2) Rosettacode (2) Search (2) SimHash (2) Skyline (2) Summary (2) TV (2) Tile (2) Tree Sum (2) Word Break (2) Word Graph (2) Word Trie (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Big Integer (1) Big Number (1) Binary (1) Bipartite (1) BitMap (1) BitMap index (1) BitSet (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Chinese (1) Cloest (1) Clone (1) Code Quality (1) Company-Epic (1) Company-Yelp (1) Concurrency (1) Custom Sort (1) DFS-Matrix (1) DP-Difficult (1) DP-Graph (1) DP-MaxMin (1) Database (1) Diagonal (1) Domino (1) Dr Dobb's (1) Duplicate (1) FST (1) Fraction (1) Funny (1) Game (1) Generation (1) GeoHash (1) Google APAC (1) Gray Code (1) HOJ (1) Hanoi (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Interview (1) Isomorphic (1) JDK8 (1) Knight (1) Kruskal (1) Kth Element (1) Linkedin (1) Local MinMax (1) Matrix BFS (1) Matrix Graph (1) Matrix+DP (1) MinHash (1) MinMax Heap (1) Monto Carlo (1) Multiple DFS (1) Next Element (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Persistent (1) Power Set (1) PreProcess (1) Python (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Region (1) Resources (1) Robin (1) Selection (1) Similarity (1) Square (1) String DP (1) SubMatrix (1) Subsequence (1) TSP (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tree Rotate (1) Trie vs Hash (1) Triplet (1) Two Stacks (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) codevs (1) cos126 (1) javabeat (1) jum (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)