Matrix Inplace Operations

当我们需要 in-place 处理矩阵的时候，最简便直接的思路往往是“多个 pass”的，即用一次 pass 做标记，第二次甚至第三次 pass 再做实际处理。

Set Matrix Zeroes

直接 in-place 的尝试一开始错了，试图每次看到一个 0 ，都把矩阵分为其左下和右下的子矩阵，递归处理，但是没有充分考虑到同一行上可能有其他 col 上的 0，会把这个 col 对应的下面位置也设成 0 的情况，因此是错误的。

• 先扫描第一行和第一列，记录第一行/列是否为 0；

• 在此之后，第一行与第一列起到标记作用，header.

• 扫描里面，在任何位置看到 0 ，都把对应的 行/列 头设为 0

• 再次扫描里面，如果行或列的头位置为 0 ，则设为 0；

• 此时第一行和列已经失去作为记录的作用，开始根据最开始的记录来设 0.

public class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return;

        int rows = matrix.length;
        int cols = matrix[0].length;

        boolean firstRowZero = false;
        boolean firstColZero = false;

        for(int i = 0; i < rows; i++) if(matrix[i][0] == 0) firstColZero = true;
        for(int i = 0; i < cols; i++) if(matrix[0][i] == 0) firstRowZero = true;

        for(int i = 1; i < rows; i++){
            for(int j = 1; j < cols; j++){
                if(matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
            }
        }

        for(int i = 1; i < rows; i++){
            for(int j = 1; j < cols; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }

        if(firstRowZero) for(int i = 0; i < cols; i++) matrix[0][i] = 0;
        if(firstColZero) for(int i = 0; i < rows; i++) matrix[i][0] = 0;
    }
}

Game of Life

吸取了上一题的经验之后，这题很容易就一次 AC 了~

• 0 : 未访问，死

• 1 : 未访问，活

• 2 : 已访问，当前活，下轮活

• 3 : 已访问，当前活，下轮死

• -2 : 已访问，当前死，下轮活

• -3 : 已访问，当前死，下轮死

正确定义了状态之后就不会产生邻居在不同迭代周期时互相影响的问题了。

从以上两题可以发现，当我们需要 in-place 处理矩阵的时候，最简便直接的思路往往是“多个 pass”的，即用一次 pass 做标记，第二次甚至第三次 pass 再做实际处理。

public class Solution {
    public void gameOfLife(int[][] board) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                board[i][j] = nextState(board, i, j);
            }
        }

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == 2 || board[i][j] == -2) board[i][j] = 1;
                else board[i][j] = 0;
            }
        }
    }

    private int nextState(int[][] board, int row, int col){
        int[] xDirs = {0, 0, 1, -1, 1, -1, -1,  1};
        int[] yDirs = {1,-1, 0,  0, 1, -1,  1, -1};

        int aliveCount = 0;

        for(int i = 0; i < 8; i++){
            int x = row + xDirs[i];
            int y = col + yDirs[i];
            // legal position
            if(x >= 0 && x < board.length && y >= 0 && y < board[0].length){
                if(board[x][y] > 0) aliveCount ++;
            }
        }

        if(board[row][col] == 0){
            if(aliveCount == 3) return -2;
            else                return -3;
        } else {
            if(aliveCount == 2 || aliveCount == 3) return 2;
            else                                   return 3;
        }
    }
}

Rotate Image

和剥洋葱差不多，一层一层从外向里；我第一种写的多一点，但是更值得学习和更好推广的是第二种。

public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return;

        int n = matrix.length;

        for(int i = 0; i < n / 2; i++){
            for(int j = i; j < n - i - 1; j++){
                swap(matrix, i, j, j, n - 1 - i);
                swap(matrix, i, j, n - 1 - i, n - 1 - j);
                swap(matrix, i, j, n - 1 - j, i);
            }
        }
    }

    private void swap(int[][] matrix, int x1, int y1, int x2, int y2){
        int tmp = matrix[x1][y1];
        matrix[x1][y1] = matrix[x2][y2];
        matrix[x2][y2] = tmp;
    }
}

另一种更直观更好理解的方式是存两个指针，a , b , 分别代表着当前处理这层的 “左上” 和 “右下” 位置 (矩阵是正方形)，然后 offset 和各种 index 就好计算很多，也完全不需要考虑到 base case 上时候的各种特殊情况。

public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return;

        int n = matrix.length;
        int a = 0;
        int b = n - 1;

        while(a < b){
            for(int i = 0; i < (b - a); i++){
                swap(matrix, a, a + i, a + i, b);
                swap(matrix, a, a + i, b, b - i);
                swap(matrix, a, a + i, b - i, a);
            }
            ++a;
            --b;
        }
    }

    private void swap(int[][] matrix, int x1, int y1, int x2, int y2){
        int tmp = matrix[x1][y1];
        matrix[x1][y1] = matrix[x2][y2];
        matrix[x2][y2] = tmp;
    }
}

Spiral Matrix

维护四个边界，按顺序输出之后步步收缩。

特别注意处理 “下” 和 “左” 边界的时候，有可能当前这层只有一行，或者一列，已经输出过了不需要重复输出。所以这两条边的循环上要注意加一个判断条件。

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if(matrix == null || matrix.length == 0) return list;

        int rowStart = 0;
        int rowEnd = matrix.length - 1;
        int colStart = 0;
        int colEnd = matrix[0].length - 1;

        while(rowStart <= rowEnd && colStart <= colEnd){
            // add top frame
            for(int i = colStart; i <= colEnd; i++) list.add(matrix[rowStart][i]);
            rowStart ++;
            // add right frame
            for(int i = rowStart; i <= rowEnd; i++) list.add(matrix[i][colEnd]);
            colEnd --;
            // add bot frame
            if(rowStart <= rowEnd) for(int i = colEnd; i >= colStart; i--) list.add(matrix[rowEnd][i]);
            rowEnd --;
            // add left frame
            if(colStart <= colEnd) for(int i = rowEnd; i >= rowStart; i--) list.add(matrix[i][colStart]);
            colStart ++;
        }

        return list;
    }
}

Spiral Matrix II

顺着同一个思路，于是这题可以轻松随意撸出来~~

public class Solution {
    public int[][] generateMatrix(int n) {
        if(n <= 0) return new int[0][0];

        int[][] matrix = new int[n][n];

        int rowStart = 0;
        int rowEnd = n - 1;
        int colStart = 0;
        int colEnd = n - 1;

        int curNum = 1;

        while(rowStart <= rowEnd && colStart <= colEnd){
            for(int i = colStart; i <= colEnd; i++) matrix[rowStart][i] = curNum++;
            rowStart ++;

            for(int i = rowStart; i <= rowEnd; i++) matrix[i][colEnd] = curNum++;
            colEnd --;

            if(rowStart <= rowEnd) for(int i = colEnd; i >= colStart; i--) matrix[rowEnd][i] = curNum++;
            rowEnd --;

            if(colStart <= colEnd) for(int i = rowEnd; i >= rowStart; i--) matrix[i][colStart] = curNum++;
            colStart ++;
        }

        return matrix;
    }
}

(G) 对角打印矩阵，左上到右下，按对角线长度降序打印

• 自定义一个函数，给定起点，打印对角线；

• 检查下 rows / cols 的长度，先把长的边长起点放进去；

• 而后依次轮流放入第一列 / 第一行的新起点，依次打印即可。

    public static void printMatrix(int[][] matrix){
        if(matrix == null || matrix.length == 0) return;
        int rows = matrix.length;
        int cols = matrix[0].length;

        int row = 0;
        int col = 0;
        if(cols > rows){
            for(int i = 0; i < cols - rows; i++){
                printDiagnal(matrix, 0, col++);
            }
        } else if(rows > cols){
            for(int i = 0; i < rows - cols; i++){
                printDiagnal(matrix, row++, 0);
            }
        }

        printDiagnal(matrix, row++, col++);

        while(row < rows || col < cols){
            if(rows - row < cols - col){
                printDiagnal(matrix, 0, col++);
            } else {
                printDiagnal(matrix, row++, 0);
            }
        }

    }

    private static void printDiagnal(int[][] matrix, int row, int col){
        if(matrix == null || matrix.length == 0) return;

        int rows = matrix.length;
        int cols = matrix[0].length;

        while(row < rows && col < cols){
            System.out.print(" " + matrix[row++][col++]);
        }
        System.out.println();
    }

    public static void main(String[] args){
        int rows = 8;
        int cols = 5;

        int[][] matrix = new int[rows][cols];

        int num = 1;
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 5; j++){
                System.out.print(num + "    ");
                matrix[i][j] = num++;
            }
            System.out.println();
        }

        printMatrix(matrix);
    }