. 연결 목록을 여러 부분으로 분할

725. 연결 목록을 여러 부분으로 분할

난이도:중

주제: 연결 목록

단일 연결 목록의 헤드와 정수 k가 주어지면 연결 목록을 k개의 연속 연결 목록 부분으로 나눕니다.

각 부분의 길이는 최대한 같아야 합니다. 두 부분의 크기가 둘 이상 달라서는 안 됩니다. 이로 인해 일부 부분이 null이 될 수 있습니다.

부분은 입력 목록에 나타나는 순서대로 이루어져야 하며, 먼저 발생한 부분은 항상 나중에 발생한 부분보다 크기가 크거나 같아야 합니다.

k개 부분의 배열을 반환합니다.

예 1:

• 입력: head = [1,2,3], k = 5
• 출력: [[1],[2],[3],[],[]]
• 설명:
  • 첫 번째 요소 출력[0]의 출력[0].val = 1, 출력[0].next = null입니다.
  • 마지막 요소인 출력[4]은 null이지만 ListNode로서의 문자열 표현은 []입니다.

예 2:

• 입력: head = [1,2,3,4,5,6,7,8,9,10], k = 3
• 출력: [[1,2,3,4],[5,6,7],[8,9,10]]
• 설명:
  • 입력은 최대 1의 크기 차이로 연속된 부분으로 분할되었으며, 앞부분이 뒷부분보다 크기가 더 큽니다.

제약조건:

• 목록의 노드 수는 [0, 1000] 범위에 있습니다.
• 0 <= Node.val <= 1000
• 1 <= k <= 50

힌트:

1. 목록에 N개의 노드가 있고 k개의 부분이 있는 경우 모든 부분에는 N/k개의 요소가 있습니다. 단, 처음 N%k개의 부분에는 추가 요소가 있습니다.

해결책:

중요한 점은 각 부분의 노드 수가 1보다 커서는 안 된다는 것입니다. 이는 다음을 의미합니다.

1. 연결리스트의 길이를 계산합니다.
2. 각 부품의 최소 크기를 결정합니다(part_size = 길이 // k).
3. 추가 노드를 처음 몇 부분에 균등하게 분배합니다(extra_nodes = 길이 % k). 첫 번째 extra_nodes 부분에는 각각 하나의 추가 노드가 있어야 합니다.

접근하다

1. 길이 계산: 연결된 목록을 탐색하여 총 노드 수를 찾습니다.
2. 각 부품의 크기 결정:
   • 각 부분의 길이는 // k 노드 이상이어야 합니다.
   • 첫 번째 길이 %k 부분에는 추가 노드가 하나 있어야 합니다.
3. 목록 분할: 루프를 사용하여 연결된 목록을 k개 부분으로 분할합니다. 각 부분에 대해:
   • 추가 노드가 있어야 하는 경우 part_size + 1 노드를 할당하세요.
   • 그렇지 않은 경우 part_size 노드를 할당하세요.
4. Null 부분: 목록이 k보다 짧으면 일부 부분이 비어 있습니다(null).

이 솔루션을 PHP로 구현해 보겠습니다. 725. 연결 목록을 여러 부분으로 분할

<?php
// Definition for singly-linked list.
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
 /**
 * @param ListNode $head
 * @param Integer $k
 * @return ListNode[]
 */
function splitListToParts($head, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Helper function to create a linked list from an array
function createLinkedList($arr) {
    $head = new ListNode($arr[0]);
    $current = $head;
    for ($i = 1; $i < count($arr); $i++) {
        $current->next = new ListNode($arr[$i]);
        $current = $current->next;
    }
    return $head;
}

// Helper function to print a linked list
function printList($head) {
    $result = [];
    while ($head !== null) {
        $result[] = $head->val;
        $head = $head->next;
    }
    return $result;
}

// Test case 1
$head = createLinkedList([1, 2, 3]);
$k = 5;
$result = splitListToParts($head, $k);
foreach ($result as $part) {
    print_r(printList($part));
}

// Test case 2
$head = createLinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
$k = 3;
$result = splitListToParts($head, $k);
foreach ($result as $part) {
    print_r(printList($part));
}
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li><p><strong>길이 계산</strong>: 먼저 연결 목록을 탐색하여 길이를 찾습니다.</p></li>
<li>
<p><strong>부품 결정</strong>:</p>

<ul>
<li>part_size를 길이 // k로 계산하여 각 부분이 가져야 하는 최소 크기를 제공합니다.</li>
<li>extra_nodes를 길이 % k로 계산하여 하나의 추가 노드가 있어야 하는 부품 수를 제공합니다.</li>
</ul>
</li>
<li>
<p><strong>목록 분할</strong>: k개 부분을 반복하고 목록을 분할합니다.</p>

<ul>
<li>각 부품에 대해 추가 노드가 필요한 경우 part_size + 1 노드를 할당하고, 그렇지 않으면 part_size를 할당합니다.</li>
<li>각 부분이 끝나면 나머지 목록에 대한 링크가 끊어집니다.</li>
</ul>
</li>
<li><p><strong>Null 부분 처리</strong>: 노드 수가 k보다 적으면 나머지 부분은 null(비어 있음)이 됩니다.</p></li>
</ol>

<h3>
  
  
  테스트 케이스
</h3>

<ul>
<li>
<strong>예 1</strong>:
</li>
</ul>

<pre class="brush:php;toolbar:false">   $head = [1,2,3]; $k = 5;
   Output: [[1],[2],[3],[],[]]

• 예 2:

   $head = [1,2,3,4,5,6,7,8,9,10]; $k = 3;
   Output: [[1,2,3,4],[5,6,7],[8,9,10]]

이 솔루션은 시간 복잡도가 (O(n + k))인 k 부분으로 연결된 목록을 효율적으로 분할합니다. 여기서 n은 목록의 길이입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 . 연결 목록을 여러 부분으로 분할의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!