LeetCode第54题螺旋矩阵

继续打卡算法题，今天学习的是LeetCode第54题螺旋矩阵，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

哈哈，本题没有特定的算法，主要是模拟遍历二维数组，并且是从外到内一层一层的模拟遍历。

模拟遍历的时候我们可以发现一个规律，从左往右或者从右到左遍历访问某行的时候，行号不变，列一直在递增或者递减，直到达到数组边界，从上访问或者从下到上遍历某列的时候，列不变，行一直在递增或者递减。

先从左到右遍历行，列递增 再从上到下遍历列，行递增 再从右到左遍历行，列递减 再从下到上遍历列，行递减

如此反复，直到数组数据全部遍历完成。

我们可以通过一个组数记录这种规律，这种规律可以帮助我们判断什么时候需要修改遍历的行号或者列号。

{{0,1},{1,0},{0,-1},{-1,0}}

{0,1} 代表，行不变，列递增

{1,0} 代表，行递增，列不变

{0,-1}代表，行不变，列递减

{-1,0} 代表，行递减，列不变

我们可以发现，由{0,1} 变成 {1,0}的情况，是列已经遍历到最后一列了，以此类推，可以知道什么时候需要转换遍历方向。

本题解题技巧

本题比较巧妙的地方就是遍历二维数组需要知道什么时候转换方向，通过一个数组存储每个方向行和列的变化规律，能够控制好遍历方向就可以解决本题。

编码解决

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix.length == 0) {
            return new ArrayList<>();
        }
        //顺时针遍历这个螺旋状数组 技巧，由外到内，一层一层往內遍历
        ArrayList<Integer> result = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        
        int row = 0;
        int col = 0;
        int total = m * n;
        //模拟元素访问 一个一个访问 从左到右 从上到下 从右到左 从下到上 的方向 一圈一圈遍历访问
        boolean[][] visited = new boolean[m][n];
        int visitDirect = 0;
        int[][] direct = {{0,1},{1,0},{0,-1},{-1,0}};
        for(int i=0; i< total; i++) {

           result.add(matrix[row][col]);
           visited[row][col] = true;

           //根据当前的访问方向 计算下一个元素位置
           int[] currDirect = direct[visitDirect];
           int nextRow = row + currDirect[0];
           int nextCol = col + currDirect[1];
           //按当前遍历方向判断是否超过了行列，或者访问过了，访问过了就转方向，重新计算下一个访问位置
           if(nextRow >= m || nextCol >= n || nextRow <0 || nextCol < 0 || visited[nextRow][nextCol]) {
               visitDirect = (visitDirect + 1) % 4;
           }
           //计算下次访问的位置
           row = row + direct[visitDirect][0];
           col = col + direct[visitDirect][1];
           System.out.println(row + "dddd" + col);
        }
        
        return result;
    }
}

总结

这种题目看着比较简单，但是写代码实现的时候还是需要掌握技巧的，掌握了遍历规律技巧了就不难，哈哈