ボックスを回転させる

1861年。ボックスを回転させる

難易度: 中

トピック: 配列、2 ポインター、行列

ボックスの側面図を表す文字ボックスの m x n 行列が与えられます。ボックスの各セルは次のいずれかです:

• 石「#」
• 静止障害物 '*'
• 空の「.」

箱は 時計回りに 90 度回転し、重力により石の一部が落下します。各石は、障害物、別の石、または箱の底に着地するまで落ちます。重力は障害物の位置に影響しません、ボックスの回転による慣性も石の水平位置に影響しません。

保証されています。

上記の回転後のボックスを表す n x m 行列を返します。

例 1:

• 入力: ボックス = [["#",".","#"]]
• 出力: [["."], ["#"], ["#"]]

例 2:

• 入力: ボックス = [["#",".","","."], ["#","#","","."] ]
• 出力: [["#","."], ["#","#"], ["",""], [".",". "]]

例 3:

• 入力: ボックス = [["#","#","",".","","."], ["#","#", "#","*",".","."], ["#","#","#",".","#","."]]
• 出力: [[".","#","#"], [".","#","#"], ["#","#"," "]、["#"、""、"."]、["#"、"."、"*"]、["#"、"."、"."]]

制約:

m == box.length
n == box[i].length
1 box[i][j] は '#'、'*'、または '.' のいずれかです。

ヒント:

rotatedBox[i][j] = box[m - 1 - j][i] の関係を使用してボックスを回転します。
ボックスの底から繰り返しを開始し、空のセルごとに、間に障害物がなく、その上に石があるかどうかを確認します。

解決策:

1. ボックスを回転します: まず、行列を時計回りに 90 度回転します。回転された行列は n 行 m 列になります。n は元のボックスの列数、m は行数です。

2. 重力効果: 回転後、重力の効果をシミュレートする必要があります。これは、すべての石 ('#') が新しい列の一番下に「落ち」、障害物 ('*') または別の石 ('#') に遭遇した場合にのみ停止することを意味します。

アプローチ：

1. Rotation: 回転後、元の行列の位置 [i][j] にある要素は、回転された行列の位置 [j][m-1-i] に配置されます。マトリックス。

2. 重力シミュレーション: 各列を下から上に処理する必要があります。石 ('#') がある場合、障害物または底に到達するまで落下します。セルが空 ('.') の場合、石を入れることができます。

段階的な説明:

1. 回転したボックスの新しい行列を作成します.
2. 回転された行列 (回転後) の各列を反復処理します.
3. 各列の重力をシミュレートします。下から開始して上に移動します。障害物 ('*') はそのままにして、石 ('#') をできるだけ下に配置します。
4. 最終的に回転された行列を返します.

このソリューションを PHP で実装してみましょう: 1861。ボックスを回転させる

<?php
function rotateTheBox($box) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$box = [
    ["#", ".", "#"],
];
print_r(rotateTheBox($box));

$box = [
    ["#", ".", "*", "."],
    ["#", "#", "*", "."],
];
print_r(rotateTheBox($box));

$box = [
    ["#", "#", "*", ".", "*", "."],
    ["#", "#", "#", "*", ".", "."],
    ["#", "#", "#", ".", "#", "."],
];
print_r(rotateTheBox($box));
?>

説明：

1. 重力をシミュレート:

   • 各行を右から左に移動します。ポインタ (空のスロット) を使用して、次の石が落ちるべき場所を追跡します。
   • 石 (#) が見つかった場合は、それを emptySlot に移動し、emptySlot をデクリメントします。
   • 障害物 (*) に遭遇した場合は、emptySlot を障害物の直前の位置にリセットします。

2. 行列を回転します:

   • 回転されたボックスの [i][j] の要素が元のボックスの [m - 1 - j][i] から取得される新しい行列を作成します。

出力例

入力：

$box = [
    ["#", ".", "#"],
];

出力：

[
    [".",],
    ["#",],
    ["#",],
]

入力：

$box = [
    ["#", ".", "*", "."],
    ["#", "#", "*", "."],
];

出力：

[
    ["#", "."],
    ["#", "#"],
    ["*", "*"],
    [".", "."],
]

時間計算量

1. 重力シミュレーション: O(m x n)。行列の各要素を反復処理します。
2. 回転: O(m x n)、回転行列を作成します。

合計: O(m x n).

空間の複雑さ

• O(m x n) は回転行列です。

このソリューションは効率的で、問題の制約を遵守しています。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がボックスを回転させるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。