C++ 给定数值字符串的所有前缀的和

在这个问题中，我们需要找到给定字符串的所有前缀的和。

最佳解决方案是遍历字符串的每个前缀并将它们相加以获得答案。

问题陈述 – 我们给出了一个名为num_Str的字符串，其中包含N个数字。我们需要找到给定字符串的所有前缀的和。

示例

输入

num_str = "1123"

输出

1247

说明 - 给定字符串的所有前缀为1、11、112和1123。所有前缀的和为1247。

输入

num_str = "1000"

输出

1111

解释 - 1 + 10 + 100 + 1000 = 1111

输入

num_str = "123456789";

输出

137174205

解释 - 1 + 12 + 123 + 1234 + 12345 + 123456 + 1234567 + 12345678 + 123456789 = 137174205

方法

在这种方法中，我们将获取字符串的每个前缀并将其和存储在一个变量中。在这里，我们将实现一个函数来求两个字符串的数字之和，从而得到较大字符串的和。

我们可以使用基本数学知识来求大字符串的和。

算法

步骤1 - 初始化’allPrefixSum’为’0’以存储所有前缀的和，将’prefix’初始化为空字符串以存储当前前缀。

步骤2 - 开始遍历字符串，并使用’+=’运算符将字符串的当前字符附加到’prefix’的末尾。

步骤3 - 执行twoDigitSum()函数将’prefix’的值加到’allPrefixSum’的值上，并将函数返回的值存储在’allPrefixSum’变量中。

步骤3.1 - 在twoDigitSum()函数中，num2的长度应大于num1的长度。如果不是，交换两个数字。

步骤3.2 - 初始化sum_Str字符串变量以存储num1和num2的和。

步骤3.3 - 将num1和num2字符串翻转，从第0个索引开始求和。在基本数学中，我们从末尾开始相加。

步骤3.4 - 将’car’变量初始化为0以存储进位。

步骤3.5 - 开始遍历num1字符串。从num1和num2的第pth个索引处取出字符，并将它们相加。还要将进位加到值上，并将最终值存储在sum中。

步骤3.6 - 执行sum % 10操作，并将其附加到sum_Str字符串中。在’car’中存储sum / 10。

步骤3.7 - 现在，将剩余的num2字符串转换。将第pth个索引处的字符加到’car’中，取其对10的模，然后附加到sum_str字符串中。还要通过sum/10更新’car’的值。

步骤3.8 - 如果’car’的值不为0，则将其附加到sum_Str字符串中。

步骤3.9 - 翻转sum_str值，并从函数中返回。

步骤4 - 最后，返回’allPrefixSum’变量的值。

示例

#include <bits/stdc++.h>
using namespace std;

string twoDigitSum(string num1, string num2) {
   // We need num2's length larger
   if (num1.length() > num2.length())
      swap(num1, num2);
   // Stores resulting sum
   string sum_str = "";
   // Get size of strings
   int len1 = num1.length(), len2 = num2.length();
   // Reverse strings
   reverse(num1.begin(), num1.end());
   reverse(num2.begin(), num2.end());
   // variable to store car bit
   int car = 0;
   // Traverse num1
   for (int p = 0; p < len1; p++) {
      // Get the sum of digits at the pth index by adding the carry
      int sum = ((num1[p] - '0') + (num2[p] - '0') + car);
      // Update sum_str
      sum_str.push_back(sum % 10 + '0');
      // Update carry to use in the next step
      car = sum / 10;
   }
   // Need to add extra digits of len2
   for (int p = len1; p < len2; p++) {
      // Get the sum of digits, update sum_str, and carry
      int sum = ((num2[p] - '0') + car);
      sum_str.push_back(sum % 10 + '0');
      car = sum / 10;
   }
   // If carry is not 0, add it to sum_str
   if (car)
      sum_str.push_back(car + '0');
   // Reverse resultant string to get answer
   reverse(sum_str.begin(), sum_str.end());
   return sum_str;
}
string getPrefixSum(string num_str) {
   // To store the sum of prefixes
   string allPrefixSum = "0";
   // To store prefix
   string prefix = "";
   // Traverse the string
   for (int p = 0; p < num_str.length(); p++) {
      // Get prefix till pth index
      prefix += num_str[p];
      // Get prefix sum
      allPrefixSum = twoDigitSum(prefix, allPrefixSum);
   }
   // Return Answer
   return allPrefixSum;
}
int main() {
   string num_str = "1123";
   cout << "The sum of all prefixes of the given string is " << 
getPrefixSum(num_str);

   return 0;
}

输出

The sum of all prefixes of the given string is 1247

时间复杂度 - 每个字符串前缀的添加的时间复杂度为O(N*N)。

空间复杂度 - 存储字符串前缀的空间复杂度为O(N)。

在遍历字符串时，我们可以获得字符串的每个前缀。解决方案的主要逻辑部分是求和函数，用于获取两个字符串的数字的和。程序员可以尝试获取给定字符串的所有后缀的和。