Matrix Inplace Operations
当我们需要in-place处理矩阵的时候，最简便直接的思路往往是“多个”pass的，即是用一次pass做标记，第二次甚至第三次pass再做实际处理。
Set Matrix Zeros
先扫描第一行和第一列，记录第一行/列是否为0；
在此之后，第一行与第一列起来标记作用，header；
扫描里面，在任何位置看到0，把对应的行/列header设为0；
再次扫描里面，如果行或者列的头为0，则设为0；
此时第一行和列已失去记录作用，开始根据最开始的记录来设0。
public class Solution {
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return;
}
int m = matrix.length, n = matrix[0].length;
boolean firstRowZero = false, firstColZero = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
for (int i = 0; i < n; i++) {
if (matrix[0][i] == 0) {
firstRowZero = true;
break;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (firstRowZero) {
for (int i = 0; i < n; i++) {
matrix[0][i] = 0;
}
}
if (firstColZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}
Game of Life
正确定义状态
- 0：未访问，当前死 / 已访问，下轮仍然死
- 1：未访问，活 / 已访问，下轮仍然活
- 2：已访问，当前活，下轮死
- 3：已访问，当前死，下轮活
public class Solution {
int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
public void gameOfLife(int[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return;
}
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int count = getLiveNeighbors(board, i, j);
if (board[i][j] == 1 && (count < 2 || count > 3)) {
board[i][j] = 2;
} else if (board[i][j] == 0 && count == 3) {
board[i][j] = 3;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = board[i][j] % 2;
}
}
}
private int getLiveNeighbors(int[][] board, int i, int j) {
int count = 0;
for (int k = 0; k < 8; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
if (board[x][y] == 1 || board[x][y] == 2) {
count++;
}
}
}
return count;
}
}
Rotate Image
先沿着水平的中轴线上下翻一次，然后沿着从左上到右下的对角线翻一次
public class Solution {
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return;
}
int m = matrix.length;
// flip the matrix horizontally
for (int i = 0; i < m / 2; i++) {
for (int j = 0; j < m; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[m - i - 1][j];
matrix[m - i - 1][j] = temp;
}
}
// flip the matrix by the diagonal line
for (int i = 0; i < m; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}
Spiral Matrix
维护四个边界，按顺序输出之后步步收缩。
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return result;
}
int m = matrix.length, n = matrix[0].length;
int total = m * n, count = 0;
int rowStart = 0, rowEnd = m - 1, colStart = 0, colEnd = n - 1;
while (count < total) {
if (rowStart <= rowEnd) {
for (int i = colStart; i <= colEnd && count < total; i++) {
result.add(matrix[rowStart][i]);
count++;
}
}
rowStart++;
if (colStart <= colEnd) {
for (int i = rowStart; i <= rowEnd && count < total; i++) {
result.add(matrix[i][colEnd]);
count++;
}
}
colEnd--;
if (rowStart <= rowEnd) {
for (int i = colEnd; i >= colStart && count < total; i--) {
result.add(matrix[rowEnd][i]);
count++;
}
}
rowEnd--;
if (colStart <= colEnd) {
for (int i = rowEnd; i >= rowStart && count < total; i--) {
result.add(matrix[i][colStart]);
count++;
}
}
colStart++;
}
return result;
}
}
Spiral Matrix II
一模一样的思路
public class Solution {
public int[][] generateMatrix(int n) {
int count = 0, total = n * n;
int[][] matrix = new int[n][n];
int rowStart = 0, rowEnd = n - 1, colStart = 0, colEnd = n - 1;
while (count < total) {
if (rowStart <= rowEnd) {
for (int i = colStart; i <= colEnd && count < total; i++) {
matrix[rowStart][i] = ++count;
}
}
rowStart++;
if (colStart <= colEnd) {
for (int i = rowStart; i <= rowEnd && count < total; i++) {
matrix[i][colEnd] = ++count;
}
}
colEnd--;
if (rowStart <= rowEnd) {
for (int i = colEnd; i >= colStart && count < total; i--) {
matrix[rowEnd][i] = ++count;
}
}
rowEnd--;
if (colStart <= colEnd) {
for (int i = rowEnd; i >= rowStart; i--) {
matrix[i][colStart] = ++count;
}
}
colStart++;
}
return matrix;
}
}