8000 added 119 · lccate/LeetCode-1@a9e075b · GitHub
[go: up one dir, main page]
Skip to content

Commit a9e075b

Browse files
pezypezy
committed
added 119
1 parent 3cda2b7 commit a9e075b

File tree

3 files changed

+108
-0
lines changed

3 files changed

+108
-0
lines changed

‎119. Spiral Matrix/README.md

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
m * n 的矩阵按螺旋顺序转为数组：
2+
3+
1 2 3
4+
4 5 6 --> 1 2 3 6 9 8 7 4 5
5+
7 8 9
6+
7+
我想到的是，直接用下标作为限制。m 行，n 列，即范围:
8+
9+
- row: 0 ~ m
10+
- col: 0 ~ n
11+
12+
首先是列递增，(0,0), (0,1), (0,2). 然后行递增，(1,2), (2,2). 再后是列递减，(2,1), (2,0). 和行递减，(1,0).
13+
最后进入下一螺旋：(1,1). 到此为止，全部数组都迭代出来。
14+
15+
可以发现的规律是，每一次螺旋，都按照以下顺序：
16+
17+
1. 列递增 (row 降到最低)
18+
2. 行递增 (col 增到最高)
19+
3. 列递减 (row 增到最高)
20+
4. 行递减 (col 降到最低)
21+
22+
写成 `for` 循环的形式，则为：
23+
24+
```cpp
25+
for (; nMin<mMax && nMin<nMax; --mMax, --nMax, ++mMin, ++nMin) {
26+
for (int i=nMin; i<nMax; ++i)
27+
ret.push_back(matrix[mMin][i]);
28+
for (int i=mMin+1; i<mMax; ++i)
29+
ret.push_back(matrix[i][nMax-1]);
30+
for (int i=nMax-2; i>=nMin; --i)
31+
ret.push_back(matrix[mMax-1][i]);
32+
for (int i=mMax-2; i>mMin; --i)
33+
ret.push_back(matrix[i][nMin]);
34+
}
35+
```
36+
37+
除此之外，需要增加一些边界条件判断：
38+
39+
- `n = matrix[0].size();` // 要提前判断 matrix.empty()
40+
- 第三个 `for` 循环要避免重复，如仅有一行的情况，列递增之后，没有行递增，直接就列递减了，那必然重复。判断 `mMax-1 != mMin`.
41+
- 第四个 `for` 循环同理，避免行重复，判断 `nMax-1 != nMin`.

‎119. Spiral Matrix/TEST.cc

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
#define CATCH_CONFIG_MAIN
2+
#include "../Catch/single_include/catch.hpp"
3+
#include "solution.h"
4+
5+
TEST_CASE("Spiral Matrix", "spiralOrder")
6+
{
7+
Solution s;
8+
SECTION( "Example" )
9+
{
10+
std::vector<std::vector<int>> matrix = {
11+
{1,2,3},
12+
{4,5,6},
13+
{7,8,9}
14+
15+
};
16+
std::vector<int> ret{1,2,3,6,9,8,7,4,5};
17+
REQUIRE(s.spiralOrder(matrix) == ret);
18+
}
19+
SECTION( "One line" )
20+
{
21+
std::vector<std::vector<int>> matrix = {{6,9,7}};
22+
std::vector<int> ret{6,9,7};
23+
REQUIRE(s.spiralOrder(matrix) == ret);
24+
}
25+
SECTION( "Two line" )
26+
{
27+
std::vector<std::vector<int>> matrix = {
28+
{1,2,3,4,5,6,7,8,9,10},
29+
{11,12,13,14,15,16,17,18,19,20}
30+
};
31+
std::vector<int> ret{1,2,3,4,5,6,7,8,9,10,20,19,18,17,16,15,14,13,12,11};
32+
REQUIRE(s.spiralOrder(matrix) == ret);
33+
}
34+
SECTION( "One Column" )
35+
{
36+
std::vector<std::vector<int>> matrix = {{7}, {9}, {6}};
37+
std::vector<int> ret{7,9,6};
38+
REQUIRE(s.spiralOrder(matrix) == ret);
39+
}
40+
}

‎119. Spiral Matrix/solution.h

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#include <vector>
2+
using std::vector;
3+
4+
class Solution {
5+
public:
6+
vector<int> spiralOrder(vector<vector<int> > &matrix) {
7+
vector<int> ret;
8+
if (matrix.empty()) return ret;
9+
int mMax = matrix.size();
10+
int nMax = matrix[0].size();
11+
int mMin = 0, nMin = 0;
12+
ret.reserve(mMax*nMax);
13+
for (; nMin<mMax && nMin<nMax; --mMax, --nMax, ++mMin, ++nMin) {
14+
for (int i=nMin; i<nMax; ++i)
15+
ret.push_back(matrix[mMin][i]);
16+
for (int i=mMin+1; i<mMax; ++i)
17+
ret.push_back(matrix[i][nMax-1]);
18+
if (mMax-1 == mMin) break;
19+
for (int i=nMax-2; i>=nMin; --i)
20+
ret.push_back(matrix[mMax-1][i]);
21+
if (nMax-1 == nMin) break;
22+
for (int i=mMax-2; i>mMin; --i)
23+
ret.push_back(matrix[i][nMin]);
24+
}
25+
return ret;
26+
}
27+
};

0 commit comments

Comments
 (0)
0