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

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. 연결 목록을 여러 부분으로 분할

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)); } ?> 
 설명: 
 
 
길이 계산: 먼저 연결 목록을 탐색하여 길이를 찾습니다.
 
 
부품 결정:
 
 
part_size를 길이 // k로 계산하여 각 부분이 가져야 하는 최소 크기를 제공합니다.
 
extra_nodes를 길이 % k로 계산하여 하나의 추가 노드가 있어야 하는 부품 수를 제공합니다.
 
 
 
 
목록 분할: k개 부분을 반복하고 목록을 분할합니다.
 
 
각 부품에 대해 추가 노드가 필요한 경우 part_size + 1 노드를 할당하고, 그렇지 않으면 part_size를 할당합니다.
 
각 부분이 끝나면 나머지 목록에 대한 링크가 끊어집니다.
 
 
 
Null 부분 처리: 노드 수가 k보다 적으면 나머지 부분은 null(비어 있음)이 됩니다.
 
 
 테스트 케이스 
 
 
 예 1: 
 
 
 $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 중국어 웹사이트의 기타 관련 기사를 참조하세요!