旋轉盒子

1861。旋轉盒子

難度：中

主題：陣列、兩個指標、矩陣

給你一個 m x n 的字元框矩陣，代錶盒子的側視圖。盒子的每個單元格都是以下之一：

• 一塊石頭“#”
• 靜止障礙物“*”
• 空“.”

盒子順時針旋轉90度，導致一些石頭因重力而掉落。每塊石頭都會落​​下，直到落在障礙物、另一塊石頭或盒子的底部。重力不會影響障礙物的位置，盒子旋轉產生的慣性不會影響石頭的水平位置。

保證盒子中的每塊石頭都放置在障礙物、另一塊石頭或盒子的底部上。

回傳一個 n x m 矩陣，表示上述旋轉後的盒子。

範例1：

• 輸入： box = [["#",".","#"]]
• 輸出： [["."], ["#"], ["#"]]

範例2：

• 輸入： box = [["#",".","","."], ["#","#","","."] ]
• 輸出： [["#","."], ["#","#"], ["",""], [".","。 “]]

範例 3：

• 輸入： box = [["#","#","",".","","."], ["#","#", "#","*",".","."], ["#","#","#",".","#","."]]
• 輸出： [[".","#","#"], [".","#","#"], ["#","#"," "], ["#","","."], ["#",".","*"], ["#",".","."]]

約束：

• m == box.length
• n == box[i].length
• 1
• box[i][j] 是「#」、「*」或「.」。

提示：

1. 使用關係式rotatedBox[i][j] = box[m - 1 - j][i].
旋轉盒子
2. 從盒子底部開始迭代，對於每個空白單元格檢查其上方是否有任何石頭且它們之間沒有障礙物。

解：

我們需要遵循幾個不同的步驟：

1. 旋轉盒子：我們先將矩陣順時針旋轉90度。旋轉後的矩陣將有 n 行和 m 列，其中 n 是原始框中的列數，m 是行數。

2. 重力效果：旋轉後，我們需要模擬重力的效果。這意味著所有石頭 ('#') 都應該「落到」新列的底部，只有在遇到障礙物 ('*') 或另一塊石頭 ('#') 時才停止。

方法：

1. 旋轉：旋轉後，原矩陣中第[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。
   • 如果遇到障礙物（*），將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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是旋轉盒子的詳細內容。更多資訊請關注PHP中文網其他相關文章！