C++版 - 剑指offer 面试题20：顺时针打印矩阵及其变形(LeetCode54. Spiral Matrix旋转矩阵) 题解

Enjoy233

发布于 2019-03-05 14:34:08

1.2K00

代码可运行

文章被收录于专栏：大白技术控的技术自留地大白技术控的技术自留地

运行总次数：0

代码可运行

剑指offer 面试题20：顺时针打印矩阵 题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵：

牛客网提交网址： http://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172

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

分析：

这是排版题中的一种类型(无明显规律)，这类题不会要求时间复杂度和空间复杂度。

先算出圈数circle=(min(row, col)-1)/2+1，然后一圈一圈的打印，循环的边界条件需注意，一次AC还是有难度的...

分析填充过程，可发现，整个填充过程可以从外到内分为几个圈，只要能完成一圈的输出，剩下的圈采用同样的方法输出即可。

从最外圈开始，一圈的遍历又可以分为四个过程，即走到底就改变方向[用X来表示横坐标(或列数)，用Y来表示纵坐标(或行数) ]：

1.从左到右遍历：matrix[startY][startX] => matrix[startY][endX]；

2.从上到下遍历：matrix[startY+1][endX] => matrix[endY-1][endX]；

3.从右到左遍历：matrix[endY][endX] => matrix[endY][startX]；

4.从下到上遍历：matrix[endY-1][startX] => matrix[startY+1][startX]；

出现某一圈中只包含一行时，要判断从左向右打印和从右向左打印的时候是否会出现重复打印，同理某一圈中只包含一列时，要判断从上向下打印和从下向上打印的时候是否会出现重复打印的情况.

牛客网 AC代码：

#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
		vector<int> res;
		int col, row;
		row=matrix.size();     // matrix.size()表示矩阵的逻辑结构中的行数 
		if(row==0) return res;		
		col=matrix[0].size();

		int circle=((row<col?row:col)-1)/2+1; // 圈数 
		
		for(int k=0; k<circle; k++)  // 此处k是所在圈数，最外圈是第0圈
		{
			for(int i=k; i<col-k; i++) res.push_back(matrix[k][i]);  // 从左到右，横坐标(列数)i++
			for(int j=k+1; j<row-k; j++) res.push_back(matrix[j][col-1-k]);  // matrix[k+1][j] ==> matrix[row-k][j]; 从上到下，纵坐标(当前所在行数)j++
			for(int m=col-k-2; (m>=k)&&(row-k-1!=k); m--) res.push_back(matrix[row-k-1][m]); // 防止重复, 从右到左，横坐标(当前所在列数)i--
			for(int n=row-k-2; (n>k)&&(col-k-1!=k); n--) res.push_back(matrix[n][k]);  // 防止重复，从下到上，纵坐标(当前所在行数)n--
		}		
	return res;	
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	vector<vector<int> > mat1={
	{1,2,3,4,5},
	{6,7,8,9,10},
	{11,12,13,14,15},
	{16,17,18,19,20}
	};
	// vector<vector<int> > mat1;
	vector<int> res1 = sol.printMatrix(mat1);

	for(unsigned int k=0; k<mat1.size(); k++)  // 外层循环，行数++ 
	{   
	    for(unsigned int i=0; i<mat1[0].size(); i++)
	    {
	        printf("%d ", mat1[k][i]);    
	    }
	    printf("\n");
	}	
	return 0;
}

LeetCode54. Spiral Matrix旋转矩阵

提交网址： https://leetcode.com/problems/spiral-matrix/

Total Accepted: 59378 Total Submissions: 262428 Difficulty: Medium

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

leetcode AC代码：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> >& matrix) {
		vector<int> res;
		int col, row;
		row=matrix.size();     // matrix.size()表示逻辑结构中的行数 
		if(row==0) return res;		
		col=matrix[0].size();

		int circle=((row<col?row:col)-1)/2+1; // 圈数 
		
		for(int k=0; k<circle; k++)  // 此处k是圈数，最外圈是第0圈 
		{
			for(int i=k; i<col-k; i++) res.push_back(matrix[k][i]); // 从左到右，横坐标(列数)++
			for(int j=k+1; j<row-k; j++) res.push_back(matrix[j][col-1-k]);  // matrix[k+1][j] ==> matrix[row-k-2][j];
			for(int m=col-k-2; (m>=k)&&(row-k-1!=k); m--) res.push_back(matrix[row-k-1][m]); // 防止重复
			for(int n=row-k-2; (n>k)&&(col-k-1!=k); n--) res.push_back(matrix[n][k]); // 防止重复
		}		
	return res;	
    }    
};

腾讯2016春后台开发实习生笔试编程题

蛇形矩阵：作为一种常用的数学数列，是由1开始的自然数一次排列成的一个N*N的正方形矩阵，数字依次由外而内的递增，如下面的实例：

n=3的蛇形矩阵：

1 2 3

8 9 4

7 6 5

n=6的蛇形矩阵：

1 2 3 4 5 6

20 21 22 23 24 7

19 32 33 34 25 8

18 31 36 35 26 9

17 30 29 28 27 10

16 15 14 13 12 11

此题要求输入蛇形矩阵宽度N，输出整个蛇形矩阵结果，注意输出格式要求按照矩阵从上至下的依次按行输出，每行中间无需换行输出。

样本输入：3

样本输出：1 2 3 8 9 4 7 6 5

AC代码：

其中n从控制台输入...

#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
    void printMatrix(int n)
	{
		vector<int> res;
		vector<vector<int> > matrix;
		int row, col;
		row=n;     // matrix.size()表示行数，二维数组以行优先存储 
		if(row==0) return;		
		col=n;
		matrix.resize(row, vector<int>(col)); // 根据输入的n来设置矩阵大小，动态分配空间 
		// matrix = vector<vector<int> >(row, vector<int>(col));

		// int circle=((row<col?row:col)-1)/2+1; // 圈数 
		int circle=(row-1)/2+1; // 圈数，由上面注释的语句简化而来 
		int val=0; // 计数器，表示当前的值，每次加1 
		
		for(int k=0; k<circle; k++)  // 此处k是列数，即横坐标x 
		{
			for(int i=k; i<col-k; i++)
				matrix[k][i]=++val; // 从左到右，横坐标(列数)++
			for(int j=k+1; j<row-k; j++)
				matrix[j][col-1-k]=++val;
			for(int m=col-k-2; (m>=k)&&(row-k-1!=k); m--)
				matrix[row-k-1][m]=++val; // 防止重复
			
			for(int n=row-k-2; (n>k)&&(col-k-1!=k); n--)
				matrix[n][k]=++val; // 防止重复
		}		
		for(int k=0; k<row; k++)  // 外层循环，行数++ 
		{   
		    for(int i=0; i<col; i++)
		    {
		        printf("%d ", matrix[k][i]);   // 内层循环，列数++ 
		    }
		    // printf("\n");
		}
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	int n;
	while(scanf("%d", &n)==1) 
	{
	sol.printMatrix(n);
	printf("\n");		
	}

	return 0;
}

如果要求输入的不是方阵，而是普通矩阵，矩阵长m，宽n，则相应代码如下：

#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
    void printMatrix(int m, int n)
	{
		vector<int> res;
		vector<vector<int> > matrix;
		int row, col;
		row=m;     // matrix.size()表示行数，二维数组以行优先存储 
		if(row==0) return;		
		col=n;
		matrix.resize(row, vector<int>(col)); // 根据输入的n来设置矩阵大小，动态分配空间 
		// matrix = vector<vector<int> >(row, vector<int>(col));

		int circle=((row<col?row:col)-1)/2+1; // 圈数 
		int val=0; // 计数器，表示当前的值，每次加1 
		
		for(int k=0; k<circle; k++)  // 此处k是列数，即横坐标x 
		{
			for(int i=k; i<col-k; i++)
				matrix[k][i]=++val; // 从左到右，横坐标(列数)++
			for(int j=k+1; j<row-k; j++)
				matrix[j][col-1-k]=++val;
			for(int m=col-k-2; (m>=k)&&(row-k-1!=k); m--)
				matrix[row-k-1][m]=++val; // 防止重复
			
			for(int n=row-k-2; (n>k)&&(col-k-1!=k); n--)
				matrix[n][k]=++val; // 防止重复
		}		
		for(int k=0; k<row; k++)  // 外层循环，行数++ 
		{   
		    for(int i=0; i<col; i++)
		    {
		        printf("%d ", matrix[k][i]);    
		    }
		    // printf("\n");
		}
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	int n,m;
	while(scanf("%d %d", &m,&n)==2) 
	{
	sol.printMatrix(m,n);
	printf("\n");		
	}

	return 0;
}

如果要求输入m,n以及m*n个值：

题目1391-九度Online Judge http://ac.jobdu.com/problem.php?pid=1391

则代码应为:

// 题意：输入的第一行包括两个整数m和n(1<=m,n<=1000)，m为行数，n为列数，后面输入矩阵中的相应值(m*n个)
#include <cstdio>
using namespace std;

int m, n;
const int MAXN = 1005;
int a[MAXN][MAXN];

int main() {
	int i, j;

	while(scanf("%d%d", &m, &n) == 2) {
		if(m <= 0 || n <= 0) {
			continue;
		}
		for(i = 0; i < m; ++i) {
			for(j = 0; j < n; ++j) {
				scanf("%d", &a[i][j]);
			}
		}

		for(i = 0; (i <= m - 1 - i) && (i <= n - 1 - i); ++i) {
			for(j = i; j <= n - 1 - i; ++j) {
				printf("%d ", a[i][j]);
			}
			if(i + 1 <= m - 1 - i - 1) {
				for(j = i + 1; j <= m - 1 - i - 1; ++j) {
					printf("%d ", a[j][n - 1 - i]);
				}
			}
			if(i < m - 1 - i) {
				for(j = n - 1 - i; j >= i; --j) {
					printf("%d ", a[m - 1 - i][j]);
				}
			}
			if(i + 1 <= m - 1 - i && i < n - 1 - i) {
				for(j = m - 1 - i - 1; j >= i + 1; --j) {
					printf("%d ", a[j][i]);
				}
			}
		}
		printf("\n");
	}

	return 0;
}