leetcode--螺旋矩阵

LCR 146.螺旋遍历二维数组

给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。

螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

示例 1：

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

示例 2：

输入：array  = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

限制：

• 0 <= array.length <= 100
• 0 <= array[i].length <= 100

原理

1. 初始化边界：

   • north, south, east, west 分别表示二维数组的上、下、右、左边界。开始时，north = 0, south = array.length - 1, east = array[0].length - 1, west = 0，即全覆盖数组的外边界。

2. 螺旋遍历：

   • 螺旋遍历从左上角（north, west）开始，顺时针按“右、下、左、上”的顺序遍历二维数组。

   • 第一步： 从左到右遍历，即遍历当前的北边界行。

   • 第二步： 从上到下遍历，即遍历当前的东边界列。

   • 第三步： 从右到左遍历，即遍历当前的南边界行。

   • 第四步： 从下到上遍历，即遍历当前的西边界列。

   每一轮螺旋遍历后，都会减少遍历区域的边界：

   • north++：上边界下移
   • west++：左边界右移
   • south--：下边界上移
   • east--：右边界左移

   这样，每完成一圈遍历，内层的元素逐步被收录，直到所有元素都被遍历完。

3. 终止条件：

   • 当 sum（剩余未遍历元素的数量）为 0 时，表示所有元素都已被访问完，跳出循环。

4. 返回结果：

   • 最终，list 数组包含了螺旋遍历的所有元素，按顺序返回。

时间复杂度：

• 假设数组的维度是 m x n，遍历所有元素的时间复杂度是 O(m * n)，因为每个元素都只会被访问一次。

空间复杂度：

• 空间复杂度为 O(m * n)，因为需要一个大小为 m * n 的数组来存储遍历的结果。

代码 

class Solution {public int[] spiralArray(int[][] array) {// 获取二维数组的行数，即南边界int south = array.length - 1;  // 如果数组没有行，直接返回空数组if (south == -1) {return new int[0];}// 获取二维数组的列数，即东边界int east = array[0].length - 1;  // 如果数组没有列，直接返回空数组if (east == -1) {return new int[0];}// 计算二维数组中的总元素个数，决定返回数组的大小int sum = (south + 1) * (east + 1);  // 初始化边界int north = 0, west = 0;// 创建存储结果的数组int[] list = new int[sum];// count 用来记录当前插入的位置int count = 0;// 开始螺旋遍历while (sum > 0) {// 从左到右遍历（沿着北边界）for (int i = west; i <= east; i++) {list[count++] = array[north][i];  // 将当前元素加入结果数组sum--;  // 每遍历一个元素，减去一个}// 如果所有元素已经遍历完，跳出循环if (sum == 0) {break;}// 从上到下遍历（沿着东边界）for (int i = north + 1; i <= south; i++) {list[count++] = array[i][east];  // 将当前元素加入结果数组sum--;  // 每遍历一个元素，减去一个}// 如果所有元素已经遍历完，跳出循环if (sum == 0) {break;}// 从右到左遍历（沿着南边界）for (int i = east - 1; i >= west; i--) {list[count++] = array[south][i];  // 将当前元素加入结果数组sum--;  // 每遍历一个元素，减去一个}// 如果所有元素已经遍历完，跳出循环if (sum == 0) {break;}// 从下到上遍历（沿着西边界）for (int i = south - 1; i > north; i--) {list[count++] = array[i][west];  // 将当前元素加入结果数组sum--;  // 每遍历一个元素，减去一个}// 更新边界，进入内层north++;west++;south--;east--;}// 返回螺旋遍历的结果return list;}
}

 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.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

原理

1. 初始化边界：

   • north, south, east, west 分别表示二维数组的上、下、右、左边界。开始时，north = 0, south = matrix.length - 1, east = matrix[0].length - 1, west = 0，即全覆盖矩阵的外边界。

2. 螺旋遍历：

   • 螺旋遍历从左上角（north, west）开始，顺时针按“右、下、左、上”的顺序遍历二维矩阵中的元素。

   • 第一步： 从左到右遍历，即遍历当前的北边界行。

   • 第二步： 从上到下遍历，即遍历当前的东边界列。

   • 第三步： 从右到左遍历，即遍历当前的南边界行。

   • 第四步： 从下到上遍历，即遍历当前的西边界列。

   每完成一圈螺旋遍历后，都会更新边界：

   • north++：上边界下移
   • west++：左边界右移
   • south--：下边界上移
   • east--：右边界左移

   这样，每完成一圈遍历，内层的元素逐步被收录，直到所有元素都被遍历完。

3. 终止条件：

   • 当 sum（剩余未遍历元素的数量）为 0 时，表示所有元素都已被访问完，跳出循环。

4. 返回结果：

   • 最终，list 列表包含了矩阵的螺旋顺序遍历结果，按顺序返回。

时间复杂度：

• 假设矩阵的维度是 m x n，遍历所有元素的时间复杂度是 O(m * n)，因为每个元素只会被访问一次。

空间复杂度：

• 空间复杂度为 O(m * n)，因为需要一个大小为 m * n 的列表来存储遍历的结果。

代码 

class Solution {public List<Integer> spiralOrder(int[][] matrix) {// 获取矩阵的南边界（即最后一行的索引）int south = matrix.length - 1;// 获取矩阵的东边界（即最后一列的索引）int east = matrix[0].length - 1;// 计算矩阵中元素的总数int sum = (south + 1) * (east + 1);// 初始化边界，north 是上边界，west 是左边界int north = 0, west = 0;// 用一个列表来存储螺旋遍历的结果List<Integer> list = new ArrayList<>(south * east);// 螺旋遍历开始，直到所有元素都被访问while (sum > 0) {// 1. 从左向右遍历（沿着北边界）for (int i = west; i <= east; i++) {list.add(matrix[north][i]);  // 将当前元素加入结果列表sum--;  // 减少未访问的元素数目}// 如果所有元素已经遍历完，退出循环if (sum == 0) {break;}// 2. 从上到下遍历（沿着东边界）for (int i = north + 1; i <= south; i++) {list.add(matrix[i][east]);  // 将当前元素加入结果列表sum--;  // 减少未访问的元素数目}// 如果所有元素已经遍历完，退出循环if (sum == 0) {break;}// 3. 从右向左遍历（沿着南边界）for (int i = east - 1; i >= west; i--) {list.add(matrix[south][i]);  // 将当前元素加入结果列表sum--;  // 减少未访问的元素数目}// 如果所有元素已经遍历完，退出循环if (sum == 0) {break;}// 4. 从下到上遍历（沿着西边界）for (int i = south - 1; i > north; i--) {list.add(matrix[i][west]);  // 将当前元素加入结果列表sum--;  // 减少未访问的元素数目}// 更新边界，进入内层north++;  // 上边界下移west++;   // 左边界右移south--;  // 下边界上移east--;   // 右边界左移}// 返回螺旋遍历的结果return list;}
}

59.螺旋矩阵II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

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

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

原理

1. 初始化：

   • 我们首先创建一个大小为 n x n 的矩阵 ans。
   • 用 sum 变量记录当前要填充的数字，从 1 开始递增。
   • 使用 row 和 column 变量来指示当前的矩阵填充位置。

2. 螺旋顺序填充：

   • 每一圈的填充包括四个方向：向右、向下、向左、向上，依次填充矩阵的边界。
   • 向右： 从当前的 (row, column) 开始，向右填充 n 个位置。
   • 向下： 在完成右边的填充后，向下填充 n-1 个位置。
   • 向左： 完成下边的填充后，向左填充 n-2 个位置。
   • 向上： 完成左边的填充后，向上填充 n-3 个位置。

   每次一圈填充后，更新边界，将 n 减少 2，以保证下一圈填充在内层矩阵中进行。

3. 边界收缩：

   • 每次完成一圈的填充后，column++ 将列向右移动，准备进行下次填充。
   • 同时 n -= 2，表示当前有效矩阵的边长减少 2，从而让填充继续进行到内层。

4. 终止条件：

   • 当 n <= 0 时，表示已经填充完所有的元素，退出循环并返回结果矩阵。

时间复杂度：

• 假设矩阵的大小为 n x n，所有元素都需要被遍历一次并填充。因此时间复杂度为 O(n²)。

空间复杂度：

• 需要一个 n x n 的矩阵来存储结果，因此空间复杂度为 O(n²)。

代码

class Solution {public int[][] generateMatrix(int n) {// 初始化一个 n x n 的矩阵int[][] ans = new int[n][n];// sum 用来记录当前填充的数字，初始为 1int sum = 1;// row 和 column 用来记录当前要填充的位置的行和列int row = 0, column = 0;// 只要 n > 0，就继续填充while (n > 0) {// 1. 从左到右填充当前的北边界for (int i = 0; i < n; i++) {ans[row][column++] = sum++;  // 填充当前元素，并将列加 1}// 向左回退一列，因为 column++ 会使列超出范围column -= 1;// 2. 从上到下填充当前的东边界for (int i = 0; i < n - 1; i++) {ans[++row][column] = sum++;  // 填充当前元素，并将行加 1}// 3. 从右到左填充当前的南边界for (int i = n - 2; i >= 0; i--) {ans[row][--column] = sum++;  // 填充当前元素，并将列减 1}// 4. 从下到上填充当前的西边界for (int i = n - 2; i > 0; i--) {ans[--row][column] = sum++;  // 填充当前元素，并将行减 1}// 回到上边界的下一列，并且减少矩阵的规模（边界收缩）column++;n -= 2;  // 每一圈填充完成后，矩阵的有效边长减少 2}// 返回生成的矩阵return ans;}
}