首页 > 代码库 > Leetcode:Spiral Matrix 螺旋矩阵
Leetcode:Spiral Matrix 螺旋矩阵
Spiral Matrix：
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]
You should return [1,2,3,6,9,8,7,4,5].
解题分析：
这题就是 边界情况非常复杂
实际上就是 从外圈到内圈依次打印矩阵中的每一个圈
假设这个矩阵的行数为nRows，列数为nCols，我们每次从一个圈的左上角开始处理
设这个开始角坐标为 startX和startY(注意是坐标系中的坐标，不是矩阵中行列下标，因为矩阵A[i][j]对应着横坐标为j，纵坐标为i)
每处理一圈之后，下一圈的行列数分别减2，所以对于 startX和startY的循环终止应该是：nRows > 2 * startX && nCols > 2 * startY
我们计算出每次循环中的当前圈的长度rowLen和宽度colLen，并且计算出横坐标的最大值和纵坐标的最大值
然后分四步处理每一圈：
1. 从左往右，打印上边一行，这时候是没有if语句判断的，因为无论如何至少可以前进一步
2. 从上往下，打印右边一列，这时候需要 endY > startY，也就是矩形宽度>=2, 如果endY == startY，表示只有一行，没有列元素打印.注意i=startY +1开始
3. 从右往左，打印下边一行，这时候需要 endX > startX && endY > startY，也就是小矩形长度和宽度都必须>=2，注意i=endX - 1开始
长度>=2确保可以从右往左开始打印，宽度>=2确保存在下边这一行
4. 从下往上，打印左边一列，这时候需要 endX > startX && endY > startY，即当前小矩形至少有2行2列，注意i = endY - 1开始，并且 i >= startY - 1(防止重复打印)
class Solution {public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> result; int nRows = matrix.size(); if (nRows == 0) return result; int nCols = matrix.at(0).size(); result.reserve(nRows * nCols); int startX = 0; int startY = 0; while (nRows > 2 * startX && nCols > 2 * startY) { PrintNumbers(matrix, startX, startY, result); ++startX; ++startY; } return result; } void PrintNumbers(vector<vector<int>>& matrix, int startX, int startY, vector<int>& result) { assert(startX >= 0 && startY >= 0); int nRows = matrix.size(); int nCols = matrix.at(0).size(); int rowLen = nRows - 2 * startX; // 当前矩形的长度 int colLen = nCols - 2 * startY; // 当前矩形的宽度 int endX = startX + colLen - 1; // endX - startX + 1 = colLen X为横坐标 int endY = startY + rowLen - 1; // endY - startY + 1 = rowLen Y为纵坐标 // 1. 从左往右 for (int i = startX; i <= endX; ++i) { result.push_back(matrix.at(startY).at(i)); } // 2. 从上往下 if (endY > startY) { for (int i = startY + 1; i <= endY; ++i) { result.push_back(matrix.at(i).at(endX)); } } // 3. 从右往左 if (endX > startX && endY > startY) { for (int i = endX - 1; i >= startX; --i) { result.push_back(matrix.at(endY).at(i)); } } // 4. 从下往上 if (endX > startX && endY > startY) { for (int i = endY - 1; i >= startY + 1; --i) { result.push_back(matrix.at(i).at(startX)); } } }};
Spiral Matrix II：
Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]
解题分析：
我们解决了上一题，这一题就很轻松了，而且题目中说明始终是一个方阵，所以 行和列数相等，startX == startY， endX == endY
直接按照打印的顺序填充矩阵即可
class Solution {public: vector<vector<int> > generateMatrix(int n) { assert(n >= 0); vector<vector<int>> result(n, vector<int>(n, 0)); int val = 1; int start = 0; for (int start = 0; start * 2 < n; ++start) { int len = n - 2 * start; int end = start + len - 1; // 1. 从左往右 for (int i = start; i <= end; ++i) { result.at(start).at(i) = val++; } // 2. 从上往下 if (end > start) { for (int i = start + 1; i <= end; ++i) { result.at(i).at(end) = val++; } } // 3. 从右往左 if (end > start) { for (int i = end - 1; i >= start; --i) { result.at(end).at(i) = val++; } } // 4. 从下往上 if (end > start) { for (int i = end - 1; i >= start + 1; --i) { result.at(i).at(start) = val++; } } } return result; }};