2807. Fügen Sie den größten gemeinsamen Teiler in die verknüpfte Liste ein
Schwierigkeit:Mittel
Themen: Verlinkte Liste, Mathematik, Zahlentheorie
Gegeben ist der Kopf einer verknüpften Liste, in der jeder Knoten einen ganzzahligen Wert enthält.
Fügen Sie zwischen jedem Paar benachbarter Knoten einen neuen Knoten mit einem Wert ein, der dem größten gemeinsamen Teiler dieser Knoten entspricht.
Gib die verknüpfte Liste nach dem Einfügen zurück.
Der größte gemeinsame Teiler zweier Zahlen ist die größte positive ganze Zahl, die beide Zahlen gleichmäßig teilt.
Beispiel 1:
Beispiel 2:
Beispiel 3:
Einschränkungen:
Hinweis:
Lösung:
Wir müssen Knoten zwischen jedem Paar benachbarter Knoten in einer verknüpften Liste einfügen. Der Wert des eingefügten Knotens sollte der größte gemeinsame Teiler (GCD) der Werte der beiden benachbarten Knoten sein. Wir durchlaufen die verknüpfte Liste, berechnen den GCD für jedes Paar benachbarter Knoten und fügen dann den neuen Knoten entsprechend ein.
So können Sie das angehen:
Lassen Sie uns diese Lösung in PHP implementieren: 2807. Fügen Sie den größten gemeinsamen Teiler in die verknüpfte Liste ein
<?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>
Erläuterung:
</h3>
<ol>
<li><p><strong>ListNode-Klasse</strong>: Diese Klasse stellt die Struktur eines Knotens in der verknüpften Liste dar, mit Eigenschaften für den Wert ($val) und den nächsten Knoten ($next).</p></li>
<li><p><strong>GCD-Berechnung</strong>: Die GCD-Funktion verwendet den euklidischen Algorithmus, um den größten gemeinsamen Teiler zweier Ganzzahlen zu berechnen.</p></li>
<li>
<p><strong>Hauptlogik (insertGreatestCommonDivisors)</strong>:</p>
<ul>
<li>Wir durchlaufen die verknüpfte Liste, bis wir den vorletzten Knoten erreichen.</li>
<li>Für jedes Paar benachbarter Knoten berechnen wir den GCD ihrer Werte.</li>
<li>Wir erstellen einen neuen Knoten mit diesem GCD-Wert und fügen ihn zwischen dem aktuellen Knoten und dem nächsten Knoten ein.</li>
</ul>
</li>
<li><p><strong>Randfall</strong>: Wenn die Liste nur einen Knoten hat, geben wir sie unverändert zurück, ohne Änderungen vorzunehmen, da es keine benachbarten Knoten gibt.</p></li>
<li><p><strong>Testen</strong>: Die Funktion printList ist eine Hilfsfunktion, mit der die Werte der verknüpften Liste zur Überprüfung ausgegeben werden.</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:
Das obige ist der detaillierte Inhalt vonFügen Sie den größten gemeinsamen Teiler in die verknüpfte Liste ein. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
