二维数组的螺旋矩阵问题

爱被打了一巴掌 2023-07-01 06:27 19阅读 0赞

> 一直在刷LeetCode，也没有放在博客上面，题目太多感觉也没有必要放在这上面。  
> 有兴趣的可以看我的GitHub题解： [https://github.com/xdxTao/LeetCode][https_github.com_xdxTao_LeetCode]

### 1、什么是螺旋矩阵呢？ ###

**1-1：我们正常的遍历二维数组都是一层一层的遍历。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70]

**1-2：但是螺旋遍历的方式是这样的**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70 1]

### 2、解题思路 ###

**2-1：遍历的方式是：我们每次只移动 i、j，其中一个，并且一直移动到底。**

**2-2：我们需要考虑每一个临界点上的变化。**

**2-3：我们可以定义三个变量来辅助我们判断**

*  int moveFlag = ‘j’; （当moveFlag=i，的时候是移动 i，否则移动 j）
 *  char jDir = ‘→’; （j 移动的方向，用这种箭头太直接了，哈哈）
 *  char iDir = ‘↓’; (同理 i，的移动方向)

### 3、举例（下面以leetcode上面两个题为例） ###

**59. 螺旋矩阵 II**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70 2]

**题解：**

*  new 一个空数组里面每一个默认数据都是0 ，（我将返回的数组命名为 result）
 *  到达**右边界** ： j+1 >= n || result\[i\]\[j+1\] != 0
 *  到达**左边界** ： j-1 < 0 || result\[i\]\[j-1\] != 0
 *  到达**下边界** ： i+1 >= n || result\[i+1\]\[j\] != 0
 *  到达**上边界** ： i-1 < 0 || result\[i-1\]\[j\] != 0
 *  其实也很好理解，就是判断是否 **超出数组范围**、和**已经赋过值**了

**代码：**

public int[][] generateMatrix(int n) { 
            if (n <= 0){ 
                return new int[][]{ };
            }
            int[][] result = new int[n][n];
            int i = 0,j = 0;
            int moveFlag = 'j';
            char jDir = '→';
            char iDir = '↓';
            int cur = 1;
            while (cur <= n * n){ 
    
                result[i][j] = cur;
                if (moveFlag == 'j'){ 
                    if (jDir == '→'){ 
                        // 到达了右边界
                        if (j+1 >= n || result[i][j+1] != 0){ 
                            // 这时，我们应该让i，向下
                            moveFlag = 'i';
                            iDir = '↓';
                            i ++;
                        }else{ 
                            j++;
                        }
                    }else{ 
                        // 到达了左边界
                        if (j-1 < 0 || result[i][j-1] != 0){ 
                            // 这时，我们应该让i，向上
                            moveFlag = 'i';
                            iDir = '↑';
                            i --;
                        }else { 
                            j --;
                        }
                    }
                }else { 
                    if (iDir == '↓'){ 
                        // 到了下边界
                        if (i+1 >= n || result[i+1][j] != 0){ 
                            // 这时候，我们应该让j,向左
                            moveFlag = 'j';
                            jDir = '←';
                            j --;
                        }else{ 
                            i ++;
                        }
                    }else { 
                        // 到达了上边界
                        if (i-1 < 0 || result[i-1][j] != 0){ 
                            // 这时候，我们应该让j,向右
                            moveFlag = 'j';
                            jDir = '→';
                            j ++;
                        }else{ 
                            i --;
                        }
                    }
                }
            }
            return result;
        }

**54. 螺旋矩阵**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70 3]

**题解：**

*  这题给出的二维数组名称是 **matrix**，因为数组数据可能是0，所以我们这次用 **Integer.MAX\_VALUE** 来辅助判断
 *  到达**右边界** ： j+1 >= m || matrix\[i\]\[j+1\] == Integer.MAX\_VALUE
 *  到达**左边界** ： j-1 < 0 || matrix\[i\]\[j-1\] == Integer.MAX\_VALUE
 *  到达**下边界** ： i+1 >= n || matrix\[i+1\]\[j\] == Integer.MAX\_VALUE
 *  到达**上边界** ： i-1 < 0 || matrix\[i-1\]\[j\] == Integer.MAX\_VALUE
 *  就是判断是否 **超出数组范围**、和**是否已经遍历过了** (遍历过的 Integer.MAX\_VALUE)

**代码：**

public List<Integer> spiralOrder(int[][] matrix) { 
    
            if (matrix == null || (matrix.length == 0 || matrix[0].length == 0)){ 
                return new ArrayList<>();
            }
            int n = matrix.length;
            int m = matrix[0].length;
            int i = 0,j = 0;
            int moveFlag = 'j';
            char jDir = '→';
            char iDir = '↓';
            List<Integer> result = new ArrayList<>();
            while (true){ 
    
                result.add(matrix[i][j]);
       
                matrix[i][j] = Integer.MAX_VALUE;
    
                if (
    		(i-1 < 0 || matrix[i-1][j] == Integer.MAX_VALUE) && 
    		(i+1 >= n || matrix[i+1][j] == Integer.MAX_VALUE) && 
    		(j - 1 < 0 || matrix[i][j-1] == Integer.MAX_VALUE) && 
    		(j+1 >= m || matrix[i][j+1] == Integer.MAX_VALUE)){ 
    
                    return result;
                }
    
    
                if (moveFlag == 'j'){ 
                    if (jDir == '→'){ 
                        // 到达了右边界
                        if (j+1 >= m || matrix[i][j+1] == Integer.MAX_VALUE){ 
                            // 这时，我们应该让i，向下
                            moveFlag = 'i';
                            iDir = '↓';
                            i ++;
                        }else{ 
                            j++;
                        }
                    }else{ 
                        // 到达了左边界
                        if (j-1 < 0 || matrix[i][j-1] == Integer.MAX_VALUE){ 
                            // 这时，我们应该让i，向上
                            moveFlag = 'i';
                            iDir = '↑';
                            i --;
                        }else { 
                            j --;
                        }
                    }
                }else { 
                    if (iDir == '↓'){ 
                        // 到了下边界
                        if (i+1 >= n || matrix[i+1][j] == Integer.MAX_VALUE){ 
                            // 这时候，我们应该让j,向左
                            moveFlag = 'j';
                            jDir = '←';
                            j --;
                        }else{ 
                            i ++;
                        }
                    }else { 
                        // 到达了上边界
                        if (i-1 < 0 || matrix[i-1][j] == Integer.MAX_VALUE){ 
                            // 这时候，我们应该让j,向右
                            moveFlag = 'j';
                            jDir = '→';
                            j ++;
                        }else{ 
                            i --;
                        }
                    }
                }
            }
        }

[https_github.com_xdxTao_LeetCode]: https://github.com/xdxTao/LeetCode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200119163459593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200119163509782.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200119163523871.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200119163534147.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy,size_16,color_FFFFFF,t_70