[LeetCode]Spiral Matrix II

可以用和Spiral Matrix一样的解法。这里我们写另外一种，模拟其螺旋遍历的方式，到了对应的节点我们转对应的方向，时间复杂度O(n)，常熟空间，代码如下：

	class Solution {
	public:
	vector<vector<int>> generateMatrix(int n) {
	vector<vector<int>> matrix(n, vector<int>(n));
	vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
	int curr = 1, layers = (n + 1) / 2;
	for(int k = 0; k < layers; ++k)
	{
	int i = k, j = k, count = 0;
	while(count < 4 * (n - 2 * k - 1))
	{
	matrix[i][j] = curr++;
	auto dir = dirs[count / (n - 2 * k - 1)];
	i += dir.first;
	j += dir.second;
	++count;
	}
	//If layer numbers is odd, we have to handle last layer specially
	if(!count)
	matrix[k][k] = curr++;
	}
	return matrix;
	}
	};

view raw Spiral Matrix II.cpp hosted with ❤ by GitHub