Modèle à deux pointeurs dans DSA

Salut ! Parlons de cette astuce intéressante appelée technique à deux points dans DSA. Ne vous inquiétez pas, je vais garder ça amusant et ajouter quelques visuels pour l'aider à rester. Prêt à plonger ?

Alors, c'est quoi cette histoire de deux points ?

Pensez-y comme à un jeu dans lequel vous avez deux joueurs (nous les appellerons des pointeurs) commençant de différents côtés d'un terrain (c'est votre tableau). Ils peuvent soit :

1. Courez l'un vers l'autre (un peu romantique, non ?)
2. Coursez dans la même direction (devenez compétitif !)
3. Faire leur propre truc (mode freestyle)

Cette technique vous aide à résoudre un tas de problèmes de manière très efficace sans écrire une tonne de boucles. Plutôt sympa, hein ?

Pourquoi devriez-vous vous en soucier ?

Eh bien, c'est comme un super pouvoir pour votre code :

• C'est rapide : résout les problèmes en O(n) au lieu de O(n²). Votre code va zoomer !
• C'est simple : moins de lignes, plus facile à comprendre.
• C'est flexible : fonctionne avec des tableaux, des chaînes et même des listes chaînées !

Regardons certains types de problèmes à deux points

1. Pointeurs se déplaçant les uns vers les autres

Imaginez que vous essayez de trouver deux nombres dans un tableau trié qui totalisent une cible. C'est comme deux personnes courant l'une vers l'autre pour se rencontrer au milieu.

Voici un exemple JavaScript rapide :

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]

Imaginez les chiffres comme de jolis petits personnages alignés :
① ② ③ ④ ⑤

• Le pointeur gauche commence à ①
• Le pointeur droit commence à ⑤
• Ils se rapprochent lentement pour trouver le match parfait

2.C'est parfait pour vérifier si une chaîne est un palindrome. Imaginez deux amis commençant à la fin d'un mot, se dirigeant vers le milieu et se félicitant si tout correspond.

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

Imaginez deux fourmis rampant l'une vers l'autre sur le mot "voiture de course" :
r ≪-> r ?
un ≪-> un ?
c ≪-> c ?

Palindrome confirmé ! ?

Quelques applications intéressantes de cette technique :

1. Trouver une somme cible (comme nous l'avons fait ci-dessus)
2. Fusion de deux tableaux triés
3. Calcul de l'eau de pluie emprisonnée (Google celle-ci, c'est fascinant !)
4. Inverser les listes chaînées

Conseils de pro :

• Trier d'abord peut rendre ces problèmes beaucoup plus faciles
• Attention aux cas extrêmes (tableaux vides, doublons, valeurs extrêmes)
• Esquissez-le ! Dessiner le tableau ou la chaîne peut vous aider à éviter les bugs

Vous voulez passer au niveau supérieur ? Essayez ces défis :

1. Two Sum II - Le tableau d'entrée est trié (LeetCode 167)
2. Sous-chaîne la plus longue sans caractères répétitifs (LeetCode 3)
3. Palindrome valide (LeetCode 125)
4. Pièger l'eau de pluie (LeetCode 42) - si vous vous sentez aventureux !

La technique des deux points est comme un couteau suisse pour le codage. C'est simple mais puissant, et avec un peu de pratique, vous l'utiliserez sans même y penser.

Vous avez des questions ou souhaitez partager vos solutions ? Laissez un commentaire ou faites-moi signe. Bon codage !

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!