. 연결 목록을 여러 부분으로 분할
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
힌트:
- 목록에 N개의 노드가 있고 k개의 부분이 있는 경우 모든 부분에는 N/k개의 요소가 있습니다. 단, 처음 N%k개의 부분에는 추가 요소가 있습니다.
해결책:
중요한 점은 각 부분의 노드 수가 1보다 커서는 안 된다는 것입니다. 이는 다음을 의미합니다.
- 연결리스트의 길이를 계산합니다.
- 각 부품의 최소 크기를 결정합니다(part_size = 길이 // k).
- 추가 노드를 처음 몇 부분에 균등하게 분배합니다(extra_nodes = 길이 % k). 첫 번째 extra_nodes 부분에는 각각 하나의 추가 노드가 있어야 합니다.
접근하다
- 길이 계산: 연결된 목록을 탐색하여 총 노드 수를 찾습니다.
-
각 부품의 크기 결정:
- 각 부분의 길이는 // k 노드 이상이어야 합니다.
- 첫 번째 길이 %k 부분에는 추가 노드가 하나 있어야 합니다.
-
목록 분할: 루프를 사용하여 연결된 목록을 k개 부분으로 분할합니다. 각 부분에 대해:
- 추가 노드가 있어야 하는 경우 part_size + 1 노드를 할당하세요.
- 그렇지 않은 경우 part_size 노드를 할당하세요.
- 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

뜨거운 주제











Laravel Back End : Part 2, React가있는 React 앱 구축

PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법
