Algoritma dua petunjuk dijelaskan

Saya ingin menerangkan teknik mudah dan berkesan yang boleh anda gunakan dalam temu bual apabila berurusan dengan Tatasusunan, Rentetan, Senarai Terpaut, dll. Ini juga akan meningkatkan pengetahuan asas anda tentang data ini struktur.

Mari kita mulakan dari teori. Terdapat dua kes penggunaan biasa algoritma ini:

• kiri/kanan Konsep pusat algoritma ini ialah mempunyai dua pembolehubah integer yang akan bergerak dari kedua-dua belah rentetan atau tatasusunan. Selalunya orang panggil kiri kanan. Kiri akan bergerak dari indeks 0 ke panjang — 1, dan kanan adalah sebaliknya.

• perlahan/cepat Penunjuk berjalan ke arah yang sama, mis., dari mula hingga akhir, tetapi satu penuding berjalan lebih laju daripada yang lain. Dalam kes ini, orang biasanya memanggil pembolehubah perlahan dan cepat.

Algoritma adalah asas, dan cara terbaik untuk memahaminya ialah dengan melihat beberapa contoh.

Mula-mula, mari kita lihat kes dengan penunjuk kiri dan kanan. Berikut ialah contoh asas masalah yang boleh kita selesaikan menggunakan algoritma ini. Matlamatnya jelas: kami ingin mencari pasangan yang jumlahnya akan sama dengan nombor tertentu.
Pendekatan brute force akan mencipta gelung bersarang, tetapi terdapat peluang yang rendah untuk lulus temu duga menggunakannya.
Pendekatan yang lebih baik ialah menggunakan algoritma dua penunjuk dan mencarinya dalam satu gelung untuk mempunyai kerumitan O(n) dan bukannya O(n²)

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]

Mari beralih kepada pendekatan yang penunjuk mempunyai kelajuan yang berbeza. Ia adalah masalah yang kerap anda boleh jumpa temuduga. Anda perlu mencari bahagian tengah Senarai Berpaut yang diberikan.
Pendekatan brute force tidak seteruk contoh sebelumnya, tetapi penemuduga mengharapkan pendekatan yang lebih baik.
Dengan algoritma dua penunjuk, anda akan menyelesaikan masalah ini dengan kerumitan O(n), manakala pendekatan brute force akan mengambil O(2n) jika anda menggunakan dua gelung berjujukan.

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)

Atas ialah kandungan terperinci Algoritma dua petunjuk dijelaskan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!