【剑指offer】顺时针打印矩阵

题目链接

acwing
leetcode

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

数据范围矩阵中元素数量 [0,400]。

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

解题

用偏移量的思想来做！

1. 所以定义偏移量数组
   • dx[] = {-1, 0, 1, 0} //dx存x的偏移量
   • dy[] = {0, 1, 0, -1} //dy存y的偏移量
2. 枚举四个方向的时候，for循环i从0开始枚举到<4
3. 求枚举后的新的坐标 a=x+dx[i] b=y+dy[i]
4. 什么时候更换方向：当越界或者a,b的下标已经存在值之后 更换方向

代码实现

class Solution {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    public int[] printMatrix(int[][] matrix) {
        // 初始方向
        int d = 0;
        int xlength = matrix.length;
        if(xlength == 0) return new int[0];
        int ylength = matrix[0].length;
        
        int[] res = new int[xlength * ylength];
        boolean[][] visit = new boolean[xlength][ylength];
        
        int x = 0, y = 0;
        for(int i = 0; i < xlength*ylength; i ++){
            visit[x][y] = true;
            res[i] = matrix[x][y];
            
            int xNext = x + dx[d];
            int yNext = y + dy[d];
            
            if(xNext < 0 || xNext >= xlength || yNext < 0 || yNext >= ylength || visit[xNext][yNext]){
                d = (d + 1) % 4;
                xNext = x + dx[d];
                yNext = y + dy[d];
            }
            
            x = xNext;
            y = yNext;
        }
        
        return res;
    }
}