ジグザグ行列印刷
行列をジグザグ状に印刷するアルゴリズムを実装します。このアルゴリズムでは、2つのポイントを使用して行列を対角線方向に走査します。
以下の変数を定義します：
- int topLeftRow = 0 - 左上ポイントの行インデックス
- int topLeftCol = 0 - 左上ポイントの列インデックス
- int bottomRightRow = 0 - 右下ポイントの行インデックス
- int bottomRightCol = 0 - 右下ポイントの列インデックス
- int maxRow = matrix.length - 1 - 最終行インデックス
- int maxCol = matrix[0].length - 1 - 最終列インデックス
- boolean isUpward = false - 上向きに印刷するかどうかのフラグ
左上ポイントは右方向へ移動し、右端に達したら下方向へ移動します：
topLeftRow = (topLeftCol == maxCol) ? topLeftRow + 1 : topLeftRow;
topLeftCol = (topLeftCol == maxCol) ? topLeftCol : topLeftCol + 1;右下ポイントは下方向へ移動し、下端に達したら右方向へ移動します：
bottomRightCol = (bottomRightRow == maxRow) ? bottomRightCol + 1 : bottomRightCol;
bottomRightRow = (bottomRightRow == maxRow) ? bottomRightRow : bottomRightRow + 1;実際の印刷処理は別メソッドに委譲し、方向を交互に切り替えます：
public void printZigzagMatrix(int[][] matrix) {
int topLeftRow = 0;
int topLeftCol = 0;
int bottomRightRow = 0;
int bottomRightCol = 0;
int maxRow = matrix.length - 1;
int maxCol = matrix[0].length - 1;
boolean isUpward = false;
while (topLeftCol != maxCol + 1) {
printDiagonal(matrix, topLeftRow, topLeftCol, bottomRightRow, bottomRightCol, isUpward);
topLeftRow = (topLeftCol == maxCol) ? topLeftRow + 1 : topLeftRow;
topLeftCol = (topLeftCol == maxCol) ? topLeftCol : topLeftCol + 1;
bottomRightCol = (bottomRightRow == maxRow) ? bottomRightCol + 1 : bottomRightCol;
bottomRightRow = (bottomRightRow == maxRow) ? bottomRightRow : bottomRightRow + 1;
isUpward = !isUpward;
}
}
public void printDiagonal(int[][] matrix, int row1, int col1, int row2, int col2, boolean isUpward) {
if (isUpward) {
while (row1 != row2 + 1) {
System.out.print(matrix[row1++][col1--] + " ");
}
} else {
while (row2 != row1 - 1) {
System.out.print(matrix[row2--][col2++] + " ");
}
}
}螺旋行列印刷 / LeetCode 54. 螺旋行列
行列を螺旋状に印刷するアルゴリズムを実装します。外側から内側へ向かって螺旋状に要素を印刷していきます。
各層の四隅の座標を追跡します：
- 左上: [startRow][startCol]
- 右上: [startRow][endCol]
- 右下: [endRow][endCol]
- 左下: [endRow][startCol]
印刷処理は以下のステップで行います：
- 左上から右上へ（右方向）
- 右上から右下へ（下方向）
- 右下から左下へ（左方向）
- 左下から左上へ（上方向）
各層の印刷が完了したら、境界を内側に移動します：
public void printSpiralMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int startRow = 0;
int startCol = 0;
int endRow = matrix.length - 1;
int endCol = matrix[0].length - 1;
while (startRow <= endRow && startCol <= endCol) {
// 上辺を左から右へ
for (int i = startCol; i <= endCol; i++) {
System.out.print(matrix[startRow][i] + " ");
}
startRow++;
// 右辺を上から下へ
for (int i = startRow; i <= endRow; i++) {
System.out.print(matrix[i][endCol] + " ");
}
endCol--;
// 下辺を右から左へ（行が残っている場合）
if (startRow <= endRow) {
for (int i = endCol; i >= startCol; i--) {
System.out.print(matrix[endRow][i] + " ");
}
endRow--;
}
// 左辺を下から上へ（列が残っている場合）
if (startCol <= endCol) {
for (int i = endRow; i >= startRow; i--) {
System.out.print(matrix[i][startCol] + " ");
}
startCol++;
}
}
}正方行列の回転
正方行列を90度時計回りに回転させるアルゴリズムを実装します。このアルゴリズムは、行列を外側から内側へ層ごとに処理していきます。
各層の四隅の座標を追跡します：
- 左上: [top][left]
- 右上: [top][right]
- 右下: [bottom][right]
- 左下: [bottom][left]
各層内の要素をグループ化し、各グループ内で要素を回転させます：
public void rotateSquareMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix.length != matrix[0].length) {
return;
}
int top = 0;
int left = 0;
int bottom = matrix.length - 1;
int right = matrix[0].length - 1;
while (top < bottom) {
rotateLayer(matrix, top, left, bottom, right);
top++;
left++;
bottom--;
right--;
}
}
public void rotateLayer(int[][] matrix, int top, int left, int bottom, int right) {
for (int offset = 0; offset < right - left; offset++) {
// 左上の要素を保存
int temp = matrix[top][left + offset];
// 左下 → 左上
matrix[top][left + offset] = matrix[bottom - offset][left];
// 右下 → 左下
matrix[bottom - offset][left] = matrix[bottom][right - offset];
// 右上 → 右下
matrix[bottom][right - offset] = matrix[top + offset][right];
// 一時保存 → 右上
matrix[top + offset][right] = temp;
}
}このアルゴリズムの時間計算量はO(N²)で、Nは行列のサイズです。空間計算量はO(1)であり、追加のメモリを使用せずにインプレースで回転を行います。