La technique des deux pointeurs

Aloha, les gars. Aujourd’hui, nous aborderons les questions les plus fréquemment posées et résoudrons quelques problèmes en utilisant la technique des deux points.

Cette approche est largement utilisée dans les tâches d’entretien. Il est crucial de lire les modèles dans l’état du problème et de les utiliser pour le résoudre. Cette approche vise à créer des pointeurs à deux points, généralement des pointeurs rapides et lents. Après cela, selon l’état du problème, nous déplacerons les pointeurs rapides/lents.

Cette approche sera plus évidente avec un exemple. Notre première tâche :

Palindrome valide

Description

Une locution est un palindrome si, après avoir converti toutes les lettres majuscules en lettres minuscules et supprimé tous les caractères non alphanumériques, il lit la même chose vers l’avant et vers l’arrière. Les caractères alphanumériques comprennent les lettres et les chiffres.

Étant donné une chaîne sretour true si c’est un palindromeou false sinon.

Exemple 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Exemple 2 :

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Exemple 3 :

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Solution

Commençons par un exemple simple, aba. Sur la base de la description, nous devrions vérifier le début et la fin. Et s’ils sont identiques, nous devrions vérifier la paire suivante. Est-ce clair?

Et pour ce faire, nous pouvons ajouter deux pointeurs, début et fin. Pour passer à une autre paire, nous pouvons augmenter le pointeur de début et diminuer le pointeur de fin (start++, end--).

Mais dans notre chaîne, nous pouvons avoir des caractères spécifiques comme : ou *. Comment pouvons-nous le gérer? Nous pouvons ignorer ce personnage et avancer ou reculer. Pour une meilleure compréhension, si le caractère actuel sur le pointeur de début n’est pas une lettre ou un chiffre, nous devons l’augmenter (ou le diminuer pour le pointeur de fin).

Plongeons profondément dans la section de code :

Code

public boolean isPalindrome(String s) {
    if (s == null || s.isEmpty()) {
      return false;
    }
    if (s.length() == 1) {
      return true;
    }

    int start = 0;
    int end = s.length() - 1;
    s = s.toLowerCase();
    while (start < end) {
      char a = s.charAt(start);
      char b = s.charAt(end);
      if (!Character.isLetterOrDigit(a)) {
        start++;
        continue;
      }
      if (!Character.isLetterOrDigit(b)) {
        end--;
        continue;
      }

      if (a != b) {
        return false;
      }
      start++;
      end--;
    }
    return true;
}

Notre problème suivant est :

Two Sum II – Le tableau d’entrée est trié

Description

Donné un 1-indexé tableau d’entiers numbers c’est déjà triés par ordre non décroissanttrouver deux nombres tels qu’ils s’ajoutent à un certain target nombre. Soit ces deux nombres numbers[index₁] et numbers[index₂] où 1 <= index₁ < index₂ <= numbers.length.

Retour les indices des deux nombres, index₁ et index₂, ajouté par un sous forme de tableau d’entiers [index₁, index₂] de longueur 2.

Les tests sont générés de telle sorte qu’il y ait exactement une solution. Toi Peut-être pas utiliser le même élément deux fois.

Votre solution ne doit utiliser que de l’espace supplémentaire constant.

Exemple 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Exemple 2 :

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Exemple 3 :

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Solution

Nous savons que notre tableau de nombres est trié. Mais qu’est-ce que cela signifie? Cela signifie que numbers[0] < numbers[1] et ainsi de suite. Pouvons-nous l’utiliser? Bien sûr, nous pouvons préparer deux pointeurs, début et fin. Ensuite, nous pouvons vérifier la somme des éléments sur ces pointeurs. Comme numbers[start] + numbers[end]. Après cela, nous devrions analyser cette somme. Si nous avons une somme supérieure à la cible, nous devons l’augmenter. Et si notre somme est supérieure à l’objectif, nous devrions le réduire. C’est évident, non ? Pour augmenter la somme, nous devons avancer le pointeur de début et diminuer le pointeur de fin pour réduire la somme.

Code

public int[] twoSum(int[] numbers, int target) {
  int[] rez = new int[2];

  int start = 0;
  int end = numbers.length - 1;

  while (start < end) {
    int a = numbers[start];
    int b = numbers[end];
    if (a + b == target) {
      rez[0] = start + 1;
      rez[1] = end + 1;
      return rez;
    } else if (a + b > target) {
      end--;
    } else {
      start++;
    }
  }
  return rez;
}

Toutes nos félicitations. Vous savez maintenant comment trouver une somme dans un tableau trié.

Et notre dernier problème pour aujourd’hui est :

3Somme

Description

Étant donné un tableau d’entiers nums, renvoie tous les triplets [nums[i], nums[j], nums[k]] tel que i != j, i != ket j != ket nums[i] + nums[j] + nums[k] == 0.

Notez que l’ensemble de solutions ne doit pas contenir de triplets en double.

Exemple 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Exemple 2 :

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Exemple 3 :

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Solution

C’est un problème d’entrevue populaire. Et je vais vous montrer une solution avec deux pointeurs.

L’idée principale de cet algorithme est de vérifier tous les triplets disponibles et, selon le résultat, d’augmenter ou de diminuer la somme.

Tout d’abord, nous devons trier le tableau. Ensuite, je veux parcourir le tableau et obtenir l’élément un sur l’index i.

Ensuite, nous pouvons préparer deux éléments. Ainsi, le deuxième élément (pointeur de début) sera sur la position je + 1, et le troisième (pointeur de fin) sera sur la position longueur – 1. Ensuite, en fonction de la somme, nous pouvons déplacer les pointeurs de début/fin.

Code

public List<List<Integer>> threeSum(int[] nums) {
  if (nums.length < 3) {
    return new ArrayList<>();
  }

  Arrays.sort(nums);

  List<List<Integer>> rez = new ArrayList<>();

  for (int i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) {
      continue;
    }
    int start = i + 1;
    int end = nums.length - 1;

    while (start < end) {
      int threeSum = nums[i] + nums[start] + nums[end];

      if (threeSum == 0) {
        List<Integer> tmp = List.of(nums[i], nums[start], nums[end]);
        rez.add(tmp);
        // todo add while iteration
        while (start < end && nums[start] == nums[start + 1]) {
          start++;
        }
        while (end > start && nums[end - 1] == nums[end]) {
          end--;
        }
        start++;
        end--;

      } else if (threeSum > 0) {
        end--;
      } else {
        start++;
      }
    }
  }
  return rez;
}

Aussi, nous pouvons essayer de résoudre ce problème avec l’approche de hachage. Mais c’est un sujet pour un autre article.

La technique des deux pointeurs – DZone

Leave A Reply Cancel Reply