代码随想录-数组-螺旋矩阵

59 螺旋矩阵||

• 思考：怎么[模拟]矩阵的遍历顺序呢？自然直觉是跟随题意螺旋式有外层向内层遍历，具体而言呢？

1. 代码随想录：把握循环不变量，对于每一层的每一条边而言，只访问前l-1个位置（l为该层边长，最外层l=n）
2. 有多少层？n=1时视作0层，随后发现n=N时，对应有N/2层；当N为奇数时，最后单独处理中心位置；
3. 每一层具体怎么遍历？设置变量startx和starty分别表示每一层的左上角坐标，offset用于控制每条边的边长；到下一层后，startx和starty各自加一，相当于向右下方移动，offset也加一模拟边长缩短（为什么不是加2？因为startx和starty也在移动）；
4. 最后中心点的坐标是[i][j]还是[startx][starty]？是后者

public static int[][] generateMatrix(int n) {
        int[][] ints = new int[n][n];
        int startx = 0, starty = 0, offset = 1;
        int i = 0, j = 0, count = 1;
        int rounds = n / 2;
        while ((rounds--) > 0) {
            for (i = starty, j = startx; j < n - offset; j++) {
                ints[i][j] = count++;
            }
            for (; i < n - offset; i++) {
                ints[i][j] = count++;
            }
            for (; j > startx; j--) {
                ints[i][j] = count++;
            }
            for (; i > starty; i--) {
                ints[i][j] = count++;
            }
            startx++;
            starty++;
            offset++;
        }
        if (n % 2 != 0) {
            ints[startx][starty] = count;
        }
        return ints;
    }

• 更好的方法：假设当前在最外层，顶边从左到右遍历，结束后想象矩阵第一行消失；右边从上到下遍历，结束后想象矩阵最右边一列消失；以此类推
  1. 怎么体现消失？设置四条界线
  2. 怎么算遍历结束？上下界线交错或者左右界线交错

public static int[][] generateMatrix1(int n) {
        int[][] matrix = new int[n][n];
        int count = 1;
        if (n == 0) return matrix;
        int i_up = 0, i_down = n - 1, j_left = 0, j_right = n - 1;
        while (true) {
            for (int k = j_left; k <= j_right; k++) {
                matrix[i_up][k] = count++;
            }
            if (++i_up > i_down) break;
            for (int k = i_up; k <= i_down; k++) {
                matrix[k][j_right] = count++;
            }
            if (--j_right < j_left) break;
            for (int k = j_right; k >= j_left; k--) {
                matrix[i_down][k] = count++;
            }
            if (--i_down < i_up) break;
            for (int k = i_down; k >= i_up; k--) {
                matrix[k][j_left] = count++;
            }
            if (++j_left > j_right) break;
        }
        return matrix;
    }

第二种方法取消了循环不变量，思想更具有普适性，尤其是当矩形是m*n规模时，只需修改边界起始参数即可；第一种方法则需要考虑更多特殊情况。这一特点在下一题中将会得到体现。

54 螺旋矩阵

• 思考：其实就是上一题的反向过程，起初按照循环不变量的遍历逻辑，遇到了很多特殊情况，略复杂。

public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int startx = 0, starty = 0, offset = 1;
        int i = 0, j = 0;
        int m = matrix.length, n = matrix[0].length;
        int min = Math.min(m, n), rounds = min / 2;
        if (m == 1) {
            for (int k = 0; k < n; k++) {
                res.add(matrix[0][k]);
            }
            return res;
        }
        if (n == 1) {
            for (int k = 0; k < m; k++) {
                res.add(matrix[k][0]);
            }
            return res;
        }
        while ((rounds--) > 0) {
            for (i = starty, j = startx; j < n - offset; j++) {
                res.add(matrix[i][j]);
            }
            for (; i < m - offset; i++) {
                res.add(matrix[i][j]);
            }
            for (; j > startx; j--) {
                res.add(matrix[i][j]);
            }
            for (; i > starty; i--) {
                res.add(matrix[i][j]);
            }
            startx++;
            starty++;
            offset++;
        }
        if (min % 2 == 1) {
            if (m < n) {
                for (i = starty, j = startx; j < n - offset + 1; j++) {
                    res.add(matrix[i][j]);
                }
            } else {
                for (i = starty, j = startx; i < m - offset + 1; i++) {
                    res.add(matrix[i][j]);
                }
            }
        }
        return res;

• 更好的方法

public static List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        //以下变量分别表示纵坐标的左右界和横坐标的左右界
        //遍历顺序为：右-下-左-上，每遍历完一条边将相应移动一条界线，比如左->右完成了最上面的一条边，随即将--i_up
        //遍历结束的标志？上边界大于下边界，右边界小于左边界
        int i_up = 0, i_down = matrix.length - 1, j_left = 0, j_right = matrix[0].length - 1;
        while (true) {
            for (int k = j_left; k <= j_right; k++) {
                res.add(matrix[i_up][k]);
            }
            if (++i_up > i_down) break;
            for (int k = i_up; k <= i_down; k++) {
                res.add(matrix[k][j_right]);
            }
            if (--j_right < j_left) break;
            for (int k = j_right; k >= j_left; k--) {
                res.add(matrix[i_down][k]);
            }
            if (--i_down < i_up) break;
            for (int k = i_down; k >= i_up; k--) {
                res.add(matrix[k][j_left]);
            }
            if (++j_left > j_right) break;
        }
        return res;
    }

---

本文章使用limfx的vscode插件快速发布