Spiral Matrix 又叫蛇形访问,通过每次循环访问一圈后,向里深入一层,关键是需要注意最后剩下一行或者一列的情况
class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int >ans; if(matrix.size()==0)return ans; int b1=0,b2=0,e2=matrix.size()-1,e1=matrix[0].size()-1; while(b1<e1&&b2<e2){ for(int i=b1;i<e1;i++)//l to r ans.push_back(matrix[b2][i]); for(int i=b2;i<e2;i++)//top to down ans.push_back(matrix[i][e1]); for(int i=e1;i>b1;i--)//r to l ans.push_back(matrix[e2][i]); for(int i=e2;i>b2;i--)//down to top ans.push_back(matrix[i][b1]); b1++; b2++; e1--; e2--; } if(b1==e1)while(b2<=e2)ans.push_back(matrix[b2++][b1]); else if(b2==e2)while(b1<=e1)ans.push_back(matrix[b2][b1++]); return ans; } };
Spiral Matrix II 此题和上一题差别不大,因为是正方形,可能还简单一些,按照上面访问的方式读改为写即可
class Solution { public: vector<vector<int> > generateMatrix(int n) { vector<vector<int> >ans; vector<int >a(n,0); for(int i=0;i<n;i++){ ans.push_back(a); } if(n==0)return ans; int b1=0,e1=n-1; int k=1; while(b1<e1){ for(int i=b1;i<e1;i++){ ans[b1][i]=k; k++; } for(int i=b1;i<e1;i++){ ans[i][e1]=k; k++; } for(int i=e1;i>b1;i--){ ans[e1][i]=k; k++; } for(int i=e1;i>b1;i--){ ans[i][b1]=k; k++; } b1++; e1--; } if(b1==e1)ans[b1][b1]=k; return ans; } };
Rotate Image 类似于Spiral Matrix ,通过先旋转外层,再旋转内层,逐层旋转
class Solution { public: void rotate(vector<vector<int> > &matrix) { int b=0,e=matrix.size()-1; if(e<=b)return; int tmp; while(b<e){ for(int i=0;i<e-b;i++){ tmp=matrix[b][b+i]; matrix[b][b+i]=matrix[e-i][b]; matrix[e-i][b]=matrix[e][e-i]; matrix[e][e-i]=matrix[b+i][e]; matrix[b+i][e]=tmp; } b++; e--; } } };