剑指offer 面试题20―顺时针打印矩阵

题目:

输入1个矩阵,依照从外向里以顺时针的顺序顺次打印出每个数字。
例如:如果输入以下矩阵:

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圈作为我们分析的目标。在下图中,我们设矩阵的宽度为columns,而其高度为rows。我们我们选取左上角坐标为(startX,
startY)
,右下角坐标为(endX, endY)的1个圈来分析。

      由于endXendY可以根据startXstartYcolumnsrows来求得,因此此时我们只需要引入startXstartY两个变量。我们可以想象有1个循环,在每次循环里我们从(startX,
startY)
动身依照顺时针打印数字。

接着我们分析这个循环结束的条件。对1个5×5的矩阵而言,最后1圈只有1个数字,对应的坐标为(2, 2)。我们发现5 > 2 * 2。对1个6×6的矩阵而言,最后1圈有4个数字,对应的坐标依然为(2,
2)
。我们发现6 > 2 * 2仍然成立。因而我们可以得出,让循环继续的条件是columns > startX * 2 && rows > startY * 2

     接下来我们分析如何依照顺时针的顺序打印1圈的数字。犹如在图中标注的那样,我们可以分4步来打印:第1步是从左到右打印1行(上图中黄色区域),第2步是从上到下打印1列(上图中绿色区域),第3步从右到左打印1行(上图中蓝色区域),最后1步是从下到上打印1列(上图中紫色区域)。也就是我们把打印1圈数字这个问题,分解成4个子问题。

      值得注意的是,最后1圈可能退化成只有1行、只有1列、乃至只有1个数字,因此打印这样的1圈就不需要4步了。

#include <iostream>
using namespace std;

void PrintMatrixIncircle(int nArr[][4], int rows, int columns, int nStart)
{
int nEndX = columns – 1 -nStart;
int nEndY = rows – 1 -nStart;

//从左到右打印1行
for (int i=nStart; i<=nEndX; i++)
{
cout << nArr[nStart][i] << " ";
}

//从上到下打印1列
if (nEndY > nStart)
{
for (int j=nStart+1; j<=nEndY; j++)
{
cout << nArr[j][nEndX] << " ";
}
}

//从右到左打印1行
if (nEndY > nStart && nEndX > nStart)
{
for (int t=nEndX⑴; t>=nStart; t–)
{
cout << nArr[nEndY][t] << " ";
}
}

//从下到上打印1列
if (nEndY ⑴ > nStart && nEndX > nStart)
{
for (int n=nEndY⑴; n>=nStart+1; n–)
{
cout << nArr[n][nStart] << " ";
}
}
}

//顺时针打印矩阵,行数为rows,列数为columns
void PrintMatrixClockWisely(int nArr[][4], int rows, int columns)
{
if (nArr == NULL || rows <= 0 || columns <= 0)
return ;

int nStart = 0;
while (rows>(nStart*2) && columns>(nStart*2))
{
PrintMatrixIncircle(nArr, rows, columns, nStart);
nStart++;
}
}

int main()
{
int nMatrix[4][4] = {
{1,2,3,4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};

PrintMatrixClockWisely(nMatrix, 4, 4);
cout << endl;

return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 剑指offer 面试题20―顺时针打印矩阵

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡