给定字符串中由连续数字组成的数字之和
问题陈述
我们给定一个字符串 str,其中包含数字和字母字符。我们需要找到给定字符串中所有由连续数字序列表示的数字的总和。
示例
输入
str = “12were43”
输出
55
解释
12 和 43 的和等于 55。
输入
str = “1a2c3d”
输出
6
解释
1、2 和 3 的和是 6。
输入
str = “werderfrewsf”
输出
0
解释
由于字符串不包含任何数字,因此输出为 0。
我们解决问题的逻辑是从给定的字符串中提取所有数字并求和。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
方法 1
在这种方法中,我们将使用 isDigit() 方法来检查当前字符是否为数字。此外,如果当前字符是数字,我们将当前数字的值乘以 10 并将当前字符添加到数字中。
算法
步骤 1 − 将“number”和“sum”变量初始化为零。
步骤 2 − 遍历字符串并使用 isDigit() 方法检查当前字符是否在 0-9 之间。
步骤 3 − 如果当前字符是数字,则将数字值乘以 10,并加上当前数字值。
步骤 4 − 如果当前字符不是数字,则将“number”变量的值添加到“sum”变量中,并将“number”变量的值更新为零。
步骤 5 − 循环迭代完成后,将“number”的值添加到“sum”变量中,并返回 sum 变量的值。
示例
#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; }
输出
The sum of consecutive digits in the given string is - 41
时间复杂度 − O(n),因为我们使用单个循环。
空间复杂度 − O(1),因为我们没有使用任何额外的空间。
方法 2
在这种方法中,我们使用字符的 ASCII 值来检查当前字符是否为数字。此外,我们将字符追加到“number”变量中,直到我们在字符串中获得数字,并使用 atoi() 方法从字符串中提取数字。
算法
步骤 1 − 定义“number”变量并将其初始化为空字符串。此外,定义“sum”变量并将其初始化为 0。
步骤 2 − 使用 for 循环遍历字符串并获取字符串的每个字符。
步骤 3 − 如果 c-'0' 大于或等于零且小于或等于 9,则表示当前字符为数字。
步骤 4 − 如果当前字符是数字,则将其追加到“number”字符串。
步骤 5 − 如果当前字符不是数字,则使用 c_str() 方法将数字字符串转换为字符数组,并将其作为 atoi() 方法的参数传递以将字符串转换为数字。此外,使用“”值更新数字字符串。
如果字符串可转换为数字,则 atoi() 方法返回一个数字;否则,它返回零。
步骤 6 − for 循环迭代完成后,再次使用 atoi() 方法将字符串转换为数字并将其添加到 sum 值中。
示例
#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; }
输出
The sum of consecutive digits in the given string is - 48
时间复杂度 − O(N)
空间复杂度 − O(1)
方法 3
在这种方法中,我们使用正则表达式查找数字的所有匹配项。之后,我们可以将字符串转换为数字并将其添加到 sum 变量中。
算法
步骤 1 − 定义正则表达式模式。
步骤 2 − 使用 regex_search() 方法查找数字字符串的匹配项。
步骤 3 − 使用 while 循环进行迭代,只要我们找到匹配项。
步骤 4 − 在 while 循环中,使用 stoi() 方法将字符串转换为数字并将其添加到 sum 变量中。
步骤 5 − 此外,使用 match().suffix() 方法更新字符串。因此,我们不会获得重复的匹配项。
示例
#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; }
输出
The sum of consecutive digits in the given string is - 0
时间复杂度 − O(N),因为正则表达式通过遍历字符串来查找匹配项。
空间复杂度 − O(1)
结论
我们学习了三种不同的方法来查找字符串中出现的连续数字的和。最后一种方法是代码最优化的,因为它使用了正则表达式。但是,对于初学者来说,使用正则表达式可能很困难。