算法刷题笔记【数组】59.螺旋矩阵II
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
模拟法
思路：要坚持循环不变量原则，模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去，每画一条边都要坚持一致的左闭右开的原则
class lc059_generateMatrix{
public:
vector<vector<int>> generateMatrix(int n) {
// 0.初始化一个n行n列的二维数组（一维：vector<int> vec(n);）
vector<vector<int>> ans(n, vector<int>(n, 0));
int round = n / 2;
int count = 1;
int startX = 0, startY = 0;
int i, j;
int offset = 1;
int mid = n / 2;
while(round--) {
i = startX;
j = startY;
for (j = startY; j < n - offset; ++j) {
ans[startX][j] = count++;
}
for (i = startX; i < n - offset; ++i) {
ans[i][j] = count++;
}
for (; j > startY; --j) {
ans[i][j] = count++;
}
for (; i > startX; --i) {
ans[i][j] = count++;
}
startX++, startY++;
offset += 1;
}
if (n % 2 == 1) {
// ans[i][j] = count;
// ans[++i][++j] = count;
ans[mid][mid] = count;
}
return ans;
}
}
小结
细节太多，想起信心满满，却不断出错，有点羞愤，又有点恼，简直打脸！
做题过程中，刚开始是`while`循环中的循环次数忘记自减导致程序死循环，尴尬！
关于**最后一个元素**的处理，一开始想着`i`和`j`最终会移动到中间位置，就直接使用`ans[i][j] = count;`加上测试时用`3`作为数组阶数，一运行，发现最后一个数是`0`，而且`i`和`j`都为`0`，给我整不会了，甚至怀疑作用域有问题。后来才发现，`i`和`j`在最后一个元素的前一个位置，一般情况下是在其左边。好，那在赋值的时候先自增一下不就好了？`ans[++i][++j] = count;`，给个`5`跑一下，正确！美滋滋 ~ 提交！执行错误！懵了，一看发现是输入为`1`的时候结果错了。凸(艹皿艹 )，原来，为`1`的时候，`ans[++i][++j] = count;`不就越界了嘛！好了，还是老老实实用一个单独的变量来表示最中间的那个值好了。`int mid = n / 2; ans[mid][mid] = count;`
附录
给出完整的可运行的程序清单
.h和.cpp文件
/**********************************************************
> FilePath: lc059_generateMatrix.h
> Author: @leon-ais
> Mail: leon-ais@qq.com
> Date: 9/26/2022 9:19 AM
> Description: 59.螺旋矩阵II
***********************************************************/
#ifndef C_TUTORIAL_LC059_GENERATEMATRIX_H
#define C_TUTORIAL_LC059_GENERATEMATRIX_H
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class lc059_generateMatrix{
public:
vector<vector<int>> generateMatrix(int n) {
// 0.初始化一个n行n列的二维数组（一维：vector<int> vec(n);）
vector<vector<int>> ans(n, vector<int>(n, 0));
int round = n / 2;
int count = 1;
int startX = 0, startY = 0;
int i, j;
int offset = 1;
int mid = n / 2;
while(round--) {
i = startX;
j = startY;
for (j = startY; j < n - offset; ++j) {
ans[startX][j] = count++;
}
for (i = startX; i < n - offset; ++i) {
ans[i][j] = count++;
}
for (; j > startY; --j) {
ans[i][j] = count++;
}
for (; i > startX; --i) {
ans[i][j] = count++;
}
startX++, startY++;
offset += 1;
}
if (n % 2 == 1) {
// ans[i][j] = count;
// ans[++i][++j] = count;
ans[mid][mid] = count;
}
return ans;
}
void print2Darr(vector<vector<int>> a) {
int m = a.size(), n = a[0].size();
// 2.美化打印一个二维数组
cout << "ans=[";
for (int i = 0; i < m; ++i) {
cout << endl;
cout << ((i == 0) ? "[" : ", [");
for (int j = 0; j < n; ++j) {
cout << ((j == 0) ? "" : ", ") << a[i][j];
}
cout << "]";
}
cout << "]" << endl;
}
vector<vector<int>> matrixTest(int n) {
// 0.使用vector初始化一个n * n数组
vector<vector<int>> ans(n, vector<int>(n, 0));
// 1.双层for循环给二维数组赋值
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ans[i][j] = count++;
}
}
// 2.美化打印一个二维数组
cout << "ans=[";
for (int i = 0; i < n; ++i) {
cout << endl;
cout << ((i == 0) ? "[" : ", [");
for (int j = 0; j < n; ++j) {
cout << ((j == 0) ? "" : ", ") << ans[i][j];
}
cout << "]";
}
cout << "]" << endl;
return ans;
}
};
#endif //C_TUTORIAL_LC059_GENERATEMATRIX_H
/**********************************************************
> FilePath: lc059_generateMatrix.cpp
> Author: @leon-ais
> Mail: leon-ais@qq.com
> Date: 9/26/2022 9:19 AM
> Description: 59.螺旋矩阵II
***********************************************************/
#include "lc059_generateMatrix.h"
void init_test() {
lc059_generateMatrix matrix;
matrix.matrixTest(9);
int n = 9;
vector<vector<int>> a(n);
vector<vector<int>> c(n, vector<int>(n, 1));
vector<vector<int>> b(n, vector<int>(n, 0));
matrix.print2Darr(a);
}
int main() {
lc059_generateMatrix matrix;
vector<vector<int>> b = matrix.generateMatrix(1);
matrix.print2Darr(b);
return 0;
}
完事~
