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

WBOY
풀어 주다: 2024-09-08 12:31:03
원래의
729명이 탐색했습니다.

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

난이도:

주제:연결 목록

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

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

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

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

예 1:

. Split Linked List in Parts

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

예 2:

. Split Linked List in Parts

  • 입력: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)); } ?> 

설명:

  1. 길이 계산: 먼저 연결 목록을 탐색하여 길이를 찾습니다.

  2. 부품 결정:

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

    • 각 부품에 대해 추가 노드가 필요한 경우 part_size + 1 노드를 할당하고, 그렇지 않으면 part_size를 할당합니다.
    • 각 부분이 끝나면 나머지 목록에 대한 링크가 끊어집니다.
  4. 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:dev.to
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!