백엔드 개발 PHP 튜토리얼 . 연결 목록을 여러 부분으로 분할

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

Sep 08, 2024 pm 12:31 PM

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

<?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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

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

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

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

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

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

11 최고의 PHP URL 쇼트너 스크립트 (무료 및 프리미엄) 11 최고의 PHP URL 쇼트너 스크립트 (무료 및 프리미엄) Mar 03, 2025 am 10:49 AM

11 최고의 PHP URL 쇼트너 스크립트 (무료 및 프리미엄)

Instagram API 소개 Instagram API 소개 Mar 02, 2025 am 09:32 AM

Instagram API 소개

Laravel의 플래시 세션 데이터로 작업합니다 Laravel의 플래시 세션 데이터로 작업합니다 Mar 12, 2025 pm 05:08 PM

Laravel의 플래시 세션 데이터로 작업합니다

Laravel Back End : Part 2, React가있는 React 앱 구축 Laravel Back End : Part 2, React가있는 React 앱 구축 Mar 04, 2025 am 09:33 AM

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

Laravel 테스트에서 단순화 된 HTTP 응답 조롱 Laravel 테스트에서 단순화 된 HTTP 응답 조롱 Mar 12, 2025 pm 05:09 PM

Laravel 테스트에서 단순화 된 HTTP 응답 조롱

PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법 PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법 Mar 14, 2025 am 11:42 AM

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

Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트 Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트 Mar 13, 2025 pm 12:08 PM

Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트

2025 PHP 상황 조사 발표 2025 PHP 상황 조사 발표 Mar 03, 2025 pm 04:20 PM

2025 PHP 상황 조사 발표

See all articles