Maison > interface Web > js tutoriel > le corps du texte

Kit d'entretien : Tableaux - Fenêtre coulissante.

WBOY
Libérer: 2024-09-05 17:35:25
original
1103 Les gens l'ont consulté

Tout est question de modèles !

Une fois que vous avez appris les modèles, tout commence à paraître un peu plus facile ! Si vous êtes comme moi, vous n'aimez probablement pas les entretiens techniques, et je ne vous en veux pas, ils peuvent être difficiles.

Les problèmes liés aux tableaux sont parmi les plus courants que vous rencontrerez lors des entretiens. Ces problèmes impliquent souvent de travailler avec des tableaux naturels :

const arr = [1, 2, 3, 4, 5];
Copier après la connexion

Et les problèmes de chaînes, qui sont essentiellement des tableaux de caractères :

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


Copier après la connexion

L'un des modèles les plus courants pour résoudre les problèmes de tableau est la fenêtre coulissante.

Modèle de fenêtre coulissante

Le modèle de fenêtre coulissante implique deux pointeurs qui se déplacent dans la même direction, comme une fenêtre glissant sur le tableau.

Quand l'utiliser

Utilisez le modèle de fenêtre coulissante lorsque vous avez besoin de trouver un sous-tableau ou une sous-chaîne qui satisfait à une certaine condition, comme être le minimum, le maximum, le plus long ou le plus court.

Règle 1 : Si vous avez besoin de trouver un sous-tableau ou une sous-chaîne et que la structure des données est un tableau ou une chaîne, envisagez d'utiliser le modèle de fenêtre coulissante.

Exemple simple

Voici un exemple basique pour introduire le concept de pointeurs dans une fenêtre coulissante :

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]);
Copier après la connexion

Notez que les pointeurs gauche (L) et droit (R) ne doivent pas nécessairement se déplacer en même temps, mais ils doivent se déplacer dans la même direction.

Interview Kit: Arrays - Sliding window.

Le pointeur droit ne sera jamais plus bas que le pointeur gauche.

Explorons ce concept avec un vrai problème d'entretien.

Problème du monde réel : sous-chaîne la plus longue sans caractères répétitifs

Problème : Étant donné une chaîne s, trouver la longueur de la sous-chaîne la plus longue sans répéter de caractères.

Mots clés : sous-chaîne, la plus longue (maximum)

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;
}
Copier après la connexion

Ne vous inquiétez pas si cela semble compliqué, nous le verrons petit à petit.

let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5
Copier après la connexion

Le cœur de ce problème est de trouver la sous-chaîne la plus longue sans répéter les caractères.

Fenêtre initiale : taille 0

Au départ, les pointeurs gauche (L) et droit (R) sont au même endroit :

let left = 0;

for (let right = 0; right < str.length; right++) {  // RIGHT POINTER
Copier après la connexion
h e l l o w o r l d 
^
^
L
R
Copier après la connexion

Et nous avons un hachage (objet) vide :

let hash = {};
Copier après la connexion

Qu’est-ce qu’il y a de génial dans les objets ? Ils stockent des clés uniques, ce qui est exactement ce dont nous avons besoin pour résoudre ce problème. Nous utiliserons le hachage pour suivre tous les personnages que nous avons visités et vérifier si nous avons déjà vu le caractère actuel (pour détecter les doublons).

En regardant la chaîne, nous pouvons dire visuellement que world est la sous-chaîne la plus longue sans répéter de caractères :

h e l l o w o r l d 
          ^        ^   
          L        R
Copier après la connexion

Ceci a une longueur de 5. Alors, comment y arriver ?

Décomposons-le étape par étape :

État initial

hash = {}

h e l l o w o r l d 
^
^
L
R
Copier après la connexion

Itération 1 :

À chaque itération, nous ajoutons le caractère sous le pointeur R à la carte de hachage et incrémentons :

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);
Copier après la connexion
Copier après la connexion

Actuellement, il n'y a pas de caractères répétitifs dans notre fenêtre (h et e) :

hash = {h: 0}
h e l l o w o r l d 
^ ^
L R
Copier après la connexion

Itération 2 :

hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R
Copier après la connexion

Maintenant, nous avons une nouvelle fenêtre : hel.

Itération 3 :

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R
Copier après la connexion

Voici où cela devient intéressant : nous avons déjà l dans notre hachage, et R pointe vers un autre l dans la chaîne. C'est là qu'intervient notre déclaration if :

if (hash[str[right]] !== undefined)
Copier après la connexion

Si notre hachage contient la lettre R vers laquelle pointe, nous avons trouvé un doublon ! La fenêtre précédente (hel) est la plus longue jusqu'à présent.

Alors, on fait quoi ensuite ? Nous réduisons la fenêtre de gauche en déplaçant le pointeur L vers le haut puisque nous avons déjà traité la sous-chaîne de gauche. Mais jusqu'où peut-on déplacer L ?

left = hash[str[right]] + 1;
Copier après la connexion

On déplace L juste après le doublon :

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R
Copier après la connexion

Nous ajoutons toujours notre double au hachage, donc L aura désormais un index de 3.

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);
Copier après la connexion
Copier après la connexion

Nouvel état : itération 4

hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R
Copier après la connexion

Itérations 4 à 6

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R
Copier après la connexion

Quand R pointe vers un autre doublon (o), on déplace L juste après le premier o :

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R
Copier après la connexion

Nous continuons jusqu'à ce que nous rencontrions un autre doublon 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
Copier après la connexion

Mais remarquez que c'est en dehors de la fenêtre actuelle ! à partir de w,

Règle 3 : Ignorer le sous-x traité

Tout ce qui se trouve en dehors de la fenêtre actuelle n'est pas pertinent : nous l'avons déjà traité. Le code clé pour gérer cela est :

if (hash[str[right]] !== undefined && hash[str[right]] >= left)
Copier après la connexion

Cette condition garantit que nous ne nous soucions que des caractères dans la fenêtre actuelle, en filtrant tout bruit.

hash[str[right]] >= left
Copier après la connexion

Nous nous concentrons sur tout ce qui est plus grand ou égal au pointeur gauche

Itération finale :

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
Copier après la connexion

Je sais que cela a été détaillé, mais décomposer les problèmes en modèles ou règles plus petits est le moyen le plus simple de les maîtriser.

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!
}

Copier après la connexion

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

source:dev.to
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!