Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
1 -> A
2 -> B
3 -> C
…
26 -> Z
27 -> AA
28 -> AB

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

Implement Stack using Queues

Implement the following operations of a stack using queues.
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
empty() — Return whether the stack is empty.
Notes:
You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

Largest Rectangle in Histogram

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

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

The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = “aab”,
Return

1
2
3
4

[
  ["aa","b"],
  ["a","a","b"]
]

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

1
2
3
4
5
6
7

     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ’s undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

1
2
3
4
5
6

   1
  / \
 /   \
0 --- 2
     / \
     \_/

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:

1
2
3
4
5
6
7
8

Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Update—Leetcode now includes this problem:

Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:

1
2
3
4
5

11110
11010
11000
00000
Answer: 1

Example 2:

1
2
3
4
5

11000
11000
00100
00011
Answer: 3

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int numIslands(char[][] grid) {
    if(grid.length==0 || grid==null) return 0;
    int count=0;
    for(int i=0; i<grid.length; i++){
        for(int j=0;j<grid[0].length;j++){
            if(grid[i][j]=='1'){
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}
private void dfs(char[][] grid, int i, int j){
    if(i<grid.length && i>=0 & j<grid[0].length && j>=0 && grid[i][j]=='1'){
        grid[i][j]='0';
        dfs(grid, i-1,j);
        dfs(grid, i+1,j);
        dfs(grid, i,j-1);
        dfs(grid, i,j+1);
    }
    return;
}

CountIslands/Floodfill

给定matrix，只有0和1，求1的连通size，连通只算上下左右，不算对角线

1
2
3
4

0 1 0 0 1 
1 1 1 0 0
1 0 0 0 1
0 0 0 0 1

Return 5， 1， 2

Solution

For each 1 in the matrix, recursivly search for the four neighbors, terminate if 0/boundary found.

• Mark each node visited to avoid duplicated counting.

public ArrayList<Integer> countIslands(int[][] mat){
    int one,count;
    ArrayList<Integer> res = new ArrayList<Integer>();
    int[][] mark = new int[mat.length][mat[0].length];

    if(mat == null || mat.length == 0) return res;

    for (int i=0; i<mat.length; i++){
        for (int j=0; j<mat[0].length; j++){

            if(mark[i][j]!=1 && mat[i][j]==1){
                res.add(dfs(i,j, mat, mark));
            }
        }
    }
    return res;
}

public int dfs(int i, int j, int[][] mat, int[][] mark){
    if(i<0 || j<0 || i>mat.length-1 || j>mat[0].length-1 || mat[i][j]==0 || mark[i][j]==1)
        return 0;
    mark[i][j] = 1;
    return 1+dfs(i-1,j,mat,mark)+dfs(i+1,j,mat,mark)+dfs(i,j-1,mat,mark)+dfs(i,j+1,mat,mark);
}

public static void main(String[] args) {
    int[][] test = {{0, 1, 0, 0, 1} ,{1, 1, 1, 0, 0}, {1, 0, 0, 0, 1}, {0, 0, 0, 0, 1}};
    countIslands c = new countIslands();
    System.out.println(c.countIslands(test));
}

Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can 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.
For example,
Given board =

1
2
3
4
5
6
7
8

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static  boolean exist(char[][] board, String word) {
		for(int i=0; i<board.length;i++){
			for(int j=0;j<board[0].length;j++){
				if(dfs(board, word, i,j)){
					return true;
				}
			}
		}
		return false;
	}
	private static boolean dfs(char[][] a, String word, int i, int j){
		if(word.equals("")) return true;
		if(i<0 || j<0 ||j>=a[0].length || i>=a.length ) return false;
		if(a[i][j]==word.charAt(0)){
			char tmp=a[i][j];
			a[i][j]='#';
			boolean res = (dfs(a, word.substring(1), i+1, j) || dfs(a, word.substring(1), i, j+1) || dfs(a, word.substring(1), i-1, j) || dfs(a, word.substring(1), i, j-1));
			if(res) return true;
			else a[i][j]=tmp;
		}
		return false;
	}

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.
For example,
Given words = [“oath”,”pea”,”eat”,”rain”] and board =

1
2
3
4
5
6
7
8
9

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
Return ["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase letters a-z.

DFS Solution

• LTE…

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

public List<String> findWords(char[][] board, String[] words) {
    List<String> res= new ArrayList<String>();
   	for(String s : words){
   		if(exist(board, s)){
   			res.add(s);
   		}
   	}
   	return res;
   }
   
   public static boolean exist(char[][] board, String word) {
       boolean[][] visited= new boolean[board.length][board[0].length];
	for(int i=0; i<board.length;i++){
		for(int j=0;j<board[0].length;j++){
		    if(board[i][j]==word.charAt(0)){
   				if(dfs(board, word, i,j, visited)){
   					return true;
   				}
		    }
		}
	}
	return false;
}
private static boolean dfs(char[][] a, String word, int i, int j, boolean[][] visited){
	if(word.equals("")) return true;
	if(i<0 || j<0 ||j>=a[0].length || i>=a.length ) return false;
	if(a[i][j]==word.charAt(0) && !visited[i][j]){
		visited[i][j]=true;
		boolean res = (dfs(a, word.substring(1), i+1, j, visited) || dfs(a, word.substring(1), i, j+1, visited) || dfs(a, word.substring(1), i-1, j, visited) || dfs(a, word.substring(1), i, j-1, visited));
		if(res) return true;
		else visited[i][j]=false;
	}
	return false;
}

Trie Solution

• Trie helps with worst case ([“aaaaaa…aaas”, “aaaaaaa..aaaay”…])

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

public class Solution {
    public class TrieNode{
        public boolean isWord = false;
        public TrieNode[] child = new TrieNode[26];
        public TrieNode(){
        }
    }
    TrieNode root = new TrieNode();
    boolean[][] flag;
    public List<String> findWords(char[][] board, String[] words) {
        Set<String> result = new HashSet<>();
        flag = new boolean[board.length][board[0].length];
        addToTrie(words);
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(root.child[board[i][j] - 'a'] != null){
                    search(board, i, j, root, "", result);
                }
            }
        }
        return new LinkedList<>(result);
    }
    private void addToTrie(String[] words){
        for(String word: words){
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++){
                char ch = word.charAt(i);
                if(node.child[ch - 'a'] == null){
                    node.child[ch - 'a'] = new TrieNode();
                }
                node = node.child[ch - 'a'];
            }
            node.isWord = true;
        }
    }
    private void search(char[][] board, int i, int j, TrieNode node, String word, Set<String> result){
        if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || flag[i][j]){
            return;
        }
        if(node.child[board[i][j] - 'a'] == null){
            return;
        }
        flag[i][j] = true;
        node = node.child[board[i][j] - 'a'];
        if(node.isWord){
            result.add(word + board[i][j]);
        }
        search(board, i-1, j, node, word + board[i][j], result);
        search(board, i+1, j, node, word + board[i][j], result);
        search(board, i, j-1, node, word + board[i][j], result);
        search(board, i, j+1, node, word + board[i][j], result);
        flag[i][j] = false;
    }
}

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution

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
45
46
47
48
49
50
51
52

class TrieNode {
    // Initialize your data structure here.
    public boolean isword;
    public TrieNode[] children = new TrieNode[26];
    public TrieNode() {}
}
public class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode r=root;
        for(int i=0;i<word.length();i++){
            if(r.children[word.charAt(i)-'a']==null){
                r.children[word.charAt(i)-'a']=new TrieNode();
            }
            r=r.children[word.charAt(i)-'a'];
        }
        r.isword=true;
    }
    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode r=root;
        for(int i=0;i<word.length();i++){
            if(r.children[word.charAt(i)-'a']==null) return false;
            r=r.children[word.charAt(i)-'a'];
        }
        return r.isword;
    }
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode r=root;
        for(int i=0;i<prefix.length();i++){
            if(r.children[prefix.charAt(i)-'a']==null) return false;
            r=r.children[prefix.charAt(i)-'a'];
        }
        return true;
    }
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");