Masukkan Pembahagi Biasa Terhebat dalam Senarai Terpaut

2807. Masukkan Pembahagi Biasa Terhebat dalam Senarai Terpaut

Kesukaran: Sederhana

Topik: Senarai Terpaut, Matematik, Teori Nombor

Diberikan kepala kepala senarai terpaut, di mana setiap nod mengandungi nilai integer.

Di antara setiap pasangan nod bersebelahan, masukkan nod baharu dengan nilai yang sama dengan pembahagi sepunya paling hebat daripadanya.

Kembalikan senarai terpaut selepas dimasukkan.

pembahagi sepunya terhebat bagi dua nombor ialah integer positif terbesar yang membahagi sama rata kedua-dua nombor.

Contoh 1:

• Input: kepala = [18,6,10,3]
• Output: [18,6,6,2,10,1,3]
• Penjelasan: Gambar rajah 1^st menandakan senarai terpaut awal dan gambar rajah 2^nd menandakan senarai terpaut selepas memasukkan nod baharu (nod berwarna biru dimasukkan nod).
  • Kami memasukkan pembahagi sepunya terbesar 18 dan 6 = 6 antara 1^st dan 2^nd nod.
  • Kami memasukkan pembahagi sepunya terbesar 6 dan 10 = 2 antara 2^nd dan 3^rd nod.
  • Kami memasukkan pembahagi sepunya terbesar 10 dan 3 = 1 antara 3^rd dan 4^th nod. Tiada lagi nod bersebelahan, jadi kami mengembalikan senarai terpaut.

Contoh 2:

• Input: kepala = [7]
• Output: [7]
• Penjelasan: Gambar rajah 1^st menandakan senarai terpaut awal dan gambar rajah 2^nd menandakan senarai terpaut selepas memasukkan nod baharu. Tiada pasangan nod bersebelahan, jadi kami mengembalikan senarai terpaut awal.

Contoh 3:

• Input: kos = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Output: 10

Kekangan:

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

Petunjuk:

1. Setiap titik di sebelah kiri sama ada akan disambungkan ke titik tepat yang telah disambungkan ke beberapa nod kiri, atau subset nod di sebelah kanan yang tidak disambungkan ke mana-mana nod
2. Gunakan pengaturcaraan dinamik dengan bitmasking, di mana keadaan akan berada (bilangan mata yang diberikan dalam kumpulan pertama, bitmask mata yang diberikan dalam kumpulan kedua).

Penyelesaian:

Kita perlu memasukkan nod antara setiap pasangan nod bersebelahan dalam senarai terpaut. Nilai nod yang dimasukkan hendaklah pembahagi sepunya (GCD) terbesar bagi dua nilai nod bersebelahan. Kami akan melintasi senarai terpaut, mengira GCD untuk setiap pasangan nod bersebelahan, dan kemudian memasukkan nod baharu dengan sewajarnya.

Begini cara anda boleh mendekati perkara ini:

1. Tentukan Kelas ListNode: Kelas ini akan mewakili setiap nod dalam senarai terpaut.
2. Lintas Senarai: Kami akan mengulangi senarai untuk mencari setiap pasangan nod bersebelahan.
3. Sisipkan Nod GCD: Untuk setiap pasangan nod bersebelahan, kami akan memasukkan nod baharu yang nilainya ialah GCD bagi dua nod bersebelahan.
4. Kembalikan senarai yang diubah suai.

Mari kita laksanakan penyelesaian ini dalam PHP: 2807. Masukkan Pembahagi Biasa Terhebat dalam Senarai Terpaut

<?php
// Definition for a singly-linked list node.
class ListNode {
    public $val = 0;
    public $next = null;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

/**
 * Function to calculate the GCD of two numbers.
 *
 * @param $a
 * @param $b
 * @return mixed
 */
function gcd($a, $b) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

/**
 * @param ListNode $head
 * @return ListNode
 */
function insertGreatestCommonDivisors($head) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to print the linked list for testing purposes.
 * 
 * @param $head
 * @return void
 */
function printList($head) {
    $current = $head;
    while ($current != null) {
        echo $current->val . " ";
        $current = $current->next;
    }
    echo "\n";
}

// Example usage:

// Create the linked list: 18 -> 6 -> 10 -> 3
$head = new ListNode(18);
$head->next = new ListNode(6);
$head->next->next = new ListNode(10);
$head->next->next->next = new ListNode(3);

// Insert GCD nodes.
$modifiedHead = insertGreatestCommonDivisors($head);

// Print the modified linked list.
printList($modifiedHead);

// Output should be: 18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3
?>




<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li><p><strong>Kelas ListNode</strong>: Kelas ini mewakili struktur nod dalam senarai terpaut, dengan sifat untuk nilai ($val) dan nod seterusnya ($seterusnya).</p></li>
<li><p><strong>Pengiraan GCD</strong>: Fungsi gcd menggunakan algoritma Euclidean untuk mengira pembahagi sepunya terbesar bagi dua integer.</p></li>
<li>
<p><strong>Logik Utama (masukkanGreatestCommonDivisors)</strong>:</p>

<ul>
<li>Kami mengulangi senarai terpaut sehingga kami mencapai nod kedua hingga terakhir.</li>
<li>Untuk setiap pasangan nod bersebelahan, kami mengira GCD nilainya.</li>
<li>Kami mencipta nod baharu dengan nilai GCD ini dan memasukkannya di antara nod semasa dan nod seterusnya.</li>
</ul>
</li>
<li><p><strong>Kes Tepi</strong>: Jika senarai hanya mempunyai satu nod, kami mengembalikannya seperti sedia ada tanpa membuat sebarang perubahan kerana tiada nod bersebelahan.</p></li>
<li><p><strong>Pengujian</strong>: Fungsi printList ialah fungsi pembantu yang digunakan untuk mengeluarkan nilai senarai terpaut untuk pengesahan.</p></li>
</ol>

<h3>
  
  
  Time Complexity:
</h3>

<ul>
<li>The time complexity of this solution is (O(n)), where (n) is the number of nodes in the linked list. Calculating the GCD for each adjacent pair takes constant time on average, and we perform a linear traversal of the list.</li>
</ul>

<h3>
  
  
  Example:
</h3>

<p>For the input list [18, 6, 10, 3], the output is:<br>
</p>

<pre class="brush:php;toolbar:false">18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Masukkan Pembahagi Biasa Terhebat dalam Senarai Terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!