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

59 螺旋矩阵||

Alt text

  • 思考:怎么[模拟]矩阵的遍历顺序呢?自然直觉是跟随题意螺旋式有外层向内层遍历,具体而言呢?
  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 螺旋矩阵

Alt text

  • 思考:其实就是上一题的反向过程,起初按照循环不变量的遍历逻辑,遇到了很多特殊情况,略复杂。
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插件快速发布