Let’s play the minesweeper game (Wikipedia, online game)!

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.
If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
Return the board when no more squares will be revealed.
Example 1:
Input:

1
2
3
4

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output:

1
2
3
4

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Example 2:
Input:

1
2
3
4

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output:

1
2
3
4

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Note:
The range of the input matrix’s height and width is [1,50].
The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
The input board won’t be a stage when game is over (some mines have been revealed).
For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

解法1：

题目看起来很复杂，其实实现起来比较简单。就一步步按照他的规则来就可以。主要是考察了DFS或者是BFS的应用。这里我用了DFS的解法，对于每一个click的方块。如果是地雷，那么直接return了。
如果不是地雷，那么统计一下周围地雷的个数。如果是空的，那么就对所有相邻的都做一遍DFS，如果是有地雷则直接范围地雷的个数。

Java

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

public class Solution {
    // defines the 8 directions it can point to
    private int[][] directions = {{0,1},{0,-1},{1,0},{-1,0},{-1,1},{1,1},{1,-1},{-1,-1}};
    public char[][] updateBoard(char[][] board, int[] click) {
        
        if (board.length == 0 || board[0].length == 0) {
            return board;
        }
        
        dfs(board, click[0], click[1]);
        
        return board;
        
    }
    
    private void dfs(char[][] board, int i, int j) {
        if (board[i][j] == 'M') {
            board[i][j] = 'X';
            return;
        }
        
        if (board[i][j] == 'E') {
            int n = getNumberOfMines(board, i, j);
            if (n == 0) {
                board[i][j] = 'B';
                // doing dfs for each direction
                for (int[] direction: directions) {
                    int x = i + direction[0];
                    int y = j + direction[1];
                    if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == 'M') {
                        continue;
                    }
                    dfs(board, x, y);
                }
            } else {
                board[i][j] = (char)(n + '0');
            }
        }
        return;
    }
    
    private int getNumberOfMines(char[][] board, int i, int j) {
        int n = board.length;
        int m = board[0].length;
        int count = 0;
        for (int[] direction: directions) {
            int x = i + direction[0];
            int y = j + direction[1];
            if (x < 0 || x >= n || y < 0 || y >= m) {
                continue;
            }
            if (board[x][y] == 'M') {
                ++count;
            }
        }
        return count;
    }
}

Given a picture consisting of black and white pixels, find the number of black lonely pixels.

The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.

A black lonely pixel is character ‘B’ that located at a specific position where the same row and same column don’t have any other black pixels.

Example:

1
2
3
4
5
6
7

Input: 
[['W', 'W', 'B'],
 ['W', 'B', 'W'],
 ['B', 'W', 'W']]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

Note:
The range of width and height of the input 2D array is [1,500].

解法1：O(MN) Time + O(M + N) Space

用两个数组分别记录每一行， 每一列的pixel的个数，然后遍历一遍矩阵，对于每一个B的位置查看当前行列的B的个数。
Java

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

public class Solution {
    public int findLonelyPixel(char[][] picture) {
        if (picture.length == 0 || picture[0].length == 0) {
            return 0;
        }
        
        int n = picture.length;
        int m = picture[0].length;
        int[] row = new int[n];
        int[] col = new int[m];
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B') {
                    row[i]++;
                    col[j]++;
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < n;++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B') {
                    if (row[i] == 1 && col[j] == 1) {
                        ++count;
                    }
                }
            }
        }
        
        return count;
        
    }
}

You need to find the largest value in each row of a binary tree.

Example:

1
2
3
4
5
6
7
8
9

Input: 
          1
         / \
        3   2
       / \   \  
      5   3   9 
Output: [1, 3, 9]

解法1：BFS

因为是按行来选择最大值，自然想到用BFS遍历每一行，然后存储下每一行的最大值。主要考察了BFS的写法。
Java

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> largestValues(TreeNode root) {
		// bfs
		List<Integer> result = new ArrayList<Integer>();
		if (root == null) {
			return result;
		}
		
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			int levelmax = Integer.MIN_VALUE;
			for (int i = 0; i < size; ++i) {
				TreeNode cur = queue.poll();
				levelmax = Math.max(levelmax, cur.val);
				if (cur.left != null) {
					queue.offer(cur.left);
				}
				if (cur.right != null) {
					queue.offer(cur.right);
				}
			}
			result.add(levelmax);
		}
		return result;
    }
}

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. 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:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid0 into a land.

1 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid2 into a land.

1 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

解法1：Union Find O(k logmn)

这是一题难题了，为了熟悉Union Find的算法也做（抄）一下吧。主要是参考了这篇.
Union Find很适合用来解决两点是否想通的问题。用一个roots来记录每一个点的group id也就是下面code中的parent。
然后对于每一个插入的点，首先把自己的点的group id设为自己，然后搜索周围相邻的点，如果相邻的点是陆地并且相邻的点的group id和自己不同的时候，则说明需要进行Union操作。
这个时候对于当前岛屿的数量需要-1，因为合并了一个。
Java

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

public class Solution {
    
	private int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
	public List<Integer> numIslands2(int m, int n, int[][] positions) {
		// Union Find
		List<Integer> result = new ArrayList<Integer>();
		if (m <= 0 || n <= 0 || positions.length == 0 || positions[0].length == 0) {
			return result;
		}
		
		int count = 0;
		int[] roots = new int[m * n];
		Arrays.fill(roots, -1);
		for (int[] position: positions) {
			// positions
			count++;
			int index = n * position[0] + position[1];
			roots[index] = index;
			// perform union operations
			for (int[] direction: directions) {
				int x = position[0] + direction[0];
				int y = position[1] + direction[1];
				int neighbor = x * n + y;
				if ( x < 0 || x >= m || y < 0 || y >= n || roots[neighbor] == -1) {
					continue;
				}
				int parent = find(roots, neighbor);
				if (parent != index) {
					roots[index] = parent;
					count--;
					index = parent;
				}
			}
			result.add(count);
		}
		
		return result;
    }
	private int find(int[] roots, int index) {
		while (roots[index] != index) {
			index = roots[index];
		}
		return index;
	}		
}

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

Example 1:

1
2

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:
You may use one character in the keyboard more than once.
You may assume the input string will only contain letters of alphabet.

解法1：

这题就是掌握一下语言中对于string查找相关的操作。
Java
Java中的string.toCharArray()，还有查找一个char是否在string里的操作string.indexOf(s) == -1

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

public class Solution {
    String[] keyboards = {"qwertyuiop","asdfghjkl","zxcvbnm"};
    public String[] findWords(String[] words) {
        
        List<String> res = new ArrayList<String>();
        for (String word: words) {
            for (String row: keyboards) {
                boolean temp = true;
                for (char s: word.toLowerCase().toCharArray()) {
                    if (row.indexOf(s) == -1) {
                        temp = false;
                        break;
                    }
                }
                if (temp) {
                    res.add(word);
                    break;
                }
            }
        }
        String[] r = new String[res.size()];
        res.toArray(r);
        return r;
        
    }
}

For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

1
2
3
4
5

1. The area of the rectangular web page you designed must equal to the given target area.
2. The width W should not be larger than the length L, which means L >= W.
3. The difference between length L and width W should be as small as possible.

You need to output the length L and the width W of the web page you designed in sequence.
Example:

1
2
3
4

Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1]. 
But according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.

Note:
The given area won’t exceed 10,000,000 and is a positive integer
The web page’s width and length you designed must be positive integers.

解法1：O(Sqrt(area))

按照提议，如果area是一个完全平方数的话正方形的边长就是最佳答案。那么可以从平方根出发，找出 1 <= x <= sqrt(area)当中最大的能被area整除的数就是所要求的。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Solution {
    public int[] constructRectangle(int area) {
        
        int temp = (int) Math.sqrt(area);
        
        while (area % temp != 0 ) {
            --temp;
        }
        
        int[] res = {area / temp, temp };
        return res;
        
    }
}

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like “USA”.
All letters in this word are not capitals, like “leetcode”.
Only the first letter in this word is capital if it has more than one letter, like “Google”.
Otherwise, we define that this word doesn’t use capitals in a right way.
Example 1:

1
2

Input: "USA"
Output: True

Example 2:

1
2

Input: "FlaG"
Output: False

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

解法1：Regex 表达式

感觉这个做法比较像作弊。。
Java

1
2
3
4
5

public class Solution {
    public boolean detectCapitalUse(String word) {
        return word.matches("[A-Z]+|[a-z]+|[A-Z][a-z]+");
    }
}

解法2: 常规解法

常规的想法，可以判断是否都是大写或者都是小写，或者第2个字母开始是否都是小写。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Solution {
    public boolean detectCapitalUse(String word) {
        if (word.equals(word.toUpperCase())) {
            return true;
        }
        
        if (word.equals(word.toLowerCase())) {
            return true;
        }
        
        if (word.substring(1).equals(word.substring(1).toLowerCase())) {
            return true;
        }
        
        return false;
    }
}

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

1
2
3
4

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note:

The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000

解法1：O(N),一次遍历

dp的思想，dp[i] = dp[i - 1] + 1 if dp[i] == 1 else dp[i] = 0, 然后用一个res来记录当前遇到的最大值即可。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int res = 0;
        
        for (int num: nums) {
            if (num == 1) {
                ++count;
                res = Math.max(res, count);
            } else {
                count = 0;
            }
        }
        return res;
    }
}

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

1
2
3
4
5
6

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

1
2
3
4
5

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:
All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.

解法1：Stack + HashMap: O(N) Time + O(N) Space

很好的一道题，主要的思路是在扫描的过程中得出每一个element对应的next greater element。 然后在hashmap中查找所需要的结果。
一次遍历找出next greater element的思路是[A,B] 如果B比A大那么B就是A对应的结果。如果B比A小的话要找出第一个比B大的数才是B的结果，而A要等到比A自己大的才可以。
那么试想，如果碰到一个递减数列[5,4,3,2,1]如果出现一个6，比前面所有的数都大，这个时候这个6就是所有数的NGE。所以有此我们可以用一个stack来维护递减的数列，只要下一个数比stack的top大，那么top值得NGE就是当前的值。
不停的弹出stack的值直到top的值比当前的值大为止。

Java

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

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        
        for (int num: nums) {
            while (!stack.isEmpty() && num > stack.peek()) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }
        
        // scan through findNums
        int[] res = new int[findNums.length];
        for (int i = 0; i < res.length; ++i) {
            res[i] = map.getOrDefault(findNums[i], -1);
        }
        
        return res;
        
    }
}

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:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

解法1：DFS

用DFS遍历每一个元素，如果是1就表示有一个岛屿，并且用DFS遍历所有与之相连的节点。并且把他们标注为非岛屿。
Java

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

public class Solution {
    public int numIslands(char[][] grid) {
   		    if (grid.length == 0 || grid[0].length == 0) {
				return 0;
			}
			int res = 0;
			for (int i = 0; i < grid.length; ++i) {
				for (int j = 0; j < grid[0].length; ++j) {
					if (grid[i][j] == '1') {
						++res;
						dfs(grid, i, j);
					}
				}
			}
			return res;
    }
	void dfs (char[][] grid, int i, int j) {
		if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
			return;
		}
		if (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;
	}		
}

解法2：BFS

Java

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

class pair {
	int x, y;
	public pair(int row, int col) {
		this.x = row;
		this.y = col;
	}
};
public class Solution {
    public int numIslands(char[][] grid) {
		if (grid.length == 0 || grid[0].length == 0) {
			return 0;
		}
		int res = 0;
		for (int i = 0; i < grid.length; ++i) {
			for (int j = 0; j < grid[0].length; ++j) {
				if (grid[i][j] == '1') {
					++res;
					bfs(grid, i, j);
				}
			}
		}    
		return res;
    }
    
    private int[][] directions = new int[][] {{0,1},{0,-1},{1,0},{-1,0}};
	private void bfs(char[][] grid, int i, int j) {
	    int row = grid.length;
	    int col = grid[0].length;
		Queue<pair> queue = new LinkedList<pair>();
		if (grid[i][j] == '1') {
			queue.offer(new pair(i, j));
			grid[i][j] = '0';
		}
		while (!queue.isEmpty()) {
			pair cur = queue.poll();
			for (int d = 0; d < directions.length; ++d) {
			    int x = cur.x + directions[d][0];
			    int y = cur.y + directions[d][1];
			    if (!isInbound(row, col, x, y)) {
			       continue;
			    }
			    if (grid[x][y] == '1') {
			        queue.offer(new pair(x,y));
			        grid[x][y] = '0';
			    }
			}
		}		
		return;
	}
	
	private boolean isInbound(int row, int col, int i, int j) {
	   return i >= 0 && i < row && j >= 0 && j < col;
	}
}