時計回りのマトリックス

牛客網AC住所:http://www.nowcoder.com/books/coding-interviews/9b4c81a02cd34f76be2659fa0d54342a?rp=1
《剣指offer》面接問題20:時計回り印刷マトリクス
タイトル:マトリクスを入力し、外から時計回りに順番に数字を印刷します.たとえば、次の行列を入力します.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16は、数字1、2、3、4、8、12、16、15、14、13、9、5、6、7、11、10を順次印刷する.
考え方:この問題を分析して、私たちは図形を借りて私たちの思考を助けることができます.外輪から内輪の順に印刷されるので,マトリクスを下図のようにいくつかの輪に想像することができる.マトリクスを1サイクルで印刷できます.各印刷マトリクスの1つのリング.
   
でもループはいつ終わるの?
この行列の行数をrows,列数をcolsと仮定する.印刷1周目の左上隅の座標は(0,0)、2周目の左上隅の座標は(1,1)となります.ここで、左上隅の座標では、行標と列標は常に同じであるため、行列の中で左上角(start,start)の輪を私たちの分析の目標として選択することができる.
次に分析サイクルはいつまでですか?
いくつかの行列を描いてみると、ループを続ける条件はcols>startXであることがわかります.×2そしてrows>startY×2.マトリクスを印刷するには、次のサイクルを使用します.

void PrintMatrixClockwisely(int** numbers, int cols, int rows) {
    if (numbers == NULL || cols <= 0 || rows <= 0) 
        return;
    int start = 0;
    while(cols > start*2 && rows > start*2) {
        PrintMatrixInCircle(numbers, cols, rows, start);
        ++start;
    }
}

次に、PrintMatrixInCircleを実現する方法を具体的に分析します.最初の図に示すように、印刷の1周を4つのステップに分けることができます.最初のステップは左から右に1行、2番目のステップは上から下に1列、3番目のステップは右から左に1行、4番目のステップは下から上に1列を印刷します.各ステップでは、開始座標と終了座標に基づいて1サイクルで1行または列を印刷できます.
ここで注目すべきは、最後のループが1行、1列、さらには1つの数字に劣化する可能性があるため、このループを印刷するには4ステップは必要ありません.下図はいくつかの劣化例です.
   
したがって、各ステップを印刷する際の前提条件を分析する必要があります.最初のステップは、少なくとも1つのステップを印刷するために必要です.1行しかない場合は、2番目のステップを印刷する必要はありません.これにより、2番目のステップの前提条件は、終了行番号が開始行番号より大きいことです.第3ステップの印刷が必要な前提条件は、圏内に少なくとも2行の2列があることである.すなわち、終了行番号が開始行番号より大きいことを要求するほか、終了列番号が開始列番号より大きいことを求める.ステップ4を印刷する必要がある前提条件は、少なくとも3行2列であるため、終了行番号が開始行番号より少なくとも2大きく、終了列番号が開始列番号より大きいことです.
上記の分析により、コードを書き出すことができます.

void PrintMatrixInCircle(int** numbers, int cols, int rows, int start) {
    int endX = cols - 1 - start;
    int endY = rows - 1 - start;

    //         
    for (int i = start; i <= endX; ++i) {
        int number = numbers[start][i];
	printNumber(number);
    }
    
    //         
    if (start < endY) {
        for (int i = start + 1; i <= endY; ++i) {
            int number = numbers[i][endX];
	    printNumber(number);
        }
    }

    //         
    if (start < endX && start < endY) {
        for (int i = endX - 1; i >= start; --i) {
            int number = numbers[endY][i];
	    printNumber(number);
        }
    }

    //         
    if (start < endX && start < endY - 1) {
        for (int i = endY - 1; i >= start + 1; --i) {
            int number = numbers[i][start];
	    printNumber(number);
        }
    }
}

この問題は複雑なデータ構造に関与していないが,実行過程を注意深く分析する必要がある.上記の手順は基本的に「剣指offer」から来ており、以下は自分のACコードです.
注意すべき点は、最後に印刷する前提条件であり、隅のnumberを繰り返すことを避ける必要があることです.

public class Solution {
	public ArrayList<Integer> printMatrix(int[][] matrix) {
		ArrayList<Integer> matrixList = new ArrayList<Integer>();
		if (matrix == null || matrix.length == 0) {
			return null;
		}
		int row = matrix.length;  //  
		int col = matrix[0].length;  //  
		int start = 0;
		while (col > start * 2 && row > start * 2) { //       
			int endX = col - start - 1;
			int endY = row - start - 1;
			for (int i = start; i <= endX; i++) { //     
				matrixList.add(matrix[start][i]);
			}
			if (start < endY) {
				for (int i = start + 1; i <= endY; i++) { //     
					matrixList.add(matrix[i][endX]);
				}
			}
			if (start < endX && start < endY) {
				for (int i = endX - 1; i >= start; i--) { //     
					matrixList.add(matrix[endY][i]);
				}
			}
			if (start < endX && start < endY - 1) {
				for (int i = endY - 1; i >= start + 1; i--) { //     
					matrixList.add(matrix[i][start]);
				}
			}
			start++;
		}
		for (int i = 0; i < matrixList.size(); i++) {
			System.out.print(matrixList.get(i) + " ");
		}
		return matrixList;
	}

	//          row，  col   （    ）
	public int[][] createMatrix(int[] arr, int col, int row) {
		int[][] matrix = new int[row][col];
		int i = 0;

		for (int j = 0; j < row; j++) { //     
			for (int k = 0; k < col; k++) {
				if (matrix[j][k] == 0) {
					matrix[j][k] = arr[i++];
				}
			}
		}
		return matrix;
	}
	
	//       
	public void printMatrixOriginal(int[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}
}

上記のコードは、必要なprintMatrixメソッドに加えて、マトリクスの行単位印刷を提供し、1次元配列で2次元配列を構築し、行番号と列番号の取得に注意する必要があります.コードをコミットするときは、matrixListを印刷する場所を削除する必要があります.そうしないと、実行は通過しません.

int row = matrix.length;  //  
int col = matrix[0].length;  //  

最後にテストコード:

public class Main {
	public static void main(String[] args) {
		Solution test = new Solution();
		int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
		int[][] matrix = test.createMatrix(arr, 4, 4);
		System.out.println("       ：");
		test.printMatrixOriginal(matrix);
		System.out.println("       ：");
		test.printMatrix(matrix);
	}
}

実行結果: