Fügen Sie den größten gemeinsamen Teiler in die verknüpfte Liste ein

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:

• Eingabe: head = [18,6,10,3]
• Ausgabe: [18,6,6,2,10,1,3]
• Erklärung: Das 1.^erste Diagramm bezeichnet die anfängliche verknüpfte Liste und das 2.^nd Diagramm bezeichnet die verknüpfte Liste nach dem Einfügen der neuen Knoten (die Knoten in Blau sind die eingefügten). Knoten).
  • Wir fügen den größten gemeinsamen Teiler von 18 und 6 = 6 zwischen dem 1.^. und dem 2.^. Knoten ein.
  • Wir fügen den größten gemeinsamen Teiler von 6 und 10 = 2 zwischen dem 2^. und dem 3^rd Knoten ein.
  • Wir fügen den größten gemeinsamen Teiler von 10 und 3 = 1 zwischen dem 3^ten und dem 4^ten Knoten ein. Es gibt keine benachbarten Knoten mehr, daher geben wir die verknüpfte Liste zurück.

Beispiel 2:

• Eingabe: head = [7]
• Ausgabe: [7]
• Erklärung: Das 1.^erste Diagramm bezeichnet die anfängliche verknüpfte Liste und das 2.^nd Diagramm bezeichnet die verknüpfte Liste nach dem Einfügen der neuen Knoten. Es gibt keine Paare benachbarter Knoten, daher geben wir die anfängliche verknüpfte Liste zurück.

Beispiel 3:

• Eingabe: Kosten = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Ausgabe: 10

Einschränkungen:

• Die Anzahl der Knoten in der Liste liegt im Bereich [1, 5000].
• 1 <= Node.val <= 1000

Hinweis:

1. Jeder Punkt auf der linken Seite wäre entweder mit genau einem Punkt verbunden, der bereits mit einem linken Knoten verbunden ist, oder mit einer Teilmenge der Knoten auf der rechten Seite, die mit keinem Knoten verbunden sind
2. Verwenden Sie dynamische Programmierung mit Bitmaskierung, wo der Status sein wird (Anzahl der in der ersten Gruppe zugewiesenen Punkte, Bitmaske der in der zweiten Gruppe zugewiesenen Punkte).

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:

1. Definieren Sie eine ListNode-Klasse: Diese Klasse repräsentiert jeden Knoten in der verknüpften Liste.
2. Liste durchqueren: Wir durchlaufen die Liste, um jedes Paar benachbarter Knoten zu finden.
3. GCD-Knoten einfügen: Für jedes Paar benachbarter Knoten fügen wir einen neuen Knoten ein, dessen Wert der GCD der beiden benachbarten Knoten ist.
4. Geänderte Liste zurückgeben.

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:

• LinkedIn
• GitHub

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!