3112、访问消失节点的最小时间

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

• 输入:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

• 输出: [1,2,3,6,9,8,7,4,5]

示例 2:

• 输入:

[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]

-输出: [1,2,3,4,8,12,11,10,9,5,6,7]

使用方向辅助索引，变更放心进行遍历赋值

• 按照规则走，借助一个辅助数组，对走过的点进行标记
• 类似又一个行径箭头，方向控制

class Solution{
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<Integer>();
        if (matrix.length == 0) return ans;
        int R = matrix.length;
        int C = matrix[0].length;
        boolean[][] seen = new boolean[R][C];
        // dr dc 方向控制，向右 向下 向左 向上
        int[] dr = {0,1,0,-1};
        int[] dc = {1,0,-1,0};
        int r = 0,c = 0,di = 0;
        for (int i = 0;i < R*C;i++) {
            // 加入到结果
            ans.add(matrix[r][c]);
            seen[r][c] = true;
            // 更新r,c
            int cr = r + dr[di];
            int cc = c + dc[di];
            // 没有越界且没有访问过
            if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]) {
                r = cr;
                c = cc;
            } else {// 需要转向
                di = (di + 1) % 4;
                r += dr[di];
                c += dc[di];
            }
        }
        return ans;
    }
}

使用边界索引，进行赋值

• 按层模拟

• 剥洋葱

• 初始化结果数组

• 初始化列下标r1 r2

• 初始化行下标c1 c2

• 循环 r1 <= r2 && c1 <= c2

  • 读取上面一行[c1,c2]
  • 读取右侧一列 从r1 + 1开始[r1 + 1, r2]，因为第一行已经读取了 r1的位置
  • 如果 r1 < r2 && c1 < c2 避免无数据
    • 读取底部一行 从c2 - 1开始(c1,c2-1]，因为右侧一列已经读取了c2 的位置
    • 读取左侧一列 [r2,r1]
  • 更新矩阵边界
    • r1++
    • r2--
    • c1++
    • c2--

• 返回结果数组

class Solution{
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<Integer>();
        if (matrix.length == 0) return ans;
        // 全局索引
        int r1 = 0,r2 = matrix.length - 1;// 行索引
        int c1 = 0,c2 = matrix[0].length - 1;// 列索引
        // 顺时针螺旋读取数据
        while (r1 <= r2 && c1 <= c2) {
            // 一横
            for (int c = c1;c <= c2;c++) ans.add(matrix[r1][c]);
            // 一竖
            for (int r = r1 + 1;r <= r2;r++) ans.add(matrix[r][c2]);

            if (r1 < r2 && c1 < c2) {// 还有数据 r1 >= r2 说明
                // 逆一横
                for (int c = c2 - 1;c > c1;c--) ans.add(matrix[r2][c]);
                // 逆一竖
                for (int r = r2;r > r1;r--) ans.add(matrix[r][c1]);
            }
            r1++;
            r2--;
            c1++;
            c2--;
        }
        return ans;
    }
}

59、旋转矩阵II

54题的相反的过程，54题是取值 59题是放值

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

思路

• 原来的读取变为赋值
• 位置状态处理

代码

class Solution {
    public int[][] generateMatrix(int n) {
        int count = 1;
        int r1 = 0,r2 = n-1;
        int c1 = 0,c2 = n-1;
        int[][] res = new int[n][n];
        while (r1 <= r2 && c1 <= c2) {
            // [c1,c2]
            for (int c = c1;c <= c2;c++) {
                res[r1][c] = count++;
            }
            // [r1+1,r2]
            for (int r = r1 + 1; r <= r2;r++) {
                res[r][c2] = count++;
            }
            if (r1 < r2 && c1 < c2) {
                // [c1+1,c2-1]
                for (int c = c2-1;c > c1;c--) {
                    res[r2][c] = count++;
                }
                // [r1+1,r2]
                for (int r = r2;r > r1;r--) {
                    res[r][c1] = count++;
                }
            }
            c1++;
            c2--;
            r1++;
            r2--;
        }
        
        return res;
        
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com