【LeetCode】螺旋矩阵 I II III IV

大家好，欢迎来到IT知识分享网。

目录

1. 螺旋矩阵

2. 螺旋矩阵 II

3. 螺旋矩阵 III

4. 螺旋矩阵 IV

1. 螺旋矩阵

题目描述：

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

提示：

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

题解：

4×5的矩阵按顺时针螺旋顺序打印如图所示。

• 每次从左往右走，都是从left走向right，结束后up++

• 每次从上往下走，都是从up走向down，结束后right–

• 每次从右往左走，都是从right走向left，结束后down–

• 每次从下往上走，都是从down走向up，结束后left++

所以，螺旋矩阵每次循环分为4步；左→右、上→下、右→左、下→上，直到up>down或left>right跳出循环。

class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> ans; int m = matrix.size(); // 行 int n = matrix[0].size(); // 列 int up = 0; // 上边界 int down = m - 1; // 下边界 int left = 0; // 左边界 int right = n - 1; // 右边界 while (1) { // 左→右 for (int j = left; j <= right; j++) { ans.push_back(matrix[up][j]); } if (++up > down) { break; } // 上→下 for (int i = up; i <= down; i++) { ans.push_back(matrix[i][right]); } if (--right < left) { break; } // 右→左 for (int j = right; j >= left; j--) { ans.push_back(matrix[down][j]); } if (--down < up) { break; } // 下→上 for (int i = down; i >= up; i--) { ans.push_back(matrix[i][left]); } if (++left > right) { break; } } return ans; } };

测试：

int main() { vector<vector<int>> matrix = { {1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20} }; vector<int> v = Solution().spiralOrder(matrix); for (auto e : v) { cout << e << " "; } cout << endl; return 0; }

2. 螺旋矩阵 II

题目描述：

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

提示：

• 1 <= n <= 20

题解：

class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> ans(n, vector<int>(n)); // n*n的二维数组 int up = 0; // 上边界 int down = n - 1; // 下边界 int left = 0; // 左边界 int right = n - 1; // 右边界 int num = 1; // 顺时针递增的矩阵元素 while (1) { // 左→右 for (int j = left; j <= right; j++) { ans[up][j] = num++; } if (++up > down) { break; } // 上→下 for (int i = up; i <= down; i++) { ans[i][right] = num++; } if (--right < left) { break; } // 右→左 for (int j = right; j >= left; j--) { ans[down][j] = num++; } if (--down < up) { break; } // 下→上 for (int i = down; i >= up; i--) { ans[i][left] = num++; } if (++left > right) { break; } } return ans; } };

测试：

int main() { vector<vector<int>> v = Solution().generateMatrix(10); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%3d ", v[i][j]); } printf("\n"); } return 0; }

3. 螺旋矩阵 III

题目描述：

在rows x cols的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有rows x cols个空间。

按照访问顺序返回表示网格位置的坐标列表。

提示：

• 1 <= rows, cols <= 100
• 0 <= rStart < rows
• 0 <= cStart < cols

题解：

以下图矩阵为例：

假设初始坐标为(rStart, cStart)，上边界为rStart-1，下边界为rStart+1，左边界为cStart-1，右边界为Start+1。

假设当前坐标为(x, y)。

• 每次从左往右走，都是从(x, y+1)走向(x, right)，结束后right++

• 每次从上往下走，都是从(x+1, y)走向(down, y)，结束后down++

• 每次从右往左走，都是从(x, y-1)走向(x, left)，结束后left–

• 每次从下往上走，都是从(x-1, y)走向(up, y)，结束后up–

重复循环左→右、上→下、右→左、下→上，当答案数组的元素个数==网格面积时，表示已遍历完网格的全部元素。

class Solution { public: vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) { vector<vector<int>> ans{ { rStart,cStart } }; // 先把起点存入答案数组 int count = 1; // 表示答案数组的元素个数 int up = rStart - 1; // 上边界 int down = rStart + 1; // 下边界 int left = cStart - 1; // 左边界 int right = cStart + 1; // 右边界 int x = rStart; // 当前位置横坐标 int y = cStart; // 当前位置纵坐标 int area = rows * cols; // 网格面积，即所有元素的个数 if (area == 1) { return ans; } while (1) { // 左→右 for (int j = y + 1; j <= right; j++) { // 检查坐标是否在网格中 if (x >= 0 && x < rows && j >= 0 && j < cols) { ans.push_back({ x,j }); if (++count == area) { return ans; } } } y = right; // 更新当前位置纵坐标 right++; // 上→下 for (int i = x + 1; i <= down; i++) { // 检查坐标是否在网格中 if (i >= 0 && i < rows && y >= 0 && y < cols) { ans.push_back({ i,y }); if (++count == area) { return ans; } } } x = down; // 更新当前位置横坐标 down++; // 右→左 for (int j = y - 1; j >= left; j--) { // 检查坐标是否在网格中 if (x >= 0 && x < rows && j >= 0 && j < cols) { ans.push_back({ x,j }); if (++count == area) { return ans; } } } y = left; // 更新当前位置纵坐标 left--; // 下→上 for (int i = x - 1; i >= up; i--) { // 检查坐标是否在网格中 if (i >= 0 && i < rows && y >= 0 && y < cols) { ans.push_back({ i,y }); if (++count == area) { return ans; } } } x = up; // 更新当前位置横坐标 up--; } } };

测试：

int main() { vector<vector<int>> v = Solution().spiralMatrixIII(4, 5, 1, 3); for (int i = 0; i < v.size(); i++) { for (int j = 0; j < v[0].size(); j++) { cout << v[i][j] << " "; } cout << endl; } return 0; }

4. 螺旋矩阵 IV

题目描述：

给你两个整数：m和n，表示矩阵的维数。

另给你一个整数链表的头节点head。

请你生成一个大小为m x n的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵左上角开始、顺时针按螺旋顺序填充。如果还存在剩余的空格，则用-1填充。

返回生成的矩阵。

提示：

• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 链表中节点数目在范围[1, m * n] 内
• 0 <= Node.val <= 1000

题解：

class Solution { public: vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) { vector<vector<int>> ans(m, vector<int>(n, -1)); // m*n的二维数组，全部初始化为-1 int up = 0; // 上边界 int down = m - 1; // 下边界 int left = 0; // 左边界 int right = n - 1; // 右边界 ListNode* cur = head; while (1) { // 左→右 for (int j = left; j <= right; j++) { if (cur == nullptr) { return ans; } ans[up][j] = cur->val; cur = cur->next; } if (++up > down) { break; } // 上→下 for (int i = up; i <= down; i++) { if (cur == nullptr) { return ans; } ans[i][right] = cur->val; cur = cur->next; } if (--right < left) { break; } // 右→左 for (int j = right; j >= left; j--) { if (cur == nullptr) { return ans; } ans[down][j] = cur->val; cur = cur->next; } if (--down < up) { break; } // 下→上 for (int i = down; i >= up; i--) { if (cur == nullptr) { return ans; } ans[i][left] = cur->val; cur = cur->next; } if (++left > right) { break; } } return ans; } };

测试：

int main() { ListNode* preHead = new ListNode; ListNode* tail = preHead; for (int i = 3; i <= 15; i++) { ListNode* newNode = new ListNode(i); tail->next = newNode; tail = tail->next; } vector<vector<int>> v = Solution().spiralMatrix(3, 5, preHead->next); for (int i = 0; i < v.size(); i++) { for (int j = 0; j < v[0].size(); j++) { printf("%2d ", v[i][j]); } printf("\n"); } return 0; }