Kit Temuduga: Tatasusunan - Tetingkap gelongsor.

Ini Semua Mengenai Corak!

Sebaik sahaja anda mempelajari corak, segala-galanya mula terasa sedikit lebih mudah! Jika anda seperti saya, anda mungkin tidak suka temu duga teknologi dan saya tidak menyalahkan anda—ia mungkin sukar.

Masalah tatasusunan ialah antara yang paling biasa anda hadapi semasa temu duga. Masalah ini selalunya melibatkan kerja dengan tatasusunan semula jadi:

const arr = [1, 2, 3, 4, 5];

Dan masalah rentetan, yang pada asasnya adalah tatasusunan aksara:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

Salah satu corak yang paling biasa untuk menyelesaikan masalah tatasusunan ialah tetingkap gelongsor.

Corak Tingkap Gelongsor

Corak tetingkap gelongsor melibatkan dua penunjuk yang bergerak ke arah yang sama—seperti tetingkap yang menggelongsor merentasi tatasusunan.

Bila Perlu Menggunakannya

Gunakan corak tetingkap gelongsor apabila anda perlu mencari sub-array atau sub-rentetan yang memenuhi syarat tertentu, seperti minimum, maksimum, terpanjang atau terpendek.

Peraturan 1: Jika anda perlu mencari sub-tatasusunan atau sub-rentetan dan struktur data ialah tatasusunan atau rentetan, pertimbangkan untuk menggunakan corak tetingkap gelongsor.

Contoh Mudah

Berikut ialah contoh asas untuk memperkenalkan konsep penunjuk dalam tetingkap gelongsor:

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l + 1;  // Right pointer

    while (r < arr.length) {
        console.log("left", arr[l]);
        console.log("right", arr[r]);
        l++;
        r++;
    }
}

SlidingWindow([1, 2, 3, 4, 5, 6, 7, 8]);

Perhatikan bahawa penunjuk kiri (L) dan kanan (R) tidak perlu bergerak pada masa yang sama, tetapi ia mesti bergerak ke arah yang sama.

Penunjuk kanan tidak akan lebih rendah daripada penunjuk kiri.

Mari teroka konsep ini dengan masalah temu duga yang sebenar.

Masalah Dunia Sebenar: Substring Terpanjang Tanpa Aksara Berulang

Masalah: Diberi rentetan s, cari panjang sub-rentetan terpanjang tanpa mengulang aksara.

Kata kunci: sub-rentetan, terpanjang (maksimum)

function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right < str.length; right++) {
        if (hash[str[right]] !== undefined && hash[str[right]] >= left) {
            left = hash[str[right]] + 1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left + 1);
    }

    return longest;
}

Jangan risau jika perkara ini kelihatan rumit—kami akan melaluinya sedikit demi sedikit.

let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5

Inti masalah ini ialah mencari terpanjang sub-rentetan tanpa aksara berulang.

Tetingkap Permulaan: Saiz 0

Pada permulaan, kedua-dua penunjuk kiri (L) dan kanan (R) berada di tempat yang sama:

let left = 0;

for (let right = 0; right < str.length; right++) {  // RIGHT POINTER

h e l l o w o r l d 
^
^
L
R

Dan kami mempunyai hash kosong (objek):

let hash = {};

Apa yang menarik tentang objek? Mereka menyimpan kunci yang unik, itulah yang kami perlukan untuk menyelesaikan masalah ini. Kami akan menggunakan cincang untuk menjejak semua aksara yang telah kami lawati dan menyemak sama ada kami pernah melihat aksara semasa sebelum ini (untuk mengesan pendua).

Dengan melihat rentetan, kita dapat mengetahui secara visual bahawa dunia ialah subrentetan terpanjang tanpa mengulang aksara:

h e l l o w o r l d 
          ^        ^   
          L        R

Ini mempunyai panjang 5. Jadi, bagaimana kita boleh sampai ke sana?

Mari kita pecahkan langkah demi langkah:

Keadaan Awal

hash = {}

h e l l o w o r l d 
^
^
L
R

Lelaran 1:

Pada setiap lelaran, kami menambah aksara di bawah penuding R pada peta cincang dan kenaikan:

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

Pada masa ini, tiada aksara berulang dalam tetingkap kami (h dan e):

hash = {h: 0}
h e l l o w o r l d 
^ ^
L R

Lelaran 2:

hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R

Kini, kami mempunyai tetingkap baharu: hel.

Lelaran 3:

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R

Di sinilah ia menjadi menarik: kami sudah mempunyai l dalam cincang kami dan R menunjuk ke l lain dalam rentetan. Di sinilah kenyataan if kami masuk:

if (hash[str[right]] !== undefined)

Jika cincang kami mengandungi huruf R yang ditunjuk, kami telah menemui pendua! Tetingkap sebelumnya (hel) adalah yang paling lama kami setakat ini.

Jadi, apa yang kita lakukan seterusnya? Kami mengecilkan tetingkap dari sebelah kiri dengan menggerakkan penunjuk L ke atas kerana kami telah memproses subrentetan kiri. Tetapi sejauh mana kita bergerak L?

left = hash[str[right]] + 1;

Kami memindahkan L ke hanya selepas pendua:

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R

Kami masih menambah pendua kami pada cincang, jadi L kini akan mempunyai indeks 3.

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

Keadaan Baharu: Lelaran 4

hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R

Lelaran 4 hingga 6

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R

Apabila R menunjuk ke pendua lain (o), kami mengalihkan L ke sejurus selepas o pertama:

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R

Kami meneruskan sehingga kami menemui pendua lagi l:

hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R

Tetapi perhatikan ia berada di luar tetingkap semasa! bermula dari w,

Peraturan 3: Abaikan sub-x yang Diproses

Apa-apa sahaja di luar tetingkap semasa adalah tidak relevan—kami telah memprosesnya. Kod utama untuk mengurus ini ialah:

if (hash[str[right]] !== undefined && hash[str[right]] >= left)

Syarat ini memastikan kami hanya mengambil berat tentang aksara dalam tetingkap semasa, menapis sebarang bunyi.

hash[str[right]] >= left

Kami menumpukan pada apa-apa yang lebih besar atau sama dengan penunjuk kiri

Lelaran Akhir:

hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R

Saya tahu ini adalah terperinci, tetapi memecahkan masalah kepada corak atau peraturan yang lebih kecil ialah cara paling mudah untuk menguasainya.

In Summary:

• Rule 1: Keywords in the problem (e.g., maximum, minimum) are clues. This problem is about finding the longest sub-string without repeating characters.
• Rule 2: If you need to find unique or non-repeating elements, think hash maps.
• Rule 3: Focus on the current window—anything outside of it is irrelevant.

Bonus Tips:

• Break down the problem and make it verbose using a small subset.
• When maximizing the current window, think about how to make it as long as possible. Conversely, when minimizing, think about how to make it as small as possible.

To wrap things up, here's a little challenge for you to try out! I’ll post my solution in the comments—it’s a great way to practice.

Problem 2: Sum Greater Than or Equal to Target

Given an array, find the smallest subarray with a sum equal to or greater than the target(my solution will be the first comment).

/**
 * 
 * @param {Array<number>} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Remember, like anything in programming, repetition is key! Sliding window problems pop up all the time, so don’t hesitate to Google more examples and keep practicing.

I’m keeping this one short, but stay tuned—the next article will dive into the two-pointer pattern and recursion (prepping for tree problems). It’s going to be a bit more challenging!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Resources:

Tech interview Handbook

leet code arrays 101

Atas ialah kandungan terperinci Kit Temuduga: Tatasusunan - Tetingkap gelongsor.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!