59. Spiral Matrix II

Given a positive integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

---

要求按螺旋方式把n阶方阵填满，和LeetCode Spiral Matrix几乎一样，而且还是方阵。直接一圈一圈填就好了。 完整代码如下：

class Solution {
public:
    vector<vector<int> > generateMatrix(int n)
    {
        vector<vector<int> > vMatrix(n, vector<int>(n, 0));
        int sx = 0, sy = 0, tx = n, ty = n, k = 1;
        while (k <= n * n) {
            for (int j = sy; j < ty; j++)
                vMatrix[sx][j] = k++;
            for (int i = sx + 1; i < tx; i++)
                vMatrix[i][ty – 1] = k++;
            for (int j = ty – 2; sx + 1 < tx && j >= sy; j–) // 满足上一个条件sx+1<tx
                vMatrix[tx – 1][j] = k++;
            for (int i = tx – 2; ty – 2 >= sy && i > sx; i–) // 满足上一个条件ty-2>=sy
                vMatrix[i][sy] = k++;
            sx++;
            sy++;
            tx–;
            ty–;
            if (sx >= tx || sy >= ty)
                break;
        }
        return vMatrix;
    }
};

本代码提交AC，用时3MS。

二刷。和LeetCode Spiral Matrix类似，更安全的方法，如下：

class Solution {
public:
    vector<vector<int> > generateMatrix(int n)
    {
        vector<vector<int> > ans(n, vector<int>(n, 0));
        int cnt = 1;
        int start_row = 0, start_col = 0, end_row = n – 1, end_col = n – 1;
        while (start_row <= end_row && start_col <= end_col) {
            for (int j = start_col; j <= end_col; ++j) {
                ans[start_row][j] = cnt++;
            }
            ++start_row;
            for (int i = start_row; i <= end_row; ++i) {
                ans[i][end_col] = cnt++;
            }
            –end_col;
            if (start_row <= end_row) {
                for (int j = end_col; j >= start_col; –j) {
                    ans[end_row][j] = cnt++;
                }
            }
            –end_row;
            if (start_col <= end_col) {
                for (int i = end_row; i >= start_row; –i) {
                    ans[i][start_col] = cnt++;
                }
            }
            ++start_col;
        }
        return ans;
    }
};

本代码提交AC，用时6MS。

三刷。朴素方法，依次填空：

class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
		vector<vector<int>> matrix(n, vector<int>(n, 0));
		int m = 0, i = 0, j = 0;
		int left = 0, right = n - 1, up = 1, down = n - 1;
		int dir = 1;// 0:left,1:right,2:up,3:down
		while (m != n * n) {
			matrix[i][j] = ++m;
			if (dir == 1) {
				if (j == right) {
					dir = 3;
					++i;
					--right;
				}
				else {
					++j;
				}
			}
			else if (dir == 3) {
				if (i == down) {
					dir = 0;
					--j;
					--down;
				}
				else {
					++i;
				}
			}
			else if (dir == 0) {
				if (j == left) {
					dir = 2;
					--i;
					++left;
				}
				else {
					--j;
				}
			}
			else if (dir == 2) {
				if (i == up) {
					dir = 1;
					++j;
					++up;
				}
				else {
					--i;
				}
			}
		}
		return matrix;
	}
};

本代码提交AC，用时0MS。