题目
59 螺旋矩阵II
给你一个正整数 n ,生成一个包含 1 到n2
所有元素,且元素按顺时针顺序螺旋排列的n x n
正方形矩阵。
示例 1:
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]
思路
首先分析清楚顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去。每完成一圈需要画上下左右四条边,并且下一圈时需要将四个边界缩小。
因此我们用代码将这个过程模拟出来(即模拟法):
- 首先确定总循环是从1到
n*n
- 定义上下左右四个边界,按图中看初始值为
left =0, right = n -1, top =0, bottom = n -1;
- 当
value <= n*n
时,始终按照 从左到右 从上到下 从右到左 从下到上(模拟的主过程)填入顺序循环,每次填入后:- value++,得到下一个要填入的值
- 根据当前填充的是哪一条边界,相应的修改边界的值,缩小边界(top和left需要+1,right和bottom需要减1)
class Solution
{
public:
vector<vector<int>> generateMatrix(int n)
{
vector<vector<int>> result(n, vector<int>(n, 0));
int value = 1;
int maxValue = n * n;
int left = 0, right = n - 1, top = 0, bottom = n - 1;
while (value <= maxValue)
{
//从左到右填充上边界
for (int i = left; i <= right; i++)
result[top][i] = value++;
top++;
//从上到下填充右边界
for (int i = top; i <= bottom; i++)
result[i][right] = value++;
right--;
//从右到左填充下边界
for (int i = right; i >= left; i--)
result[bottom][i] = value++;
bottom--;
//从下到上填充左边界
for (int i = bottom; i >= top; i--)
result[i][left] = value++;
left++;
}
return result;
}
};