LeetCode54 Spiral Matrix 解题报告

By | 11/03/2018

【题目】:

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

【Code】:

#include<iostream>

#include<vector>

using namespace std;

//尽管是一个二维向量,但是在进行matrix.size()的时候其实是有多少个vector<int> 的向量,其实就是有多少个每行有N个元素的元素也就是行

//如果说这个地方更不懂的话可以看一个二维向量的构造方法可能就知道了

//此处的++ or --必须放在变量的前面 因为是先改变了进行判断是否需要进行下一步 那如果是是++ or --在后面的话举 u为栗子 那么u为3的时候才无法进行

//但是当u为3的时候在if前面的for循环已经进行了一次了然而这根本是子虚乌有的因为数组越界了故为了避免这样的事情发生所以应该是先将变量的结果改变了判断一下

//再来说是不是可以进行while true下面的再一次的同一个for循环

//++ or --很重要切记不可以搞混淆了

// 实现2维数组:

// 如果一个向量的每一个元素是一个向量,则称为二维向量,例如

// vector<vector<int> >vv(3, vector<int>(4)); //这里,两个“>”间的空格是不可少的

// vector<vector<int> >vv(3, vector<int>(4)); //这里,两个“>”间的空格是不可少的

// 将构造一个二维向量vv,它含有三个元素,每个元素含有4个int型元素的向量。编译器两次调用vector的构造函数构造对象vv,第一次调用构造函数构造了一个无名的含有4个0的vector<int>对象:

// [0]  [1] [2] [3]

// 0    0   0   0

// 第二次调用构造函数,以这个无名向量为初值初始化它的三个元素,结果是:

// vv   [0] [1] [2] [3]

// [0]  0   0   0   0

// [1]  0   0   0   0

// [2]  0   0   0   0

// vv[i]表示第i(i=0,1,2)行的元素组成的向量。vv.size()的值是3,vv[1].size()的值是4.

class Solution {

public:

vector<int> spiralOrder(vector<vector<int> >& matrix) {

if(matrix.empty()){

return vector<int>();

}

// 向上的行是u,向下的行是d,向左的列是l,向右的列是r.

// k是spiral的当前索引,不断往后走.

int m = matrix.size();//二维数组的行数

int n = matrix[0].size();//统计第一行的元素有多少个所以得到列的数目

vector<int> spiral(m*n);//所返回的一位数组也是需要旋转输出的结果

int u=0, d=m-1, l=0, r=n-1, k=0;//k为当前的索引

while(true){

/** up **/

for(int col=l; col<=r; col++){

spiral[k++]=matrix[u][col];

}

if(++u>d){

break;

}

/** right **/

for(int row=u; row<=d; row++){

spiral[k++]=matrix[row][r];

}

if(--r<l){

break;

}

/** down **/

for(int col=r; col>=l; col--){

spiral[k++]=matrix[d][col];

}

if(--d<u){

break;

}

/** left **/

for(int row=d; row>=u; row--){

spiral[k++]=matrix[row][l];

}

if(++l>r){

break;

}

}

return spiral;

}

};

int main(){

vector<vector<int> > vec;

vector<int> a;

a.push_back(1);

a.push_back(2);

a.push_back(3);

vector<int> b;

b.push_back(4);

b.push_back(5);

b.push_back(6);

vector<int> c;

c.push_back(7);

c.push_back(8);

c.push_back(9);

vec.push_back(a);

vec.push_back(b);

vec.push_back(c);

vector<int>::iterator it;

vector<vector<int> >::iterator iter;

vector<int> tmp;

for(iter=vec.begin();iter!=vec.end();iter++){

tmp = *iter;

for(it=tmp.begin();it!=tmp.end();it++){

cout<<*it<<" ";

//cout<<endl;

}

}

Solution S;

S.spiralOrder(vec);

}

【遇到的问题及解决办法】:

在做这一题的时候主要是寻找矩阵的行数难到了我,因为尽管我知道size是确定当前容器中元素的个数,并且也知道列的数目怎么去求但是就是不知道怎么去求行数,这个时候我想既然想知道的话那就去看一下size函数吧然而看着看着就发现matrix.size()正是我所找的求行数的方式,但是为什么这个就是求行数呢,我一直觉得这个应该是求整个矩阵的元素的,然鹅想终究是不行的因为没有理论依据,于是我就去找二维vector的初始过程,看一看他到底是个什么操作怎么就可以生成的是行数,看了之后明白了其实matrix是里面包含了多少个n个元素的元素那么matrix.size()就是有少行了呀,是不是很容易就理解了呢,嗯是的。然后下面我们讨论一下具体该怎么进行旋转输出的操作呢,首先很明显的是如果该矩阵为空的话我就只需要输出一个为空的一位数组,然后如果不为空的话那么从一行从左往右,然后这个时候到了最后一个列数不动,行数要开始往下面遍历,然后每一次遍历完了之后呢要对当前遍历的数据进行自增或者自减,因为只有这样我们才可以一直遍历下去,然后这个需要新建一个一维数组同时根据遍历的数据个数进行自增然后储存下去,这样我们最后梳理一下,有上下左右四个方向并且每一个方向每一次进行一次操作之后就会进行数目上面的相对应的自增和自减,同时在遍历的过程中有一个新的数组进行村数据,最后返回所村数组的首地址,到此为止算法结束。同时问题也得到了比较不错的解决。

发表评论