leetcode 59. 螺旋矩阵 II

大耗子 2021年02月20日 19次浏览

题目: 59. 螺旋矩阵 II

59. 螺旋矩阵 II

难度中等300收藏分享切换为英文接收动态反馈

给你一个正整数 n ,生成一个包含 1n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

示例 1:

img

输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]

示例 2:

输入:n = 1
输出:[[1]]

提示:

  • 1 <= n <= 20

解题思路

首先初始化ans数组大小。

设置一个visit数组,代表是否走过该位置。

然后通过模拟行走的过程来完成数组的复制。

只要遇到边界或者遇到visit位置有置为1,说明该拐弯了,那么d = (d+1)%4;

代码

int directions[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
		vector<vector<int>> ans;
		vector<vector<int>> visit;
		if (n == 0) return ans;
		initVec(ans,n,n);
		visit = ans;
		int d = 0;
		int row = 0, col = 0;
		for (int i = 0; i < n * n; i++)
		{
			ans[row][col] = i + 1;
			visit[row][col] = 1;
			int nextRow = row + directions[d][0];
			int nextCol = col + directions[d][1];
			if(nextRow >= n || nextRow < 0 || nextCol >= n || nextCol < 0 || visit[nextRow][nextCol])
				d = (d + 1) % 4;
			row += directions[d][0];
			col += directions[d][1];


		}
		return ans;
	}
	void initVec(vector<vector<int>> &vec, int row, int col) {
		vector<int> tmp;
		tmp.resize(col);
		for (int i = 0; i < row; i++)
		{
			vec.push_back(tmp);
		}
	}
	
};


int main() {
	vector<vector<int>> ans;
	Solution sln;
	ans = sln.generateMatrix(2);
	printVecVev(ans);
}