Lintcode: Kth Smallest Number in Sorted Matrix

最后一个testcase 过不了，memory limit exceeded

public class Solution {
    public int kthSmallest(final int[][] matrix, int k) {
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        PriorityQueue<int[]> heap = new PriorityQueue<int[]>(k, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]);
            }
        });
        heap.add(new int[]{0,0});
        visited[0][0] = true;
        while (k > 1) {
            int[] res = heap.remove();
            int x = res[0];
            int y = res[1];
            
            
            if (x+1 < matrix.length && visited[x+1][y] == false) {
                visited[x+1][y] = true;
                heap.add(new int[]{x+1, y});
            }
            if (y+1 < matrix[0].length && visited[x][y+1] == false) {
                visited[x][y+1] = true;
                heap.add(new int[]{x, y+1});
            }
            k--;
        }
        int[] res = heap.remove();
        return matrix[res[0]][res[1]];
    }
}

Lintcode: Longest Increasing Continuous subsequence II

非常好的DP + DFS题。值得多思考

public class Solution {
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        int res = 0;
        if (A == null || A.length == 0 || A[0].length == 0) {
        	return res;
        }
        int[][] store = new int[A.length][A[0].length];
        for (int i = 0; i < A.length; i++) {
        	for (int j = 0; j < A[0].length; j++) {
        		if (store[i][j] == 0) {
        			res = Math.max(res, dfs(A, store, i, j));
        		}
        	}
        }
        return res;
    }
    private int dfs(int[][] a, int[][] store, int i, int j) {
    	if (store[i][j] != 0) {
    		return store[i][j];
    	}
    	int left = 0, right = 0, up = 0, down = 0;
    	if (j + 1 < a[0].length && a[i][j+1] > a[i][j]) {
    		right = dfs(a, store, i, j+1);
    	}
    	if (j > 0 && a[i][j-1] > a[i][j]) {
    		left = dfs(a, store, i, j-1);
    	}
    	if (i + 1 < a.length && a[i+1][j] > a[i][j]) {
    		down = dfs(a, store, i+1, j);
    	}
    	if (i > 0 && a[i-1][j] > a[i][j]) {
    		up = dfs(a, store, i-1, j);
    	}
    	store[i][j] = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    	return store[i][j];
    }
}

Lintcode: Find Peak Element II

class Solution {
    public List<Integer> findPeakII(int[][] A) {
        List<Integer> res = new ArrayList<Integer>();
        if (A == null || A.length == 0 || A[0].length == 0) {
        	return res;
        }
        int i = 1, j = 1;
        while (true) {
    		if (isValid(A, i, j)) {
    			res.add(i);
    			res.add(j);
    			return res;
    		}
			if (A[i+1][j] > A[i][j+1]) {
				i++;
			} else {
				j++;
			}
        }
    }
    private boolean isValid(int[][] a, int i, int j) {
    	if (i > 0 && i < a.length - 1 && j > 0 && j < a[0].length - 1 
    		&& a[i-1][j] < a[i][j] && a[i+1][j] < a[i][j] && a[i][j+1] < a[i][j] && a[i][j+1] < a[i][j]) {
    		return true;
    	}
    	return false;
    }
}

Leetcode: Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

---

用Word Search I的解法会超市，因此得用trie来保存input的所有string，然后dfs遍历board来看当前的string是否存在于trie中。如果当前string不是trie中任意string的prefix，可以剪枝，不需要继续dfs下去。很好的题目，需要加强。

public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<String>();
        if (board == null || board.length == 0 || board[0].length == 0 || words == null || words.length == 0) {
            return res;
        }
        
        boolean[][] visited = new boolean[board.length][board[0].length];
        Set<String> noDuplicateInput = new HashSet<String>(Arrays.asList(words));
        Trie trie = new Trie(noDuplicateInput);
        for (int i = 0; i < board.length; i++) {
        	for (int j = 0; j < board[0].length; j++) {
        		search(board, i, j, "", visited, trie, res);
        	}
        }
        return res;
    }
    private void search(char[][] board, int i, int j,
			String str, boolean[][] visited, Trie trie, List<String> res) {
		if (i < board.length && i >= 0 && j < board[0].length && j >= 0 && visited[i][j] == false) {
			String newStr = str + board[i][j];
			TrieNode endNode = trie.startWith(newStr);
			if (endNode != null) {
				if (endNode.leaf == true) {
					res.add(newStr);
					endNode.leaf = false; //avoid duplicate in result
				}
				visited[i][j] = true;
				search(board, i+1, j, newStr, visited, trie, res);
				search(board, i-1, j, newStr, visited, trie, res);
				search(board, i, j+1, newStr, visited, trie, res);
				search(board, i, j-1, newStr, visited, trie, res);
				visited[i][j] = false;
			}
		}
	}
	class Trie {
    	TrieNode root;
    	public Trie(Set<String> strs) {
    		root = new TrieNode();
    		for (String str : strs) {
    			add(str);
    		}
    	}
    	//gets the last node in the tree that matches the str, return null if not match
    	public TrieNode startWith(String str) {
    		TrieNode res = null;
    		TrieNode curRoot = root;
    		for (int i = 0; i < str.length(); i++) {
    			if (curRoot.children != null && curRoot.children.get(str.charAt(i)) != null) {
    				if (i == str.length() - 1) {
    					res = curRoot.children.get(str.charAt(i));
    				}
    				curRoot = curRoot.children.get(str.charAt(i));
    			} else {
    				break;
    			}
    		}
    		return res;
		}
		public void add(String str) {
    		TrieNode curRoot = root;
    		for (int i = 0; i < str.length(); i++) {
    			if (curRoot.children == null) {
    				curRoot.children = new HashMap<Character, TrieNode>();
    			}
    			if (curRoot.children.get(str.charAt(i)) == null) {
    				curRoot.children.put(str.charAt(i), new TrieNode(str.charAt(i)));
    			}
    			if (i == str.length() - 1) {
    				curRoot.children.get(str.charAt(i)).leaf = true;
    			}
    			curRoot = curRoot.children.get(str.charAt(i));
    		}
    	}
    	public boolean contains(String str) {
    		TrieNode lastNode = startWith(str);
    		if (lastNode == null || lastNode.leaf == false) {
    			return false;
    		}
    		return true;
    	}
    }
    class TrieNode {
    	boolean leaf;
    	char ch;
    	Map<Character, TrieNode> children;
    	public TrieNode() { }
    	public TrieNode(char ch) {
    		this.ch = ch;
    	}
    }
}

Leetcode & Lintcode: N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

---

Solution 1: 这个解法直接对string［］进行判断以及操作，很费时。

public class Solution {
    public List<String[]> solveNQueens(int n) {
        List<String[]> result = new ArrayList<String[]>();
        String[] start = new String[n];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append('.');
        }
        for (int i = 0; i < n; i++) {
            start[i] = sb.toString();
        }
        sub(n, 0, start, result);
        return result;
    }
    private void sub(int n, int row, String[] strings, List<String[]> result) {
        if (row == n) {
        	String[] toAdd = new String[strings.length];
        	for (int i = 0; i < toAdd.length; i++) {
        		toAdd[i] = new String(strings[i]);
        	}
            result.add(toAdd);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (isValid(n, strings, row, j) == true) {
            	StringBuilder sb = new StringBuilder(strings[row]);
            	sb.setCharAt(j, 'Q');
            	strings[row] = sb.toString();
                sub(n, row+1, strings, result);
                sb.setCharAt(j, '.');
                strings[row] = sb.toString();
            }
        }
    }
    private boolean isValid(int n, String[] strings, int row, int col) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < n; j++) {
                if (strings[i].charAt(j) == 'Q' && (j == col || Math.abs(col - j) == Math.abs(row - i))) {
                    return false;
                }
            }
        }
        return true;
    }
}

Solution 2: 应该用一个int[] 表示每一行的queen在第几个元素即可。

private void solveRow(ArrayList<ArrayList> res, ArrayList curList, int[] pos, int row, int n) {
for (int i = 0; i < n; i++) {
if (isValid(pos, row, i)) {
pos[row] = i;
StringBuilder sb = new StringBuilder();
for (int x = 0; x < n; x++) {
if (x == i) {
sb.append('Q');
} else {
sb.append('.');
}
}
if (row == n-1) {
ArrayList newList = new ArrayList(curList);
newList.add(sb.toString());
res.add(newList);
} else {
int prevLen = res.size();
solveRow(res, curList, pos, row+1, n);
for (int newResStart = prevLen; newResStart < res.size(); newResStart++) {
res.get(newResStart).add(0, sb.toString());
}
}
pos[row] = -1;
}
}
}
private boolean isValid(int[] pos, int row, int i) {
for (int prevRow = 0; prevRow < row; prevRow++) {
if (pos[prevRow] == i || Math.abs(row – prevRow) == Math.abs(i – pos[prevRow])) {
return false;
}
}
return true;
}

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

---

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.' && isValid(board, i, j) == false) {
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == board[row][col] && i != row) {
                return false;
            }
        }
        for (int j = 0; j < board[0].length; j++) {
            if (board[row][j] == board[row][col] && j != col) {
                return false;
            }
        }
        for (int i = row/3 * 3; i < row/3 * 3 + 3; i++) {
            for (int j = col/3 * 3; j < col/3 * 3 + 3; j++) {
                if (board[i][j]==board[row][col] && !(i == row && j == col)) {
                    return false;
                }
            }
        }
        return true;
    }
}

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.
对于返回条件，还需要思考和练习。

public class Solution {
    public void solveSudoku(char[][] board) {
        solvable(board);
    }
    private boolean solvable(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    for (int tryNumber = 1; tryNumber <= 9; tryNumber++) {
                        if (isValid(board, i, j, tryNumber)) {
                            board[i][j] = (char)(tryNumber + '0');
                            if (solvable(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int row, int col, int tryNumber) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[row][j] - '0' == tryNumber) {
                return false;
            }
        }
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] - '0' == tryNumber) {
                return false;
            }
        }
        for (int i = row/3 * 3; i < (row/3 + 1) * 3; i++) {
            for (int j = col/3 * 3; j < (col/3 + 1)*3; j++) {
                if (board[i][j] - '0' == tryNumber) {
                    return false;
                }
            }
        }
        return true;
    }
}

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

---

public class Solution {
public void rotate(int[][] matrix) {
for (int level = 0; level < matrix.length/2; level++) {
for (int index = level; index < matrix.length – level – 1; index++) {
int tmp = matrix[matrix.length – 1 – index][level];
matrix[matrix.length-1-index][level] = matrix[matrix.length-level-1][matrix.length-1-index];
matrix[matrix.length-level-1][matrix.length-1-index] = matrix[index][matrix.length – level – 1];
matrix[index][matrix.length – level – 1] = matrix[level][index];
matrix[level][index] =tmp;
}
}
}
}

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

---

和Spiral MatrixII思路一样。

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<Integer>();
        if (matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
        int level = 0;
        for (; level < Math.min(matrix.length, matrix[0].length)/2; level++) {
            for (int j = level; j < matrix[0].length - level - 1; j++) {
                result.add(matrix[level][j]);
            }
            for (int i = level; i < matrix.length - level - 1; i++) {
                result.add(matrix[i][matrix[0].length - level - 1]);
            }
            for (int j = matrix[0].length - level - 1; j > level; j--) {
                result.add(matrix[matrix.length - level - 1][j]);
            }
            for (int i = matrix.length - level - 1; i > level ; i--) {
                result.add(matrix[i][level]);
            }
        }
        if (matrix.length <= matrix[0].length && matrix.length % 2 != 0) {
            for (int j = level; j < matrix[0].length - level; j++) {
                result.add(matrix[matrix.length/2][j]);
            }
        } else if (matrix[0].length % 2 != 0) {
            for (int i = level; i < matrix.length - level; i++) {
                result.add(matrix[i][matrix[0].length/2]);
            }
        }
        return result;
    }
}

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

---

对于matrix的螺旋处理，一般的套路就是一圈圈的处理外围的四条边。

public class Solution {
    public int[][] generateMatrix(int n) {
        int cur = 1;
        int[][] result = new int[n][n];
        for (int level = 0; level < n/2; level++) {
            for (int j = level; j < n - level - 1; j++) {
                result[level][j] = cur++;
            }
            for (int i = level; i < n - level - 1; i++) {
                result[i][n - level -1] = cur++;
            }
            for (int j = n - level - 1; j > level; j--) {
                result[n-level-1][j] = cur++;
            }
            for (int i = n - level - 1; i > level; i--) {
                result[i][level] = cur++;
            }
        }
        if (n % 2 != 0) {
            result[n/2][n/2] = cur;
        }
        return result;
    }
}