Rumah >pembangunan bahagian belakang >tutorial php >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:
Contoh 2:
Contoh 3:
Kekangan:
Petunjuk:
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:
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:
Atas ialah kandungan terperinci Masukkan Pembahagi Biasa Terhebat dalam Senarai Terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!