나선형 매트릭스 IV

2326. 나선형 매트릭스 IV

난이도:중

주제: 배열, 연결 목록, 행렬, 시뮬레이션

행렬의 차원을 나타내는 두 개의 정수 m과 n이 주어졌습니다.

정수 연결 리스트의 헤드도 제공됩니다.

행렬의 왼쪽 위부터 시작하여 나선형 순서(시계 방향)으로 표시된 연결 목록의 정수를 포함하는 m x n 행렬을 생성합니다. . 남은 공백이 있으면 -1로 채웁니다.

생성된 행렬을 반환합니다.

예 1:

• 입력: m = 3, n = 5, 헤드 = [3,0,2,6,8,1,7,9,4,2,5,5,0]
• 출력: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
• 설명:
  • 위 다이어그램은 값이 행렬에 인쇄되는 방식을 보여줍니다.
  • 행렬의 나머지 공간은 -1로 채워져 있습니다.

예 2:

• 입력: m = 1, n = 4, 헤드 = [0,1,2]
• 출력: [[0,1,2,-1]]
• 설명:
  • 위 다이어그램은 값이 행렬의 왼쪽에서 오른쪽으로 인쇄되는 방식을 보여줍니다.
  • 행렬의 마지막 공백은 -1로 설정됩니다.

예 3:

• 입력: 비용 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• 출력: 10

제약조건:

• 1 5
• 1 5
• 목록의 노드 수는 [1, m * n] 범위에 있습니다.
• 0

힌트:

1. 먼저 -1로 채워진 m x n 행렬을 생성합니다.
2. 방향 벡터 ⟨di, dj⟩를 사용하여 (i, j)의 행렬 내에서 탐색합니다. (i, j)에서는 현재 방향으로 계속 나아갈 수 있는지 판단해야 합니다.
3. 계속 갈 수 없다면 방향 벡터를 시계 방향으로 90도 회전하세요.

해결책:

연결된 목록의 값으로 채우는 m x n 행렬의 나선형 순회를 시뮬레이션합니다. 해당 연결 목록 값이 없는 나머지 위치는 -1로 채워집니다.

솔루션의 구성은 다음과 같습니다.

1. 행렬 초기화: 먼저 -1로 초기화된 m x n 행렬을 만듭니다.
2. 방향 벡터: 오른쪽, 아래쪽, 왼쪽, 위쪽 방향을 순환하는 방향 벡터를 사용하여 나선형 이동을 제어할 수 있습니다. 이를 통해 나선형 방식으로 행렬을 탐색할 수 있습니다.
3. 연결된 목록 반복: 연결 목록을 탐색하여 나선형 순서로 행렬에 값을 배치합니다.
4. 경계 처리: 경계에 도달했는지 또는 이미 채워진 셀을 만났는지 확인합니다. 그렇다면 방향(시계방향)을 바꿔보겠습니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2326. 나선형 매트릭스 IV

<?php class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
/**
 * @param Integer $m
 * @param Integer $n
 * @param ListNode $head
 * @return Integer[][]
 */
function spiralMatrix($m, $n, $head) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Helper function to print the matrix (for debugging)
function printMatrix($matrix) {
    foreach ($matrix as $row) {
        echo implode(" ", $row) . "\n";
    }
}

// Example usage:
// Create the linked list: [3,0,2,6,8,1,7,9,4,2,5,5,0]
$head = new ListNode(3);
$head->next = new ListNode(0);
$head->next->next = new ListNode(2);
$head->next->next->next = new ListNode(6);
$head->next->next->next->next = new ListNode(8);
$head->next->next->next->next->next = new ListNode(1);
$head->next->next->next->next->next->next = new ListNode(7);
$head->next->next->next->next->next->next->next = new ListNode(9);
$head->next->next->next->next->next->next->next->next = new ListNode(4);
$head->next->next->next->next->next->next->next->next->next = new ListNode(2);
$head->next->next->next->next->next->next->next->next->next->next = new ListNode(5);
$head->next->next->next->next->next->next->next->next->next->next->next = new ListNode(5);
$head->next->next->next->next->next->next->next->next->next->next->next->next = new ListNode(0);

$m = 3;
$n = 5;

$matrix = spiralMatrix($m, $n, $head);
printMatrix($matrix);
?>

설명:

1. 행렬 초기화: 행렬은 -1로 초기화되므로 채워지지 않은 공간은 기본적으로 -1로 유지됩니다.

2. 나선형 운동:

   • 방향 벡터 dirs는 오른쪽, 아래, 왼쪽, 위의 네 방향으로의 움직임을 관리합니다.
   • dirIndex 인덱스는 현재 방향을 추적합니다. 한 방향으로 이동한 후 다음 위치를 계산하여 유효한지 확인합니다. 그렇지 않다면 방향을 바꿔보겠습니다.

3. 연결된 목록 탐색:

   • 나선형 순서에 따라 연결된 목록 노드를 탐색하여 행렬에 값을 하나씩 배치합니다.

4. 경계 및 방향 변경:

   • 잘못된 위치(경계를 벗어났거나 이미 채워짐)를 발견하면 방향을 90도 회전합니다(즉, 방향 벡터 변경).

시간 복잡도:

• 모든 셀을 한 번 탐색하므로 행렬을 채우는 데는 O(m * n)이 걸립니다. 따라서 시간 복잡도는 O(m * n)이며 이는 제약 조건을 고려하면 효율적입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

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

• 링크드인
• 깃허브

위 내용은 나선형 매트릭스 IV의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!