## Sunday, November 23, 2014

### [LeetCode] Spiral Matrix I, II

Spiral Matrix I
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
```[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
```
You should return `[1,2,3,6,9,8,7,4,5]`.

Spiral Matrix II

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 ]
]```

1. m和n可以不同，所以对于第i层来说，最后一行为lastRow = m-1-i，而最后一列为lastCol = n-1-i。所以层数由min(m,n)决定。
2. 当min(m,n)为奇数时，最后一层为一行或一列，需要特殊处理。

 ``` 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``` ```class Solution { public: vector spiralOrder(vector > &matrix) { vector ret; if(matrix.empty() || matrix[0].empty()) return ret; int m = matrix.size(), n = matrix[0].size(); int nlvl = (min(m,n)+1)/2; for(int i=0; ii; j--) ret.push_back(matrix[lastRow][j]); for(int j=lastRow; j>i; j--) ret.push_back(matrix[j][i]); } } return ret; } }; ```

II比I简单，一样的按层访问法。由于是正方形矩阵，当n为奇数时，最后只会剩下一个数字即matrix[n/2][n/2]，最后不要忘记补填上这个数字。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21``` ```class Solution { public: vector > generateMatrix(int n) { vector> ret(n,vector(n,0)); int nlvl = n/2; int val = 1; for(int i=0; ii; j--) ret[last][j] = val++; for(int j=last; j>i; j--) ret[j][i] = val++; } if(n%2==1) ret[n/2][n/2] = val; return ret; } }; ```