个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言今天是数组的最后一章节最近还在整理苍穹外卖前面我们刚学完关于滑动窗口的方法这一章节我们学习螺旋矩阵这是面试中常见的题目主要考察的不是思维而是我们能否正确顺畅的手撕出来是一个中等题。题目背景LeetCode 59给定一个正整数 n生成一个包含 1 到 n^2 所有元素且元素按顺时针顺序螺旋排列的正方形矩阵。示例:输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]题目理解看到这个题目我们第一眼可能不知道题目要干什么但是仔细地看一眼我们就能理解了根据我们输入的正整数n会生成一个正方形的矩阵如果所示而且还是按照顺时针方向的排列方向思路其实很简单但是在具体操作的时候往往会让我们纠结或者搞混就和二分法一样难的不是思路而是我们能否清晰的把这道题写出来而不是漏掉一些或者写错一些地方。下面我们会讲解具体的方法题目答案class Solution { public int[][] generateMatrix(int n) { int[][] nums new int[n][n]; int startX 0, startY 0; // 每一圈的起始点 int offset 1; int count 1; // 矩阵中需要填写的数字 int loop 1; // 记录当前的圈数 int i, j; // j 代表列, i 代表行; while (loop n / 2) { // 顶部 // 左闭右开所以判断循环结束时 j 不能等于 n - offset for (j startY; j n - offset; j) { nums[startX][j] count; } // 右列 // 左闭右开所以判断循环结束时 i 不能等于 n - offset for (i startX; i n - offset; i) { nums[i][j] count; } // 底部 // 左闭右开所以判断循环结束时 j ! startY for (; j startY; j--) { nums[i][j] count; } // 左列 // 左闭右开所以判断循环结束时 i ! startX for (; i startX; i--) { nums[i][j] count; } startX; startY; offset; loop; } if (n % 2 1) { // n 为奇数时单独处理矩阵中心的值 nums[startX][startY] count; } return nums; } }题目讲解在写这道题的时候我们要遵循一个选择就是循环不变量原则跟写二分法一样我们要根据一个固定的原则来写循环在二分法中我们是事先固定了区间范围之后再写内部逻辑。在这里我们要先固定每次循环的起始位置这里我们固定的是从起始开始而不遍历每一行的最后一个元素这样执行一圈之后正好全部遍历到而不是一会遍历一会不遍历的类似于数学中的控制变量法因为循环本来就是一个动态的过程如果我们连条件都没固定那岂不是很容易混乱。底层逻辑已经讲完了下面我们来说一下代码的实现逻辑顺时针排列那起始位置就是原点我们定义起始位置startXstartY代表原点和一个二维数组代表ij轴这个位置就是记录添加到哪个位置的我们还定义了loop是代表要循环几圈如果是奇数圈那么最后一圈就不满足我们while的条件就执行到了if最后一圈就是内部的一个点直接把count添加到里面即可。那我们在核心循环的代码实现思路我们一开始是从j轴开始的就是最顶部的一行循环的截止条件是n-offset代表不去遍历最后一个位置然后就是第二次for循环我们是遍历最右侧j轴不变i轴加加不遍历最后一个把遍历到的每个位置count的值都赋给当前的位置count第三次for循环的时候注意条件条件是i轴不变j轴--而此时j的值就是n已经在最底部的位置了因此一直--直到等于0时截止。下面的也同理。当循环完这一圈之后我们进行的一系列操作首先就是对原点位置的向内收缩都是加一偏移量offset自然也就是加1因为内圈的行列数都少了一格圈数加1以此类推。下面我们来讲解这道题相反过程的题目背景LeetCode 54给你一个m行n列的矩阵matrix请按照顺时针螺旋顺序返回矩阵中的所有元素。示例 1输入matrix [[1,2,3],[4,5,6],[7,8,9]]输出[1,2,3,6,9,8,7,4,5]示例 2输入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.lengthn matrix[i].length1 m, n 10-100 matrix[i][j] 100题目理解这道题的背景跟上一题一摸一样仅仅是过程相反了我们完全可以用上面相同的方式来处理但是有细微的差别下面具体说明同时附上另一种优化的解法。第一种解法class Solution { public ListInteger spiralOrder(int[][] matrix) { ListInteger result new ArrayList(); if (matrix null || matrix.length 0) { return result; } int m matrix.length; // 行数 int n matrix[0].length; // 列数 int startX 0, startY 0; // 起始位置 int offset 1; // 偏移量 int loop 1; // 当前圈数 int i, j; // 需要遍历多少圈取行和列的最小值除以2 int circles Math.min(m, n) / 2; while (loop circles) { // 顶部从左到右 for (j startY; j n - offset; j) { result.add(matrix[startX][j]); } // 右列从上到下 for (i startX; i m - offset; i) { result.add(matrix[i][j]); } // 底部从右到左 for (; j startY; j--) { result.add(matrix[i][j]); } // 左列从下到上 for (; i startX; i--) { result.add(matrix[i][j]); } startX; startY; offset; loop; } // 处理中间剩余的行或列 if (Math.min(m, n) % 2 1) { if (m n) { // 行数少剩余一行 for (j startY; j n - offset; j) { result.add(matrix[startX][j]); } } else { // 列数少剩余一列 for (i startX; i m - offset; i) { result.add(matrix[i][startY]); } } } return result; } }题目解析底层逻辑是一样的需要注意的细节是我们第一提到的是正方形矩阵但这道题目并没有规定而是矩形那么这就默认了行和列并不是完全相等的因此我们需要单独注意这一部分首先被牵扯到的就是循环的圈数了我们需要从行和列中找一个较小值来计算圈数而不是像第一那样不用考虑其次就是内圈的处理问题在结束了外层圈的循环在最后一圈的时候我们就需要判断到底是行少还是列少因为这决定了我们执行最后一次循环的方向到底是按i方向还是j方向这里的循环条件为什么是n-offset因为 我们的startX或则startY都已经自增向内缩进了我们要遍历完这行或者列不好解释如图吧完整过程原始矩阵 [1, 2, 3, 4] [5,6, 7, 8] [9, 10, 11, 12] 第1圈遍历后最外层 已遍历1,2,3,4,8,12,11,10,9,5 剩余 [6, 7] ← 这是1行2列 此时 startX 1 startY 1 m - offset 3 - 2 1 n - offset 4 - 2 2 剩余的是第1行从第1列到第2列 for (j startY; j n - offset; j) { // j从1到2 result.add(matrix[1][1]) 6 result.add(matrix[1][2]) 7 }图解第1圈后 [1, 2, 3, 4] [5, ← 中心区域 → 8] [9,10,11,12] 中心区域剩余一行 startX1 [6, 7] ← 一行 startY1 到 n-offset2这样看下来当我们执行完外层的圈数时这时还剩下一行67没有添加原点位置被缩进了其实就执行了索引1和2刚好添加完。第二种优化解法class Solution { public ListInteger spiralOrder(int[][] matrix) { ListInteger result new ArrayList(); if (matrix null || matrix.length 0) { return result; } int top 0; int bottom matrix.length - 1; int left 0; int right matrix[0].length - 1; while (top bottom left right) { // 1. 从左到右遍历上边 for (int j left; j right; j) { result.add(matrix[top][j]); } top; // 上边界下移 // 2. 从上到下遍历右边 for (int i top; i bottom; i) { result.add(matrix[i][right]); } right--; // 右边界左移 // 3. 从右到左遍历下边需要检查是否还有行 if (top bottom) { for (int j right; j left; j--) { result.add(matrix[bottom][j]); } bottom--; // 下边界上移 } // 4. 从下到上遍历左边需要检查是否还有列 if (left right) { for (int i bottom; i top; i--) { result.add(matrix[i][left]); } left; // 左边界右移 } } return result; } }题目解析这种解法的核心逻辑就是实时更新边界而不用手动的去处理最后一圈这种解法用来解决我们正向59题也是同样优雅的避免了offset的使用首先就是变量的定义int botton matrix.length; // 有多少行 3 int right matrix[0].length; // 第一行有多少列 3就是记录二维数组的上下左右的边界while循环的判断条件这个条件是边界检查确保在遍历过程中不会越界并且能正确处理各种形状的矩阵正方形、长方形、单行、单列。直到执行完之后才自动跳过。因为这个遍历的过程就是边界的收缩过程知道最后重合到一个点或者是一行一列时才结束while。下面的for循环大差不大。结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励