-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path059.SpiralMatrixII.cpp
More file actions
118 lines (103 loc) · 2.92 KB
/
059.SpiralMatrixII.cpp
File metadata and controls
118 lines (103 loc) · 2.92 KB
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/*Question:
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
SP: 54
*/
/*思路:
思路一:
直接按照54的存储matrix的值。
思路二:
该题目中的数组是n*n的，所以可以利用这一特性来改变访问数组元素的方法。
*/
//Code:
//Code 1:
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int> > result(n, vector<int>(n));
int begRow = 0;
int endRow = n - 1;
int begCol = 0;
int endCol = n - 1;
int count = 1;
while(begRow <= endRow && begCol <= endCol)
{
//left->right
if(begRow <= endRow)
{
for(int i = begCol; i <= endCol; ++i, ++count)
result[begRow][i] = count;
++begRow;
}
//up->down
if(begCol <= endCol)
{
for(int i = begRow; i <= endRow; ++i, ++count)
result[i][endCol] = count;
--endCol;
}
//right->left
if(begRow <= endRow)
{
for(int i = endCol; i >= begCol; --i, ++count)
result[endRow][i] = count;
--endRow;
}
//down->up
if(begCol <= endCol)
{
for(int i = endRow; i >= begRow; --i, ++count)
result[i][begCol] = count;
++begCol;
}
}
return result;
}
};
//Code 2:
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int> > result(n, vector<int>(n));
for(int k = 0, num = 1, count = (n+1)/2; k < count; ++k)
{
int iEnd = n - k * 2;
//left->right
for(int i = 0; i < iEnd; ++i )
result[k][k+i] = num++;
//up->down
for(int i = 1; i < iEnd; ++i)
result[k+i][n-k-1] = num++;
//right->left
for(int i = 1; i < iEnd; ++i)
result[n-k-1][n-k-i-1] = num++;
//down->up
--iEnd;
for(int i = 1; i < iEnd; ++i)
result[n-k-i-1][k] = num++;
}
return result;
}
};
//Code 3:
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int> > mat(n, vector<int>(n));
int r = 0, c = -1, x = 1;
const int g[5] = { 0, 1, 0, -1, 0 };
for (int b = 0, i = 0; n > 0; n -= (b ^= 1), i = (++i % 4)) {
for (int s = 0; s < n; s++) {
mat[r += g[i]][c += g[i+1]] = x++;
}
}
return mat;
}
};