29
03/2015
[LeetCode] Spiral Matrix
Spiral Matrix
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].
解题思路：
分析题，没有什么难度，注意防止重复读取。读了“7”字形之后要判断。下面是代码：
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 | class Solution {public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> result; int rows = matrix.size(); if(rows == 0){ return result; } int cols = matrix[0].size(); if(cols == 0){ return result; } int rowsRead = 0; int colsRead = 0; while(rowsRead<(rows+1)/2 && colsRead<(cols + 1)/2){ //输出上层边 for(int i = colsRead; i < cols - colsRead; i++){ result.push_back(matrix[rowsRead][i]); } //输出最右边 for(int i = rowsRead + 1; i < rows - rowsRead; i++){ result.push_back(matrix[i][cols - colsRead - 1]); } //若行数为奇数，并读到了中间一行，退出 if((rowsRead + 1)*2 > rows){ break; } //若列数为奇数，且读到了中间一列，跳出 if((colsRead + 1)*2 > cols){ break; } //输出最低边 for(int i = cols - colsRead - 2; i>=colsRead; i--){ result.push_back(matrix[rows - rowsRead - 1][i]); } //输出最左边 for(int i = rows - rowsRead - 2; i>=rowsRead+1;i--){ result.push_back(matrix[i][colsRead]); } rowsRead++; colsRead++; } return result; }}; |
二次刷题（update in 2015-07-29）
同样在“7”字形之后忘记判断了，导致重复读取。这里之用一个变量：layer表示目前读那一层。
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 | class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> result; int m = matrix.size(); if(m==0){ return result; } int n = matrix[0].size(); if(n==0){ return result; } int layer = 0; //已经读取的层次 while(result.size() < m * n){ //读取北边 for(int i=layer; i<n-layer; i++){ result.push_back(matrix[layer][i]); } //读取东边，注意读北边的时候将最上边的那个读取了 for(int i=layer + 1; i<m-layer; i++){ result.push_back(matrix[i][n - 1 - layer]); } if(result.size() >= m * n){ break; } //读取南边，注意读东边的时候最右边那个已经读取了 for(int i=n - 1 - layer - 1; i>=layer; i--){ result.push_back(matrix[m - 1 - layer][i]); } //读取西边，注意读取北边和南边的时候，最上边和最下边的那个已经读取了 for(int i=m - 1 - layer - 1; i>layer; i--){ result.push_back(matrix[i][layer]); } layer++; } return result; }}; |
转载请注明：康瑞部落 » [LeetCode] Spiral Matrix
0 条评论