59. 螺旋矩阵 II

59. 螺旋矩阵 II

最初版本：

class Solution {
  public:
	vector<vector<int>> generateMatrix(int n)
	{
		vector<vector<int>> mat(n, vector<int>(n, 0));
		int num = 1;
		for (int layer = 1; layer <= n / 2; layer++) {
			// 每个layer分4个部分
			int x, y;
			x = layer - 1, y = layer - 1;
			for (int i = 0; i < n + 1 - 2 * layer; i++) {
				mat[x][y + i] = num++;
			}
			x = layer - 1, y = n - layer;
			for (int i = 0; i < n + 1 - 2 * layer; i++) {
				mat[x + i][y] = num++;
			}
			x = n - layer, y = n - layer;
			for (int i = 0; i < n + 1 - 2 * layer; i++) {
				mat[x][y - i] = num++;
			}
			x = n - layer, y = layer - 1;
			for (int i = 0; i < n + 1 - 2 * layer; i++) {
				mat[x - i][y] = num++;
			}
		}
		if (n % 2 == 1) {
			mat[n / 2][n / 2] = n * n;
		}
		return mat;
	}
};

看完一些题解和讲解，我依然认为我的写法最合适。改进版在这里：

完整代码

class Solution {
  public:
	vector<vector<int>> generateMatrix(int n)
	{
		vector<vector<int>> mat(n, vector<int>(n, 0));
		int num = 1;
		for (int layer = 1; layer <= n / 2; layer++) {
			// 每个layer分4个部分
			int x, y;
			int side = n + 1 - 2 * layer;
			x = layer - 1, y = layer - 1;
			for (int i = 0; i < side; i++) {
				mat[x][y + i] = num++;
			}
			x = layer - 1, y = n - layer;
			for (int i = 0; i < side; i++) {
				mat[x + i][y] = num++;
			}
			x = n - layer, y = n - layer;
			for (int i = 0; i < side; i++) {
				mat[x][y - i] = num++;
			}
			x = n - layer, y = layer - 1;
			for (int i = 0; i < side; i++) {
				mat[x - i][y] = num++;
			}
		}
		if (n % 2 == 1) {
			mat[n / 2][n / 2] = num;
		}
		return mat;
	}
};

讲解

要完成这个事情，我把螺旋的过程拆成一圈一圈，按照层级来处理。每一层又被我分解成4条线段分别处理，如图：

我把最外层叫作layer=1,layer越大越往内深入。需要执行n/2个层。如果n是奇数，会有余1,那个1就是最中心的点，待会会特殊处理。

在同一层里，有4个线段，起点就是4个角，角的坐标和layer的关系已经在图上标出。同一层的每一条边长度都相同，用side表示长度，side的计算已经在图中展示。

n为奇数的时候，中心点没处理，也不方便放进我这个四段制的处理方法。那就直接特判，发现n为奇数，就在中心点补。

这是一道模拟，难度一般，关键在于需要把这里面的过程拆解清楚。