旋转盒子

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中文网其他相关文章！