您當(dāng)前位置：首頁 > php開源 > php教程 > 劍指offer 面試題20―順時(shí)針打印矩陣

劍指offer 面試題20―順時(shí)針打印矩陣

來源：程序員人生發(fā)布時(shí)間：2015-05-11 09:21:54 閱讀次數(shù)：2548次

題目：

輸入1個(gè)矩陣，依照從外向里以順時(shí)針的順序順次打印出每個(gè)數(shù)字。
例如：如果輸入以下矩陣：

1             2             3             4
5             6             7             8
9             10            11             12
13            14            15             16
則順次打印出數(shù)字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6,7, 11, 10。

基本思想：

通常當(dāng)我們遇到1個(gè)復(fù)雜的問題的時(shí)候，我們可以用圖形幫助我們思考。由于我們是以從外圈到內(nèi)圈的順序順次打印，我們在矩陣中標(biāo)注1圈作為我們分析的目標(biāo)。在下圖中，我們設(shè)矩陣的寬度為columns，而其高度為rows。我們我們選取左上角坐標(biāo)為(startX, startY)，右下角坐標(biāo)為(endX, endY)的1個(gè)圈來分析。

由于endX和endY可以根據(jù)startX、startY和columns、rows來求得，因此此時(shí)我們只需要引入startX和startY兩個(gè)變量。我們可以想象有1個(gè)循環(huán)，在每次循環(huán)里我們從(startX, startY)動(dòng)身依照順時(shí)針打印數(shù)字。

接著我們分析這個(gè)循環(huán)結(jié)束的條件。對1個(gè)5×5的矩陣而言，最后1圈只有1個(gè)數(shù)字，對應(yīng)的坐標(biāo)為(2, 2)。我們發(fā)現(xiàn)5 > 2 * 2。對1個(gè)6×6的矩陣而言，最后1圈有4個(gè)數(shù)字，對應(yīng)的坐標(biāo)依然為(2, 2)。我們發(fā)現(xiàn)6 > 2 * 2仍然成立。因而我們可以得出，讓循環(huán)繼續(xù)的條件是columns > startX * 2 && rows > startY * 2。

接下來我們分析如何依照順時(shí)針的順序打印1圈的數(shù)字。猶如在圖中標(biāo)注的那樣，我們可以分4步來打印：第1步是從左到右打印1行（上圖中黃色區(qū)域），第2步是從上到下打印1列（上圖中綠色區(qū)域），第3步從右到左打印1行（上圖中藍(lán)色區(qū)域），最后1步是從下到上打印1列（上圖中紫色區(qū)域）。也就是我們把打印1圈數(shù)字這個(gè)問題，分解成4個(gè)子問題。

值得注意的是，最后1圈可能退化成只有1行、只有1列、乃至只有1個(gè)數(shù)字，因此打印這樣的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] << " "; } } } //順時(shí)針打印矩陣，行數(shù)為rows，列數(shù)為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; }

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生

------分隔線----------------------------

上一篇 生成所有的BST

下一篇 如何快速高效的接入移動(dòng)第三方SDK

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關(guān)注

欄目熱點(diǎn)

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

劍指offer 面試題20―順時(shí)針打印矩陣