本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
130. 被围绕的区域
本题来自LeetCode：130. 被围绕的区域[1]
题目描述
给定一个二维的矩阵，包含
'X' 和
'O'（字母
O）。
找到所有被
'X'围绕的区域，并将这些区域里所有的
'O'用
'X'填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
解释: 被围绕的区间不会存在于边界上，换句话说，任何边界上的
'O'都不会被填充为
'X'。任何不在边界上，或不与边界上的
'O'相连的
'O'最终都会被填充为
'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
题目分析
题目解答
class Solution {
public void solve(char[][] board) {
if(board == null || board.length = 2 || board[0].length = 2) {
return;
}
int m = board.length;
int n = board[0].length;
// 将和第一列和最后一列相邻的'O'，全部标记为'-'
for(int i = 0; i m; i ++) {
dfs(board, m, n, i, 0);
dfs(board, m, n, i, n - 1);
}
// 将和第一行和最后一行相邻的'O'，全部标记为'-'
for(int i = 0; i n; i ++) {
dfs(board, m, n, 0, i);
dfs(board, m, n, m - 1, i);
}
//
for(int i = 0; i m; i ++) {
for(int j = 0; j n; j ++) {
if(board[i][j] == '-') {
// 将标记为'-'恢复为'O'
board[i][j] = 'O';
} else if(board[i][j] == 'O') {
// 将'O'填充为'X'，因为它们被'X'围绕了
board[i][j] = 'X';
}
}
}
}
public void dfs(char[][] board, int m, int n, int i, int j) {
if(board[i][j] == 'X' || board[i][j] == '-') {
return;
}
if(board[i][j] == 'O') {
board[i][j] = '-';
}
// 向上搜索相邻的'O'
if(i 0) {
dfs(board, m, n, i - 1, j);
}
// 向下搜索相邻的'O'
if(i m - 1) {
dfs(board, m, n, i + 1, j);
}
// 向左搜索相邻的'O'
if(j 0) {
dfs(board, m, n, i, j - 1);
}
// 向右搜索相邻的'O'
if(j n - 1) {
dfs(board, m, n, i, j + 1);
}
}
}
复杂度分析：
时间复杂度：
O(m*n)
空间复杂度：
O(m * n)，调用栈的最大深度为
m*n
289. 生命游戏
本题来自LeetCode：289. 生命游戏[2]
题目描述
根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live（1）即为活细胞， 或 dead（0）即为死细胞。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
示例:
输入:
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出:
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
进阶:
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？
题目分析
不使用额外空间，本题可以分成两步进行。
题目解答
class Solution {
public static final int DEAD = 0;
public static final int LIVE = 1;
public static final int WILL_DEAD = 2;
public static final int WILL_LIVE = 3;
public void gameOfLife(int[][] board) {
if(board.length == 0 || board[0].length == 0) {
return;
}
int m = board.length;
int n = board[0].length;
for(int i = 0; i m; i ++) {
for(int j = 0; j n; j ++) {
int lives = countLive(board, i, j, m, n);
if(board[i][j] == LIVE) {
// 满足条件1和条件3，标记为待死亡
if(lives 2 || lives 3) {
board[i][j] = WILL_DEAD;
}
} else {
// 满足条件4，标记为待复活
if(lives == 3) {
board[i][j] = WILL_LIVE;
}
}
}
}
// 计算细胞的下一个（一次更新后的）状态。
for(int i = 0; i m; i ++) {
for(int j = 0; j n; j ++) {
// 待复活 - 活细胞
if(board[i][j] == WILL_LIVE) {
board[i][j] = LIVE;
} else if(board[i][j] == WILL_DEAD) {
// 待死亡 - 死细胞
board[i][j] = DEAD;
}
}
}
}
// 计算相邻8个位置活细胞的个数
public int countLive(int[][] board, int i, int j, int m, int n) {
int top = i == 0 ? 0 : i - 1;
int bottom = i == m - 1 ? m - 1 : i + 1;
int left = j == 0 ? 0 : j - 1;
int right = j == n - 1 ? n - 1 : j + 1;
int lives = 0;
for(int i1 = top; i1 = bottom; i1 ++) {
for(int j1 = left; j1 = right; j1++) {
// 排除自身
if(i1 == i && j1 == j) {
continue;
}
if(board[i1][j1] == LIVE || board[i1][j1] == WILL_DEAD) {
lives ++;
}
}
}
return lives;
}
}
复杂度分析：
时间复杂度：
O(n^2)
空间复杂度：
O(1)
73. 矩阵置零
本题来自LeetCode：73. 矩阵置零[3]
题目描述
给定一个
m x n的矩阵，如果一个元素为
0，则将其所在行和列的所有元素都设为
0。请使用原地算法。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
题目分析
和题
289. 生命游戏一样，本题不使用额外空间，分成两步进行。
题目解答
class Solution {
private static final int SET_ZERO_FLAG = Integer.MAX_VALUE - 1;
public void setZeroes(int[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0) {
return;
}
int m = matrix.length;
int n = matrix[0].length;
// 1. 标记
for(int i = 0; i m; i ++) {
for(int j = 0; j n; j ++) {
if(matrix[i][j] == 0) {
mark(matrix, i, j);
}
}
}
// 2. 赋值
for(int i = 0; i m; i ++) {
for(int j = 0; j n; j ++) {
if(matrix[i][j] == SET_ZERO_FLAG) {
matrix[i][j] = 0;
}
}
}
}
// 将0所在行和列的所有元素都标记为待置零
public void mark(int[][] matrix, int row, int column) {
matrix[row][column] = SET_ZERO_FLAG;
for(int i = 0; i matrix[0].length; i ++) {
if(matrix[row][i] != 0) {
matrix[row][i] = SET_ZERO_FLAG;
}
}
for(int i = 0; i matrix.length; i ++) {
if(matrix[i][column] != 0) {
matrix[i][column] = SET_ZERO_FLAG;
}
}
}
}
复杂度分析：
时间复杂度：
O(n^2)
空间复杂度：
O(1)
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
