59.Spiral Matrix II

59.Spiral Matrix II

难度:Medium

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

Example:

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

从起点位置开始,一次连续放置数字,到头了或者前面的数字已经被放过了,则开始转向。建立一个方向向量,每次到头换一次,知道所有的n*n个数被放满。

class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n,vector<int>(n,0));
res[0][0]=1;
// if(n==1) return res;
int cur=2;
vector<vector<int>> direct={{0,1}, {1,0},{0,-1}, {-1,0}};
vector<int > start = {0,0};
vector<int> p=direct[0];
int pr=0;
int N=n*n;
while(cur<=N)
{
int indx = start[0]+p[0] ;
int indy = start[1]+p[1] ;
// cout<<cur<<" "<< start[0]+p[0] << " "<<start[1]+p[1]<<endl;
if(indx<0 || indx >=n || indy <0 || indy >=n || res[indx][indy] )
{
pr = (pr+1)%4;
p = direct[pr];
}
else
{
res[indx][indy] =cur++;
start[0]=indx;
start[1] = indy;
}
}
return res;
}
};

执行用时 :8 ms, 在所有 C++ 提交中击败了68.59%的用户 内存消耗 :9 MB, 在所有 C++ 提交中击败了42.07%的用户