상자 회전하기

1861. 상자 회전

난이도:중

주제: 배열, 두 포인터, 행렬

상자의 측면도를 나타내는 문자 상자의 m x n 행렬이 제공됩니다. 상자의 각 셀은 다음 중 하나입니다.

• 돌 '#'
• 고정 장애물 '*'
• 비어 있는 '.'

상자가 시계 방향으로 90도 회전하여 중력으로 인해 일부 돌이 떨어집니다. 각 돌은 장애물, 다른 돌 또는 상자 바닥에 닿을 때까지 아래로 떨어집니다. 중력은 장애물의 위치에 영향을 주지 않습니다, 상자 회전의 관성은 돌의 수평 위치에 영향을 주지 않습니다

상자 안의 각 돌이 장애물, 다른 돌 또는 상자 바닥에 놓여 있다는 것이 보장됩니다.

위에서 설명한 회전 후 상자를 나타내는 n x m 행렬을 반환합니다.

예 1:

• 입력: 상자 = [["#",".","#"]]
• 출력: [["."], ["#"], ["#"]]

예 2:

• 입력: 상자 = [["#",".","","."], ["#","#","","."] ]
• 출력: [["#","."], ["#","#"], ["",""], [".",". "]]

예 3:

• 입력: 상자 = [["#","#","",".","","."], ["#","#", "#","*",".","."], ["#","#","#",".","#","."]]
• 출력: [[".","#","#"], [".","#","#"], ["#","#"," "], ["#","","."], ["#",".","*"], ["#",".","."]]

제약조건:

• m == 상자.길이
• n == 상자[i].길이
• 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)를 사용하여 다음 돌이 떨어질 위치를 추적하세요.
   • 돌(#)이 나타나면 이를 빈 슬롯으로 옮긴 후 빈 슬롯을 감소시킵니다.
   • 장애물(*)이 발견되면 빈 슬롯을 장애물 직전 위치로 재설정하세요.

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에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 상자 회전하기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!