题目:
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,
例如,如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路:
把矩阵想象成若干个圈,通过循环操作来打印矩阵,每次打印矩阵中的一个圈;
1、循环起始条件和结束条件:
起始条件:(1,1),(2,2)。。。(start,start)
结束条件:columns>start*2 && rows>start*2
2、如何打印一圈:
分为四步:1、从左到右打印一行(上);2、从上到下打印一列(右);3、从右到左打印一行(下);4、从下到上打印一列(左)
每一步根据起始坐标和终止坐标用一个循环就可以打印一行或一列,但并不是每一圈都需要打印四次,有些圈可能退化为一行或一列或其他,需要考虑每一步打印的前题条件;
3、每一步打印的前提条件:
第一步:没有,一定需要的;
第二步:终止行号大于起始行号;
第三步:终止行号大于起始行号&&终止列号大于起始列号;
第四部:终止行号大于起始行号+1,&&终止列号大于起始列号;
代码:
#include <stdio.h>
#include <stdlib.h> using namespace std; void PrintMatrixInCircle(int** numbers,int columns,int rows,int start){
int endX=columns-1-start;
int endY=rows-1-start; // print from left to right
for(int i=start;i<=endX;i++)
printf("%d ",numbers[start][i]); // print from top to bottom
if(endY>start){
for(int i=start+1;i<=endY;i++)
printf("%d ",numbers[i][endX]);
} // print from right to left
if(endY>start && endX>start){
for(int i=endX-1;i>=start;i--)
printf("%d ",numbers[endY][i]);
} // print bottom to top
if(endX>start && endY>(start+1)){
for(int i=endY-1;i>=start+1;i--)
printf("%d ",numbers[i][start]);
}
} void PrintMatrixClockwisely(int** numbers,int columns,int rows){
if(numbers==NULL || columns<=0 || rows<=0)
return;
int start=0;
while(columns>start*2 && rows>start*2){
PrintMatrixInCircle(numbers,columns,rows,start);
++start;
}
printf("\n");
} int main()
{
const int M=4;
const int N=4;
/*
int** array=new int*[M];
for(int i=0;i<M;i++)
array[i]=new int[N];
*/
int** array=(int **)malloc(M *sizeof(int *));
for(int i=0;i<M;i++)
array[i] = (int *)malloc(N *sizeof(int)); int k=1;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++)
array[i][j]=k++;
} PrintMatrixClockwisely(array,M,N); for(int i=0;i<M;i++){
free(array[i]);
array[i] = NULL;
}
free(array);
array=NULL; return 0;
}
在线测试OJ:
http://www.nowcoder.com/books/coding-interviews/9b4c81a02cd34f76be2659fa0d54342a?rp=1
AC代码:
class Solution {
public:
void PrintMatrixInCircle(const vector<vector<int> > &matrix,vector<int> &mat,int rows,int columns,int start){
int endX=columns-1-start;
int endY=rows-1-start; // print from left to right
for(int i=start;i<=endX;i++)
mat.push_back(matrix[start][i]);
//printf("%d ",numbers[start][i]); // print from top to bottom
if(endY>start){
for(int i=start+1;i<=endY;i++)
mat.push_back(matrix[i][endX]);
//printf("%d ",numbers[i][endX]);
} if(endY>start && endX>start){
for(int i=endX-1;i>=start;i--)
mat.push_back(matrix[endY][i]);
//printf("%d ",numbers[endY][i]);
} if(endX>start && endY>(start+1)){
for(int i=endY-1;i>=start+1;i--)
mat.push_back(matrix[i][start]);
//printf("%d ",numbers[i][start]);
}
}
vector<int> printMatrix(vector<vector<int> > matrix) {
int rows=matrix.size();
int columns=matrix[0].size();
int start=0;
vector<int> mat;
while(columns>2*start && rows>2*start){
PrintMatrixInCircle(matrix,mat,rows,columns,start);
++start;
}
return mat;
}
};