leetcode:54.螺旋矩阵

旧城等待， 2022-01-05 07:55 227阅读 0赞

### 题目描述： ###

给定一个包含 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]

##### 题目难度：中等 #####

##### 分析： #####

可以把整个二维数组看作一个平面，不管是顺时针还是逆时针，都可以看作有一个方向，然后顺着这个方向去读取元素即可。比如：首先从第一行往右读取，那么此时的方向就是`right`，当往右没有元素时，就只能往下，然后此时的方向就是`down`，以此类推即可读取所有的元素。  
代码如下：

class Solution { 
        public List<Integer> spiralOrder(int[][] matrix) { 
            List<Integer> res = new ArrayList<>();
            Set<String> set = new HashSet<>();
            helpMethod(res, set, matrix, 0, 0, 'r');
            return res;
        }
        
        /** * @param res 最终结果 * @param set 临时存储结果，用来判断此位置是否走过 * @param matrix 二维数组 * @param x 横坐标 * @param y 纵坐标 * @param ori 方向 */
        private void helpMethod(List<Integer> res, Set<String> set, int[][] matrix, int x, int y, char ori) { 
            if (matrix.length == 0) { 
                return;
            }
            int m = matrix.length, n = matrix[0].length;
            // 递归结束的条件
            if (res.size() == m * n) return;
            res.add(matrix[x][y]);
            // 走过的位置加入Set集合中
            set.add(x +","+ y);
            // 判断此时的方向
            if (ori == 'r') { 
            	// 判断是否走到头
                if (y == n - 1) { 
                    ori = 'd';
                    x++;
                } else { 
                    y++;
                }
                // 判断此位置是否走过
                if (set.contains(x + "," + y)) { 
                    ori = 'd';
                    x++;
                    y--;
                }
            } else if (ori == 'd') { 
                if (x == m - 1) { 
                    ori = 'l';
                    y--;
                } else { 
                    x++;
                }
                if (set.contains(x + "," + y)) { 
                    ori = 'l';
                    x--;
                    y--;
                }
            } else if (ori == 'l') { 
                if (y == 0) { 
                    ori = 'u';
                    x--;
                } else { 
                    y--;
                }
                if (set.contains(x + "," + y)) { 
                    ori = 'u';
                    x--;
                    y++;
                }
            } else if (ori == 'u') { 
                if (x == 0) { 
                    ori = 'r';
                    y++;
                } else { 
                    x--;
                }
                if (set.contains(x + "," + y)) { 
                    x++;
                    ori = 'r';
                    y++;
                }
            }
            helpMethod(res, set, matrix, x, y, ori);
        }
    }

##### 总结： #####

可以利用递归简化代码的书写，然后根据不同的方向处理不同的逻辑即可。