Matrix相关

Spiral Matrix

• 面试好题，思路多少有一点，但是想要bug free没有那么容易

• clean code就更难了

• iterate from 4 direcitons, right, down, left, up

• always iterate between rowStart and rowEnd, colStart and colEnd

• need to make sure while (rowStart <= rowEnd && colStart <= colEnd) {}

• 发现一个switch case 的写法，代码简单易懂

public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;
        
        int rowStart = 0, rowEnd = matrix.length - 1, colStart = 0, colEnd = matrix[0].length - 1;
        int dir = 0;
        while (rowStart <= rowEnd && colStart <= colEnd) {
            switch(dir) {
                case 0: //right 
                    for (int j = colStart; j <= colEnd; j++) {
                        res.add(matrix[rowStart][j]);
                    }
                    rowStart++;
                    break;
                    
                case 1: //down
                    for (int i = rowStart; i <= rowEnd; i++) {
                        res.add(matrix[i][colEnd]);
                    }
                    colEnd--;
                    break;
                
                case 2: //left
                    for (int j = colEnd; j>= colStart; j--) {
                        res.add(matrix[rowEnd][j]);
                    }
                    rowEnd--;
                    break;
                    
                case 3: //up
                    for (int i = rowEnd; i >= rowStart; i--) {
                        res.add(matrix[i][colStart]);
                    }
                    colStart++;
                    break;
            }
            dir = (dir + 1) % 4;
        }
        return res;
    }

Spiral Matrix II

• 给定n, generate出一个from 1 to n * n的 spiral matrix

• 套用第一题的代码，稍作修改就好

public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int rowStart = 0, colStart = 0, rowEnd = n - 1, colEnd = n - 1;
        int dir = 0;
        int num = 1;
        while (rowStart <= rowEnd && colStart <= colEnd) {
            switch(dir) {
                case 0: //right 
                    for (int j = colStart; j <= colEnd; j++) {
                        matrix[rowStart][j] = num++;
                    }
                    rowStart++;
                    break;
                    
                case 1: //down
                    for (int i = rowStart; i <= rowEnd; i++) {
                        matrix[i][colEnd] = num++;
                    }
                    colEnd--;
                    break;
                
                case 2: //left
                    for (int j = colEnd; j>= colStart; j--) {
                        matrix[rowEnd][j] = num++;
                    }
                    rowEnd--;
                    break;
                    
                case 3: //up
                    for (int i = rowEnd; i >= rowStart; i--) {
                        matrix[i][colStart] = num++;
                    }
                    colStart++;
                    break;
            }
            dir = (dir + 1) % 4;
        }
        return matrix;
    }