学习笔记二 螺旋矩阵旋起来
本题来自：力扣59.螺旋矩阵2.
题目解读
螺旋矩阵问题是面试常考问题之一，通过编程来模拟过程可以有效检验出应试者对代码的掌控能力，以及对边界条件的清晰认识。
对于这个问题，切记不要一上来就沉浸于代码中。
事实上，这道题只要理清了思路，每一部分的代码写起来是大同小异的。
下面来看具体思路：
思路一：模拟一个完整的loop
一个完整的圈由四条边组成，那么处理相邻两条边的交点便是关键，到底应该将交点分配给哪一条边呢？
无论是左开右闭还是左闭右开都是可以的，只要选择使用一种即可。
很多同学没有想明白问题，一会左闭右开，一会左闭右闭，很快就把自己绕了进去。
这里我们推荐一直使用左闭右开的方式，对每条边都以左闭右开的方式去遍历。
示意图
以上图为例，不同颜色表示一个边的遍历方式。
下面我们来看具体实现：
变量的定义
- 第一组变量是定义每一圈的起始位置
int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
- 第二组变量是圈的循环次数
int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
- 第三组变量是赋值变量，由于螺旋矩阵数值是依次递增的，于是用 count++ 为其赋值
int count = 1; // 用来给矩阵赋值
- 第四组变量是用来控制每个圈边长的长度，由于每遍历一圈，未赋值部分长宽都会缩小2，因此用它来记录已赋值部分的厚度。
int offset = 1; // 每一圈循环，需要控制每一条边遍历的长度
- 第五组全局变量用来进行 for 循环，不做解释。
int i,j;
循环的组成
代码部分有详细注释，结合上方定义的变量食用更佳~
while (loop --) {
i = startx;
j = starty;
// 下面开始的四个for就是模拟转了一圈
// 模拟填充上行从左到右(左闭右开)
for (j = starty; j < starty + n - offset; j++) {
res[startx][j] = count++;
}
// 模拟填充右列从上到下(左闭右开)
for (i = startx; i < startx + n - offset; i++) {
res[i][j] = count++;
}
// 模拟填充下行从右到左(左闭右开)
for (; j > starty; j--) {
res[i][j] = count++;
}
// 模拟填充左列从下到上(左闭右开)
for (; i > startx; i--) {
res[i][j] = count++;
}
// 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
startx++;
starty++;
// offset 控制每一圈里每一条边遍历的长度
offset += 2;
}
特殊情况的判断
- 额外要注意的一点是：如果矩阵边长 n 是奇数，需要给矩阵中心一个点单独赋值，因为它无法成完整的圈。
// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
if (n % 2) {
int mid = n / 2;
res[mid][mid] = count;
}
完整代码
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
int count = 1; // 用来给矩阵中每一个空格赋值
int offset = 1; // 每一圈循环，需要控制每一条边遍历的长度
int i,j;
while (loop --) {
i = startx;
j = starty;
// 下面开始的四个for就是模拟转了一圈
// 模拟填充上行从左到右(左闭右开)
for (j = starty; j < starty + n - offset; j++) {
res[startx][j] = count++;
}
// 模拟填充右列从上到下(左闭右开)
for (i = startx; i < startx + n - offset; i++) {
res[i][j] = count++;
}
// 模拟填充下行从右到左(左闭右开)
for (; j > starty; j--) {
res[i][j] = count++;
}
// 模拟填充左列从下到上(左闭右开)
for (; i > startx; i--) {
res[i][j] = count++;
}
// 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
startx++;
starty++;
// offset 控制每一圈里每一条边遍历的长度
offset += 2;
}
// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
if (n % 2) {
res[mid][mid] = count;
}
return res;
}
};
思路二：渐缩边界（通用解法！）
这个解法更加简单易懂，强烈建议掌握！、
变量的定义
- 第一组变量，矩阵的四个边界
int left = 0, right = n - 1, top = 0, bottom = n - 1;
- 第二组变量，赋值变量 count
int count = 1;
循环的组成
- 这里的循环结束条件是：（好处：不用考虑特殊情况！！！）
while (count <= n * n) //count = n * n 时说明矩阵所有位置均已赋值
- 而循环的关键在于 渐缩！ 这里以一重 for 循环为例：
for (int i = left; i <= right; i++) {
ans[top][i] = count++;
}
++top; // 一重for循环结束后渐缩
完整代码
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int left = 0, right = n - 1, top = 0, bottom = n - 1;
int count = 1;
vector<vector<int>> ans(n, vector<int>(n));
while (count <= n * n) {
for (int i = left; i <= right; i++) {
ans[top][i] = count++;
}
++top;
for (int i = top; i <= bottom; i++) {
ans[i][right] = count++;
}
--right;
for (int i = right; i >= left; i--) {
ans[bottom][i] = count++;
}
--bottom;
for (int i = bottom; i >= top; i--) {
ans[i][left] = count++;
}
++left;
}
return ans;
}
};
相似题目
力扣54.螺旋矩阵.
此题由上面的正方形扩展到了长方形，但整体思路大同小异，大家可以拿来练手~
