Corak dua penunjuk dalam DSA

Hei! Mari kita sembang tentang helah hebat ini yang dipanggil teknik dua mata dalam DSA. Jangan risau, saya akan memastikan ia menyeronokkan dan melemparkan beberapa visual untuk membantu ia melekat. Bersedia untuk menyelam?

Jadi, apakah maksud dua mata ini?

Fikirkan ia seperti permainan di mana anda mempunyai dua pemain (kami akan memanggil mereka penunjuk) bermula pada bahagian yang berbeza dalam medan (itu susunan anda). Mereka boleh sama ada:

1. Berlari ke arah satu sama lain (agak romantik, kan?)
2. Berlumba ke arah yang sama (menjadi kompetitif!)
3. Lakukan perkara mereka sendiri (mod gaya bebas)

Teknik ini membantu anda menyelesaikan banyak masalah dengan sangat cekap tanpa menulis satu tan gelung. Agak kemas, ya?

Mengapa anda perlu mengambil berat tentangnya?

Nah, ia seperti kuasa besar untuk kod anda:

• Ia pantas: Menyelesaikan masalah dalam O(n) dan bukannya O(n²). Kod anda akan mengezum!
• Mudah sahaja: Kurang baris, lebih mudah difahami.
• Ia fleksibel: Berfungsi dengan tatasusunan, rentetan, malah senarai terpaut!

Jom lihat beberapa jenis masalah dua mata

1. Penunjuk Bergerak Ke Arah Satu Sama Lain

Bayangkan anda cuba mencari dua nombor dalam tatasusunan disusun yang menjumlahkan sehingga sasaran. Ia seperti dua orang berlari ke arah satu sama lain untuk bertemu di tengah.

Berikut ialah contoh JavaScript pantas:

function twoSumSorted(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) return [left, right];
        if (sum < target) left++;
        else right--;
    }
    return -1; // No pair found
}

console.log(twoSumSorted([1, 2, 3, 4, 6], 10)); // Output: [2, 4]

Gambar nombor sebagai watak kecil yang comel dalam satu baris:
① ② ③ ④ ⑤

• Penunjuk kiri bermula pada ①
• Penunjuk kanan bermula pada ⑤
• Mereka perlahan-lahan bergerak ke arah satu sama lain untuk mencari pasangan yang sempurna

2. Ini sesuai untuk menyemak sama ada rentetan ialah palindrom. Gambar dua rakan bermula di hujung perkataan, bergerak ke arah tengah dan bertegur sapa jika semuanya sepadan.

function isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right]) return false;
        left++;
        right--;
    }

    return true;
}

console.log(isPalindrome("racecar")); // Output: true
console.log(isPalindrome("hello"));   // Output: false

Bayangkan dua semut merangkak ke arah satu sama lain pada perkataan "kereta lumba":
r <-> r ?
a <-> a ?
c <-> c ?

Palindrom disahkan! ?

Beberapa aplikasi hebat teknik ini:

1. Mencari jumlah sasaran (seperti yang kami lakukan di atas)
2. Menggabungkan dua tatasusunan yang diisih
3. Mengira air hujan yang terperangkap (Google yang ini, memang menarik!)
4. Menterbalikkan senarai terpaut

Petua pro:

• Isih dahulu boleh memudahkan masalah ini
• Berhati-hati dengan kes tepi (tatasusunan kosong, pendua, nilai ekstrem)
• Lakarkan! Melukis tatasusunan atau rentetan boleh membantu anda mengelakkan pepijat

Nak naik level? Cuba cabaran ini:

1. Dua Jumlah II - Tatasusunan Input Diisih (LeetCode 167)
2. Subrentetan Terpanjang Tanpa Aksara Berulang (LeetCode 3)
3. Palindrom Sah (LeetCode 125)
4. Memerangkap Air Hujan (LeetCode 42) - jika anda berasa mencabar!

Teknik dua mata adalah seperti pisau Swiss Army untuk pengekodan. Ia mudah tetapi berkuasa, dan dengan beberapa latihan, anda akan menggunakannya tanpa berfikir.

Ada soalan atau ingin berkongsi penyelesaian anda? Tinggalkan komen atau beri saya jeritan. Selamat mengekod!

Atas ialah kandungan terperinci Corak dua penunjuk dalam DSA. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!