. Pisah Senarai Pautan dalam Bahagian

725. Pisah Senarai Terpaut dalam Bahagian

Kesukaran: Sederhana

Topik: Senarai Terpaut

Memandangkan ketua senarai terpaut tunggal dan integer k, bahagikan senarai terpaut kepada k bahagian senarai terpaut berturut-turut.

Panjang setiap bahagian hendaklah sama yang mungkin: tiada dua bahagian harus mempunyai saiz yang berbeza lebih daripada satu. Ini boleh menyebabkan sesetengah bahagian menjadi batal.

Bahagian tersebut hendaklah mengikut urutan kejadian dalam senarai input dan bahagian yang berlaku lebih awal hendaklah sentiasa mempunyai saiz yang lebih besar daripada atau sama dengan bahagian yang berlaku kemudian.

Kembalikan tatasusunan bahagian k.

Contoh 1:

• Input: kepala = [1,2,3], k = 5
• Output: [[1],[2],[3],[],[]]
• Penjelasan:
  • Output elemen pertama[0] mempunyai output[0].val = 1, output[0].seterusnya = null.
  • Output elemen terakhir[4] adalah nol, tetapi perwakilan rentetannya sebagai ListNode ialah [].

Contoh 2:

• Input: kepala = [1,2,3,4,5,6,7,8,9,10], k = 3
• Output: [[1,2,3,4],[5,6,7],[8,9,10]]
• Penjelasan:
  • Input telah dibahagikan kepada bahagian berturut-turut dengan perbezaan saiz paling banyak 1, dan bahagian yang lebih awal adalah saiz yang lebih besar daripada bahagian yang terkemudian.

Kekangan:

• Bilangan nod dalam senarai berada dalam julat [0, 1000].
• 0 <= Node.val <= 1000
• 1 <= k <= 50

Petunjuk:

1. Jika terdapat N nod dalam senarai dan k bahagian, maka setiap bahagian mempunyai N/k elemen, kecuali N%k bahagian pertama mempunyai satu tambahan.

Penyelesaian:

Pemerhatian utama ialah bilangan nod dalam setiap bahagian tidak boleh berbeza lebih daripada 1. Ini bermakna:

1. Kira panjang senarai terpaut.
2. Tentukan saiz minimum setiap bahagian (saiz_bahagian = panjang // k).
3. Agihkan nod tambahan secara sama rata pada beberapa bahagian pertama (extra_nodes = panjang % k). Bahagian extra_nodes pertama harus mempunyai satu nod tambahan setiap satu.

Pendekatan

1. Kira panjang: Lintas senarai terpaut untuk mencari jumlah bilangan nod.
2. Tentukan saiz setiap bahagian:
   • Setiap bahagian hendaklah mempunyai sekurang-kurangnya panjang // k nod.
   • Bagian % k panjang pertama harus mempunyai satu nod tambahan.
3. Bahagikan senarai: Gunakan gelung untuk membahagikan senarai terpaut kepada k bahagian. Untuk setiap bahagian:
   • Jika ia sepatutnya mempunyai nod tambahan, tetapkan saiz_bahagian + 1 nod.
   • Jika tidak, tetapkan nod saiz_bahagian.
4. Bahagian nol: Jika senarai lebih pendek daripada k, beberapa bahagian akan kosong (null).

Mari laksanakan penyelesaian ini dalam PHP: 725. Pisah Senarai Terpaut dalam Bahagian

<?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>
  
  
  Penjelasan:
</h3>

<ol>
<li><p><strong>Kira Panjang</strong>: Kami mula-mula melintasi senarai terpaut untuk mencari panjangnya.</p></li>
<li>
<p><strong>Tentukan Bahagian</strong>:</p>

<ul>
<li>Kami mengira saiz_bahagian sebagai panjang // k, yang memberikan saiz minimum yang sepatutnya ada pada setiap bahagian.</li>
<li>Kami mengira extra_nod sebagai panjang % k, yang memberikan bilangan bahagian yang sepatutnya mempunyai satu nod tambahan.</li>
</ul>
</li>
<li>
<p><strong>Bahagikan Senarai</strong>: Kami melingkari k bahagian dan membahagikan senarai:</p>

<ul>
<li>Untuk setiap bahagian, tetapkan saiz_bahagian + 1 nod jika ia sepatutnya mempunyai nod tambahan, jika tidak hanya saiz_bahagian.</li>
<li>Pada penghujung setiap bahagian, kami memutuskan pautan ke senarai yang lain.</li>
</ul>
</li>
<li><p><strong>Kendalikan Bahagian Null</strong>: Jika terdapat kurang nod daripada k, bahagian yang tinggal akan menjadi batal (kosong).</p></li>
</ol>

<h3>
  
  
  Kes Ujian
</h3>

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

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

• Contoh 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]]

Penyelesaian ini membahagikan senarai terpaut dengan cekap kepada k bahagian dengan kerumitan masa (O(n + k)), dengan n ialah panjang senarai.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci . Pisah Senarai Pautan dalam Bahagian. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!