精选力扣500题第25题 LeetCode 54. 螺旋矩阵【c++ / java 详细题解】

太过爱你忘了你带给我的痛 2021-07-24 11:43 361阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、c++代码
         *  4、java代码

### 1、题目 ###

给你一个 `m` 行 `n` 列的矩阵 `matrix` ，请按照 **顺时针螺旋顺序** ，返回矩阵中的所有元素。

**示例 1：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70][]

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[1,2,3,6,9,8,7,4,5]

**示例 2：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1][]

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

**提示：**

*  `m == matrix.length`
 *  `n == matrix[i].length`
 *  `1 <= m, n <= 10`
 *  `-100 <= matrix[i][j] <= 100`

### 2、思路 ###

*  1、我们顺时针定义四个方向：上右下左。
    
    `d = 0`表示向上走，`d = 1`表示向右走，`d = 2`表示向下走，`d = 3`表示向左走。
 *  2、使用`d=(d+1)%4`来更改方向当前位置`(x,y)`,下个位置`(a, b)`，`a=x+dx[d], b=y+dy[d]`。
 *  3、从左上角开始遍历，先往右走，走到不能走为止，然后更改到下个方向，再走到不能走为止，依次类推，遍历  n 2 n^2 n2 个格子后停止。

**图示**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UJnbDqrl-1622160008455)(力扣500题刷题笔记.assets/20210409112830795.png)\]][img-UJnbDqrl-1622160008455_500_.assets_20210409112830795.png]

### 3、c++代码 ###

class Solution { 
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) { 
            vector<int>res;
            if(matrix.empty()) return res;
            int n = matrix.size(), m = matrix[0].size();
            vector<vector<bool>> st(n,vector<bool>(m,false));
            int dx[4] = {  - 1, 0 , 1, 0}, dy[4] = {  0, 1, 0, -1};
            int x = 0, y = 0 ,d = 1;
            for(int i = 0; i < n*m; i++)
            { 
                res.push_back(matrix[x][y]);
                st[x][y] = true; //标记该点为走过
    
                int a = x + dx[d], b = y + dy[d]; //下一个点
                if(a < 0 || a >= n || b < 0 || b >=m || st[a][b])
                { 
                    d = (d + 1) % 4; //按照上右下左更改方向
                    a = x + dx[d], b = y + dy[d];
                }
                x = a, y = b;
            }
            return res;   
        }
    };

### 4、java代码 ###

class Solution { 
        public List<Integer> spiralOrder(int[][] matrix) { 
            List<Integer> result = new ArrayList();
            if(matrix == null || matrix.length < 1) return result;
    
            int m = matrix.length, n = matrix[0].length;
            int[] dx = { 0,1,0,-1}, dy = { 1,0,-1,0};
            boolean[][] used = new boolean[m][n];
    
            for(int i = 0, x = 0, y = 0, d = 0; i < m * n; i++){ 
                result.add(matrix[x][y]);
                used[x][y] = true;
    
                //检验下一个位置是否合法, 不合法则更新方向, 并重新计算下一个位置
                int a = x + dx[d], b = y + dy[d];
                if( a < 0 || a >= m || b < 0 || b >= n || used[a][b]){ 
                 
                    d = (d + 1) % 4;
                    a = x + dx[d];
                    b = y + dy[d];
                }
    
                x = a ;
                y = b;
            }
    
            return result;
        }
    }

**原题链接：** [54. 螺旋矩阵][54.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/687f4afa669645dfb364f78b8e3379d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/21814e82370b4d308fc13a1a42cdcfaf.png
[img-UJnbDqrl-1622160008455_500_.assets_20210409112830795.png]: /images/20210724/8ce9cc7e85134577828dd7304f07abcb.png
[54.]: https://leetcode-cn.com/problems/spiral-matrix/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/2186f69452d74d77afac387a0edd16ae.png