Maison  >  Article  >  développement back-end  >  Étant donné une chaîne, trouvez la somme des nombres consécutifs qu'elle contient

Étant donné une chaîne, trouvez la somme des nombres consécutifs qu'elle contient

王林
王林avant
2023-08-28 09:17:14703parcourir

Étant donné une chaîne, trouvez la somme des nombres consécutifs quelle contient

Énoncé du problème

Nous avons donné une chaîne str contenant les caractères numériques et alphabétiques. Nous devons trouver la somme de tous les nombres représentés par une séquence continue de chiffres disponibles dans la chaîne donnée.

Exemple Exemple

Entrée

str = “12were43”

Sortie

55

Explication

La somme de 12 et 43 est égale à 55.

Entrée

str = “1a2c3d”

Sortie

6

Explication

La somme de 1, 2 et 3 est 6.

Entrée

str = “werderfrewsf”

Sortie

0

Explication

Il donne 0 dans la sortie car la chaîne ne contient aucun chiffre.

Notre logique pour résoudre le problème est d'extraire tous les nombres de la chaîne donnée et de les additionner.

Méthode 1

Dans cette approche, nous utiliserons la méthode isDigit() pour vérifier si le caractère actuel est un chiffre. Nous multiplions également la valeur actuelle du nombre par 10 et ajoutons le caractère actuel au nombre si le caractère actuel est un chiffre.

Algorithme

  • Étape 1 - Initialisez les variables « nombre » et « somme » à zéro.

  • Étape 2 - Parcourez la chaîne et vérifiez que le caractère actuel est compris entre 0 et 9 à l'aide de la méthode isDigit().

  • Étape 3 - Si le caractère actuel est un nombre, multipliez la valeur numérique par 10 et ajoutez la valeur numérique actuelle.

  • Étape 4 - Si le caractère actuel n'est pas un nombre, ajoutez la valeur de la variable "nombre" à la variable "somme" et mettez à jour la valeur de la variable "nombre" à zéro.

  • Étape 5 - Une fois l'itération de la boucle terminée, ajoutez la valeur du « nombre » à la variable « somme » et renvoyez la valeur de la variable somme.

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to return the sum of the consecutive number present in the string
int getSumOfDigits(string str){
   // store the current number
   int number = 0;
   // Stores total sum
   int sum = 0;
   // Traverse the string
   for (auto &ch : str){
      // If the current character is between '0' and '9', append it to the number
      if (isdigit(ch)) {
         number = number * 10 + ch - '0';
      } else {
         // 	if the current character is not between '0' and '9', add 'number' to the sum and reset 'number'
         sum += number;
         number = 0;
      }
   }
   // if the number is greater than 0, add it to sum
   sum += number;
   return sum;
}
int main(){
   string str = "6we24er5rd6";
   cout << "The sum of consecutive digits in the given string is - " << getSumOfDigits(str);
   return 0;
}

Sortie

The sum of consecutive digits in the given string is - 41
  • Complexité temporelle - O(n) car nous n'utilisons qu'une seule boucle.

  • Complexité de l'espace − O(1) puisque nous n'utilisons aucun espace supplémentaire.

Approche 2

Dans cette approche, nous utilisons les valeurs ASCII du caractère pour vérifier si le caractère actuel est un chiffre. De plus, nous ajoutons des caractères à la variable 'number' jusqu'à ce que nous obtenions des chiffres dans la chaîne et utilisons la méthode atoi(). pour extraire le numéro de la chaîne.

Algorithme

  • Étape 1 - Définissez la variable 'number' et initialisez-la avec une chaîne vide. Définissez également la variable 'sum' et initialisez-la à 0.

  • Étape 2 - Utilisez la boucle for pour parcourir la chaîne et obtenir chaque caractère de la chaîne.

  • Étape 3 - Si c-'0' est supérieur ou égal à zéro et inférieur ou égal à 9, cela signifie que le caractère actuel est un nombre.

  • Étape 4 - Si le caractère actuel est un chiffre, ajoutez-le à la chaîne « numéro ».

  • Étape 5 - Si le caractère actuel n'est pas un chiffre, utilisez la méthode c_str() pour convertir la chaîne numérique en tableau de caractères et transmettez-la comme paramètre de la méthode atoi() pour convertir la chaîne en nombre . Mettez également à jour la chaîne numérique avec la valeur « ».

    La méthode atoi() renvoie un nombre si la chaîne est convertible en nombre ; sinon, elle renvoie zéro.

  • Étape 6 - Une fois l'itération de la boucle for terminée, utilisez à nouveau la méthode atoi() pour convertir la chaîne en nombre et l'ajouter à la valeur de la somme.

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to return the sum of the consecutive numbers present in the string
int getSumOfDigits(string str){
   string number = "";
   // to store the sum of all the consecutive numbers
   int sum = 0;
   // traverse the string
   for (char c : str){
      // if the current character is between 0 to 9
      if (c - '0' >= 0 && c - '0' <= 9){
         // append it to the number string
         number += c;
      }
      // if the current character is an alphabet
      else {
         // convert string to an array of characters and pass it to atoi() function
         sum += atoi(number.c_str());
         // reset temporary string to empty
         number = "";
      }
   }
   // if the number is greater than 0, add it to sum
   sum += atoi(number.c_str());
   return sum;
}
int main(){
   string str = "11aa32bbb5";
   cout << "The sum of consecutive digits in the given string is - " << getSumOfDigits(str);
   return 0;
}

Sortie

The sum of consecutive digits in the given string is - 48
  • Complexité temporelle - O(N)

  • Complexité spatiale − O(1)

Méthode 3

Dans cette méthode, nous utilisons des expressions régulières pour trouver les correspondances de tous les nombres. Après cela, nous pouvons convertir la chaîne en nombre et l'ajouter à la variable somme.

Algorithme

  • Étape 1 − Définissez le modèle regex.

  • Étape 2 - Utilisez la méthode regex_search() pour trouver la correspondance pour la chaîne numérique.

  • Étape 3 - Effectuez des itérations en utilisant une boucle while tant que nous trouvons des correspondances.

  • Étape 4 - Dans la boucle while, utilisez la méthode stoi() pour convertir la chaîne en nombre et ajoutez-la à la variable somme.

  • Étape 5 - Encore une fois, mettez à jour la chaîne en utilisant la méthode match().suffix(). De cette façon, nous n’obtiendrons pas de correspondances en double.

Exemple

#include <bits/stdc++.h>
using namespace std;
// Function to calculate the sum of the numbers found in the string
int getSumOfDigits(string str){
   // regex pattern to find the numbers in the string
   regex pattern("d+");
   smatch match;
   // variable to store the sum of the numbers
   int sum = 0;
   // using the regex_search() function to find the numbers
   while (regex_search(str, match, pattern)){
      // adding the numbers to the sum variable
      sum += stoi(match[0].str());
      // update the string
      str = match.suffix().str();
   }
   return sum;
}
int main(){
   // input alphanumeric string
   string str = "abc23@12";
   cout << "The sum of consecutive digits in the given string is - " << getSumOfDigits(str);
   return 0;
}

Sortie

The sum of consecutive digits in the given string is - 0
  • Complexité temporelle − O(N), car l'expression régulière trouve des correspondances en parcourant la chaîne.

  • Complexité spatiale − O(1)

Conclusion

Nous avons appris trois façons différentes de trouver la somme des nombres consécutifs dans une chaîne. La dernière méthode est le code le plus optimisé car elle utilise des expressions régulières. Cependant, travailler avec des expressions régulières peut être difficile pour les débutants.

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!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer