マトリックスを時計回りに印刷(面接プログラミングまたは問題)
1827 ワード
タイトル:マトリクスを入力し、外から時計回りに順番に各数字を印刷します.たとえば、次のマトリクスを入力します.
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の順に印刷されます.
2年前、面接に行った时、机に乗ってこの问题をやらせて、久しぶりに考えて、1时间の笔记试験の答案を作ったことを悔やんでいました.....
今日はこの定番の面接問題を理解したいと思います.
考え方:
タイトルの説明に従って、回転して印刷して、1回転して左から右へ、上から下へ、右から左へ、下から上へ.
上記の例では、
1、2、3、4、8、12、16、15、14、13、9、5が1周目
6、7、11、10は2周目
この問題の難点は,複数の境界条件をどのように判定するかである.
このサイクル終了の条件を解析する.1対5×5の行列では,最後の輪には1つの数字しかなく,対応する座標は(2,2)である.5>2*2を発見しました.対6×6の行列の場合、最後の輪には4つの数字があり、対応する座標は依然として(2,2)である.6>2*2は依然として成立していることが分かった.そこで,サイクルを継続させる条件はcolumns>startX*2&&rows>startY*2であることが分かった.
再帰コード実装:
非再帰的な形式は、『剣指offer』を参照してください.http://blog.csdn.net/rsljdkt/article/details/9749915
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の順に印刷されます.
2年前、面接に行った时、机に乗ってこの问题をやらせて、久しぶりに考えて、1时间の笔记试験の答案を作ったことを悔やんでいました.....
今日はこの定番の面接問題を理解したいと思います.
考え方:
タイトルの説明に従って、回転して印刷して、1回転して左から右へ、上から下へ、右から左へ、下から上へ.
上記の例では、
1、2、3、4、8、12、16、15、14、13、9、5が1周目
6、7、11、10は2周目
この問題の難点は,複数の境界条件をどのように判定するかである.
このサイクル終了の条件を解析する.1対5×5の行列では,最後の輪には1つの数字しかなく,対応する座標は(2,2)である.5>2*2を発見しました.対6×6の行列の場合、最後の輪には4つの数字があり、対応する座標は依然として(2,2)である.6>2*2は依然として成立していることが分かった.そこで,サイクルを継続させる条件はcolumns>startX*2&&rows>startY*2であることが分かった.
再帰コード実装:
#include
using namespace std;
/*
: ; , , , , , ; , , 。
:numbers: ;columns: ;rows: ;start: (x、y , 5X5, (start,start) (0,0)...)
*/
void PrintMatrix(int **number, int columns, int rows, int start=0)
{
if( !number || columns < 1 || rows < 1 || start < 0 )
return;
if( columns <= 2*start || rows <= 2*start )
return;
int stopX = columns - 1 - start;//
int stopY = rows - 1 - start;//
//
for( int i=start; i<=stopX; i++)
cout <= start; i--)
cout<= start+1; i--)
cout<
非再帰的な形式は、『剣指offer』を参照してください.http://blog.csdn.net/rsljdkt/article/details/9749915