Erklärung des Zwei-Zeiger-Algorithmus

Ich möchte eine einfache und effektive Technik erläutern, die Sie in einem Vorstellungsgespräch beim Umgang mit Arrays, Strings, verknüpften Listen usw. anwenden können. Dadurch verbessern Sie auch Ihr grundlegendes Wissen über diese Daten Strukturen.

Beginnen wir mit der Theorie. Es gibt zwei häufige Anwendungsfälle dieses Algorithmus:

• links/rechts Das zentrale Konzept dieses Algorithmus besteht darin, zwei ganzzahlige Variablen zu haben, die sich von beiden Seiten einer Zeichenfolge oder eines Arrays bewegen. Normalerweise nennen die Leute es links und rechts. Die linke Seite bewegt sich vom Index 0 zur Länge 1, die rechte Seite ist das Gegenteil.

• langsame/schnelle Zeiger laufen in die gleiche Richtung, z. B. vom Anfang bis zum Ende, aber ein Zeiger läuft schneller als ein anderer. In diesem Fall werden Variablen normalerweise als langsam und schnell bezeichnet.

Algorithmen sind elementar, und der beste Weg, sie zu verstehen, besteht darin, sich einige Beispiele anzusehen.

Schauen wir uns zunächst einen Fall mit Links- und Rechtszeigern an. Hier ist ein einfaches Beispiel für ein Problem, das wir mit diesem Algorithmus lösen können. Das Ziel ist klar: Wir wollen ein Paar finden, dessen Summe einer bestimmten Zahl entspricht.
Der Brute-Force-Ansatz erzeugt verschachtelte Schleifen, aber die Chance, das Interview damit zu bestehen, ist gering.
Ein besserer Ansatz wäre, den Zwei-Zeiger-Algorithmus zu verwenden und in einer Schleife zu finden, dass er eine O(n)-Komplexität anstelle von O(n²) hat

const findPair = (arr, target) => {
    let left = 0;                 // Start with two pointers left from start, right, from the end
    let right = arr.length - 1;

    while (left < right) { // when pointers meet, finish loop
        const sum = arr[left] + arr[right];

        if (sum === target) {
            return [arr[left], arr[right]];  // Return the pair if we find the target sum
        } else if (sum < target) {
            left++;  // Move left pointer to the right if sum is less than target
        } else {
            right--;  // Move right pointer to the left if sum is greater than target
        }
    }

    return null;  // Return null if no such pair exists
}

const arr = [1, 2, 3, 4, 6];
const target = 6;

findPair(arr, target);  // Output: [2, 4]

Lassen Sie uns zu einem Ansatz wechseln, bei dem Zeiger unterschiedliche Geschwindigkeiten haben. Es ist ein häufiges Problem, auf das man in einem Vorstellungsgespräch stoßen kann. Sie müssen die Mitte der angegebenen verknüpften Liste finden.
Der Brute-Force-Ansatz ist nicht so schlimm wie das vorherige Beispiel, aber der Interviewer erwartet einen besseren.
Mit dem Zwei-Zeiger-Algorithmus lösen Sie dieses Problem mit einer Komplexität von O(n), wohingegen der Brute-Force-Ansatz O(2n) erfordert, wenn Sie zwei aufeinanderfolgende Schleifen verwenden.

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

const findMiddle = (head) => {
    if (!head) return null;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;           // Move slow pointer one step
        fast = fast.next.next;      // Move fast pointer two steps
    }

    return slow;  // Slow pointer will be at the middle
}

// Creating a linked list 1 -> 2 -> 3 -> 4 -> 5
const head = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
const node5 = new ListNode(5);

head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

findMiddle(head).value);  // Output: 3 (middle node)

Das obige ist der detaillierte Inhalt vonErklärung des Zwei-Zeiger-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!