59. 螺旋矩阵 II
题目描述
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路
顺时针画矩阵的过程，用文字描述有：
1）从左到右，填充上行；
2）从上到下，填充右列；
3）从右到左，填充下行；
4）从下到上，填充左列；
四个为一圈往里层画。
这个操作不涉及知名算法，主要是考验代码边界条件的把控能力。
实现并不难，但一次就过占少数，大部分人都需要输出每一个步骤后的矩阵状态来调试，细调边界条件。
修修补补版代码
根据描述，第 1）横着填充完后，执行 2）时会发现已经被 1）中填充了；
为了不重复填充，每个步骤之后都要矫正位置；
len：值为 n^2 表示主循环的边界；
num：从1到n^2的计数 resv[i][j] 填入值；
il：i 的左边界，每次操作后边界需要缩小范围；
ir：i 的右边界，每次操作后边界需要缩小范围；
jl：j 的左边界，每次操作后边界需要缩小范围；
jr：j 的右边界，每次操作后边界需要缩小范围；
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> resv(n,vector<int>(n));
if( n == 0 )
return resv;
int len = n*n;
int i=0, j=0, num = 1;
int il=1, ir=n-1, jl=0, jr=n-1;
while( num <= len )
{
while( j <= jr )
{
resv[i][j++] = num++;
if( num > len )
return resv;
}
j=jr--; //边界缩小范围
i++; //矫正位置
while( i <= ir )
{
resv[i++][j] = num++;
if( num > len )
return resv;
}
i=ir--;
j--;
while( j >= jl )
{
resv[i][j--] = num++;
if( num > len )
return resv;
}
j=jl++;
i--;
while( i >= il )
{
resv[i--][j] = num++;
if( num > len )
return resv;
}
i=il++;
j++;
}
return resv;
}
};重理思路
一圈有四条边，每条边都保持左闭右开的原则
n=3为例，有下图：
n=4为例，有下图：
优化版
loop：循环圈数，如上图n=3，循环一圈，最后填充中心位置；
mid：当n为基数时，中心位置 resv[mid][mid] 直接填写，不需要再循环；
count：从1到n^2的计数 resv[i][j] 填入值；
len：每次循环边的长度，保证边的左闭右开原则，初始值为n-1；一次循环之后边长应该减2，因为左右两侧各已填写；
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> resv(n,vector<int>(n));
int loop = n/2;
int mid = n/2;
int count = 1;
int starti = 0, startj = 0;
int i, j, len = n-1;
while(loop--)
{
for( j=startj; j<startj+len; j++ )
resv[starti][j] = count++;
for( i=starti; i<starti+len; i++ )
resv[i][j] = count++;
for( ; j>startj; j-- )
resv[i][j] = count++;
for( ; i>starti; i-- )
resv[i][j] = count++;
len -= 2;
starti++;
startj++;
}
if(n%2)
resv[mid][mid] = count;
return resv;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-12-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
