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 m = matrix.length; int n = matrix[0].length;
        boolean firstRow = false; boolean firstCol = false;
        for(int i=0;i<m;i++)
            if(matrix[i][0]==0) firstCol = true;
        for(int i=0;i<n;i++)
            if(matrix[0][i]==0) firstRow = true;

        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++){
            if(matrix[i][0]==0){
                for(int j=1;j<n;j++)
                matrix[i][j]=0;
            }
        }

        for(int j=0;j<n;j++){
            if(matrix[0][j]==0){
                for(int i=1;i<m;i++)
                matrix[i][j]=0;
            }
        }
        //System.out.println(firstRow);
        //System.out.println(firstCol);
        if(firstRow){
            for(int i=0;i<n;i++)
                matrix[0][i] = 0;
        }
        if(firstCol){
            for(int j=0;j<m;j++)
                matrix[j][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) {
        if(board==null || board.length==0) return;
        int[] dx = new int[] {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = new int[] {-1, 0, 1, -1, 1, -1, 0, 1};
        int m = board.length; int n=board[0].length;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int count = 0;
                for(int k=0;k<8;k++){
                    int newx = i+dx[k];int newy = j+dy[k];
                    if(newx>=0&&newx<m &&newy>=0&&newy<n && (board[newx][newy]&1)==1)
                        count++;
                }
                if(count<2 && board[i][j]==1) board[i][j] = 1;
                else if(count>=2 && count<=3 && board[i][j]==1) board[i][j] = 3;
                else if(count>3 && board[i][j]==1) board[i][j] = 1;
                else if(count==3 && board[i][j]==0) board[i][j] = 2;
            }
        }

        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                board[i][j] = board[i][j]>>1;
    }
}

Rotate Image

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

这道题需要注意的两点是在rotate的过程中, 为了in place交换, 交换第一条边和第二条边, 再交换第一条边和第三条边, 再交换第一条边和第四条边.

注意边的交换对应关系, 3种.

• swap(matrix, start, start+i, start+i, end);
• swap(matrix, start, start+i, end, end-i);
• swap(matrix, start, start+i, end-i, start);

public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix==null || matrix.length==0) return;
        int start = 0; int end = matrix.length-1;
        while(start<end){
            for(int i=0;i<(end-start);i++){
                swap(matrix, start, start+i, start+i, end);
                swap(matrix, start, start+i, end, end-i);
                swap(matrix, start, start+i, end-i, start);
            }
            start++;
            end--;
        }
    }

    public 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> ans = new ArrayList<Integer>();
        if(matrix==null || matrix.length==0) return ans;

        int startx = 0; int endx = matrix.length-1;
        int starty = 0; int endy = matrix[0].length-1;
        while(startx<=endx && starty<=endy){
            int curx = startx; int cury = starty;
            if(endx==startx){
                while(cury<=endy)
                    ans.add(matrix[curx][cury++]);
                break;
            }
            else if(endy==starty){
                while(curx<=endx)
                ans.add(matrix[curx++][cury]);
                break;
            }


            while(cury<endy)
                ans.add(matrix[curx][cury++]);
            while(curx<endx)
                ans.add(matrix[curx++][cury]);

            while(cury>starty)
                ans.add(matrix[curx][cury--]);

            while(curx>startx)
                ans.add(matrix[curx--][cury]);

            startx++; starty++;
            endx--;endy--;
        }
        return ans;
    }
}

Spiral Matrix II

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

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix= new int[n][n];
        int start = 0; int end = n-1;
        int count = 1;
        while(start<=end){
            int curx = start; int cury = start;
            if(start==end){
                while(cury<=end)
                    matrix[curx][cury++] = count++;
                break;
            }

            while(cury<end)
                matrix[curx][cury++] = count++;
            while(curx<end)
                matrix[curx++][cury] = count++;
            while(cury>start)
                matrix[curx][cury--] = count++;
            while(curx>start)
                matrix[curx--][cury] = count++;
            start++;end--;
        }
        return matrix;
    }
}

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

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

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

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