Spiral Matrix II
没什么好说的, 旋转填充N宫格
my solution (4ms)
可以用一个 while + 4个for 来做, 这样是最直观, 最好理解的
但是不太想这样, 感觉太丑陋了… 所以想了一下办法在一个循环中实现它
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ret( n, vector<int>(n, 0) );
vector<vector<int>> step { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
int type = 0, count = 0, xstep = 0, ystep = 0;;
for (int nums = 1, end = n * n; nums <= end; ) {
ret[ystep][xstep] = nums++;
xstep += step[type][0];
ystep += step[type][1];
count = ++count >= (n - 1) ? count - n + 1 : count;
if (count == 0) {
type = ++type % 4;
if (type == 0) {
n -= 2;
xstep += 1;
ystep += 1;
}
}
}
return ret;
}
};
|
前进有4个方向, 每次的位移是一定的, 而且是按照循环来做位移
所以用了取余和数组来确定每一次的位移是正确的
然后是将每个方向的步数看做同一个值, 所以求取步数在之前
比如 n = 3:
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
则是按照 1, 2 3, 4 … ( (4 * n - 1) )这样的概念来前进, 但是问题在于
如果将计算步数的操作放到了最后, 那么 3 就会被错误计算, 所以保存了一下最后一次越界前的值
(我隐约感觉这里应该能够优化, 毕竟这样写出来的代码不易理解)
结果没什么好说的
the best solution (4ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int> > result(n,vector<int>(n));
if(n==0)
{
return result;
}
if(n==1)
{
result[0][0] = n;
return result;
}
int top = 0;
int bottom = n-1;
int left = 0;
int right = n-1;
long index = 1;
while(top<=bottom)
{
for(int i=left;i<=right;i++)
{
result[top][i]=index;
index++;
}
for(int i=top+1;i<bottom;i++)
{
result[i][right]=index;
index++;
}
if(top<bottom)
{
for(int i=right;i>=left;i--)
{
result[bottom][i]=index;
index++;
}
}
if(left<right)
{
for(int i=bottom-1;i>top;i--)
{
result[i][left]=index;
index++;
}
}
left++;
right--;
top++;
bottom--;
}
return result;
}
};
|
我不喜欢丑陋的 while for for for for :( , 就不分析了