Corak Penyelesaian Masalah

Selamat datang kembali ke siri blog kami tentang penyelesaian masalah dalam kejuruteraan perisian moden!

Dalam Bahagian 1, kami meneroka Corak Kaunter Frekuensi, teknik yang berkuasa untuk mengoptimumkan algoritma dengan mengira kekerapan elemen dengan cekap. Jika anda terlepas atau mahukan penyegaran pantas, sila semak sebelum meneruskan.

Dalam bahagian ini, kita akan menyelami corak penting lain: Corak Multipointer. Corak ini tidak ternilai apabila berhadapan dengan senario di mana berbilang elemen perlu dibandingkan, dicari atau dilalui secara serentak. Mari terokai cara ia berfungsi dan tempat anda boleh menggunakannya untuk meningkatkan kecekapan kod anda.

02. Corak Multipointer

Corak Multipointer ialah teknik yang digunakan dalam reka bentuk algoritma di mana berbilang penunjuk (atau iterator) digunakan untuk melintasi struktur data seperti tatasusunan atau senarai terpaut. Daripada bergantung pada satu penunjuk atau gelung, corak ini menggunakan dua atau lebih penunjuk yang bergerak melalui data pada kelajuan yang berbeza atau dari titik permulaan yang berbeza.

Contoh Masalah

Tulis fungsi yang dipanggil sumZero yang menerima diisih tatasusunan integer. Fungsi harus mencari pasangan pertama di mana jumlahnya adalah sifar. Jika pasangan sedemikian wujud, kembalikan tatasusunan yang merangkumi kedua-dua nilai; jika tidak, kembalikan tidak ditentukan.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Penyelesaian Asas

function sumZero(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

Kerumitan Masa - O(N^2)

Penyelesaian menggunakan Corak Multipointer

langkah 1: Fahami masalahnya
Kita perlu mencari dua nombor dalam tatasusunan **diisih yang menambah hingga sifar. Memandangkan tatasusunan diisih, kami boleh memanfaatkan pesanan ini untuk mencari penyelesaian dengan lebih cekap.

langkah 2: Mulakan Dua Penunjuk
Sediakan dua penunjuk: satu (kiri) bermula pada permulaan tatasusunan, dan satu lagi (kanan) bermula pada penghujung.

Contoh:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5

Langkah 3: Kira Jumlah Nilai pada Penunjuk
Tambahkan nilai di penunjuk kiri dan kanan untuk mendapatkan jumlah

Sum = -4 + 5 = 1

Langkah 4: Bandingkan Jumlah dengan Sifar

• Jika jumlahnya lebih besar daripada sifar: Gerakkan penunjuk kanan satu langkah ke kiri untuk mengurangkan jumlah.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• Jika jumlahnya kurang daripada sifar: Gerakkan penunjuk kiri satu langkah ke kanan untuk menambah jumlah.

New Sum = -4 + 2 = -2
Sum is -2 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -3
Right Pointer (R): 2

Langkah 5: Ulangi Proses
Teruskan menggerakkan penunjuk dan mengira jumlahnya sehingga ia bertemu atau sepasang ditemui.

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -2
Right Pointer (R): 2

Jumlahnya ialah sifar, jadi fungsi mengembalikan [-2, 2].

Jika gelung selesai tanpa mencari pasangan sedemikian, kembalikan tidak ditentukan.

Kod Akhir

function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left++;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}

NOTA:
Kerumitan Masa: O(n) – Fungsi ini cekap dan berskala secara linear dengan saiz tatasusunan.
Kerumitan Angkasa: O(1) – Fungsi menggunakan jumlah minimum memori tambahan.

Kesimpulan

Corak Multipointer ialah teknik yang berkuasa untuk menyelesaikan masalah yang melibatkan pencarian, membandingkan atau memanipulasi elemen dalam struktur data yang diisih. Dengan menggunakan berbilang penunjuk yang bergerak ke arah satu sama lain, kami boleh meningkatkan kecekapan algoritma dengan ketara, mengurangkan kerumitan masa daripada O(n²) kepada O(n) dalam banyak kes. Corak ini serba boleh dan boleh digunakan untuk pelbagai masalah, menjadikannya strategi penting untuk mengoptimumkan prestasi dalam kod anda.

Nantikan siaran seterusnya kami, di mana kami akan menyelami Corak Tetingkap Gelongsor satu lagi alat penting untuk menangani masalah yang melibatkan segmen data dinamik. Ia adalah corak yang sangat berguna yang boleh membantu anda menyelesaikan cabaran yang lebih kompleks dengan mudah!

Atas ialah kandungan terperinci Corak Penyelesaian Masalah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!