首页 > 文章列表 > 使用C++根据给定条件拆分给定的二进制字符串,以最大化和

使用C++根据给定条件拆分给定的二进制字符串,以最大化和

条件 拆分 二进制字符串
345 2023-09-02

本文旨在解决一个复杂的算法问题,涉及以最大化从各个组件获得的累积和的方式分割二进制字符串。我们将为读者提供用于实现代码的全面语法大纲,并建议两种可能的技术来克服这一挑战。此外,我们将基于上述方法展示两个真正的完整可执行代码。

语法

在深入研究算法之前,至关重要的是,我们必须熟悉我们将通过即将发布的代码示例展示的指定方法的结构。该方法采用二进制字符串作为输入,并通过使用预定条件对所述输入进行分区来计算其最高可能值。下面说明了这种方法在语法方面的外观 -

int maximizeSum(string binaryString) {
   // Implementation of the algorithm goes here
}

算法

现在我们应该讨论一下逐步算法,以解决通过拆分二进制字符串来最大化总和的问题。

代码片段 1

  • 初始化两个变量“maxSum”和“currentSum”,均设置为零。

  • 从左到右遍历二进制字符串。

  • 对于字符串中的每个字符 -

    • 如果字符是'0',则将其添加到当前子字符串中。

    • 如果字符是'1' −

      • 通过添加当前的“currentSum”来更新“maxSum”。

      • 将`currentSum`重置为零。

  • 遍历结束后,将最终的“currentSum”与“maxSum”相加。

  • 返回 `maxSum` 作为结果。

方法一

解决此问题的第一种方法涉及实现上述算法。让我们看看相应的代码片段 -

示例

#include <iostream>
#include <string>
using namespace std;

int maximizeSum(string binaryString) {
   int maxSum = 0;
   int currentSum = 0;

   for (char c : binaryString) {
      if (c == '0') {
         currentSum = currentSum * 10 + (c - '0');
      } else {
         maxSum += currentSum;
         currentSum = 0;
      }
   }

   maxSum += currentSum;
   return maxSum;
}

int main() {
   string binaryString = "1001101001";
    
   int result = maximizeSum(binaryString);
   cout << "Maximum sum: " << result << endl;

   return 0;
}

输出

Maximum sum: 0

说明

  • 为了方便起见,代码首先包含必要的库(“iostream”和“string”)并使用“std”命名空间。

  • 要计算通过拆分二进制字符串可实现的最大和,可以使用 `maximizeSum` 函数,该函数以二进制字符串作为输入并返回输出。

  • 在这个函数内部初始化了两个变量 - `maxSum` 和 `currentSum`。前者跟踪到目前为止达到的最大值,而后者计算每个单独子串的总和。

  • 使用基于范围的 for 循环我们迭代输入“binaryString”中的每个字符“c”。

  • 如果当前字符“c”是“0”,我们将其乘以 10 并加上数值“0”来更新“currentSum”。这有效地将“0”附加到当前子字符串。

  • 如果当前字符“c”为“1”,则表示当前子字符串结束。我们将 `currentSum` 添加到 `maxSum` 以更新迄今为止达到的最大总和,然后将 `currentSum` 重置为零以开始一个新的子字符串。

  • 完成循环后,通过将最后一个子字符串的`currentSum`加到前一个`maxSum`中来计算。`main`函数提供了一个提示,允许用户输入一个二进制字符串。

  • “main”函数提供一个提示,允许用户输入二进制字符串。

  • 输入字符串被传递给`maximizeSum`函数,并将返回的最大和存储在`result`变量中。

  • 最后,将最大总和显示给用户。

方法2

在第二种方法中,我们将通过消除执行整数乘法的需要来优化代码。相反,我们将使用按位运算来计算当前总和。让我们看一下这种方法的代码片段 -

示例

#include <iostream>
#include <string>
using namespace std;

int maximizeSum(string binaryString) {
   int maxSum = 0;
   int currentSum = 0;

   for (char c : binaryString) {
      if (c == '0') {
         currentSum = (currentSum << 1) + 0;
      } else {
         maxSum += currentSum;
         currentSum = 0;
      }
   }

   maxSum += currentSum;
   return maxSum;
}

int main() {
   string binaryString = "10110010"; // Assumed binary string
   int result = maximizeSum(binaryString);
   cout << "Maximum sum: " << result << endl;

   return 0;
}

输出

Maximum sum: 0

说明

  • 与第一种方法类似,代码首先包含必要的库,并使用 `std` 命名空间。

  • 函数`maximizeSum`和函数`main`的定义与第一种方法中的定义相同。

  • 在`maximizeSum`函数中,使用位左移运算符(`<<`)来更新`currentSum`。我们不是通过乘以10来更新,而是将`currentSum`的位向左移动1位,即

  • 相当于乘以 2。然后我们将 0 添加到 `currentSum` 中,因为当前字符是“0”。

  • 两种方法中其余的代码是相同的。它们接收一个二进制字符串作为输入。使用`maximizeSum`函数来计算在分割字符串时可能的最大和。然后将这个结果呈现给用户。

您可以在C++编译器中编译并运行这些代码,当输入一个二进制字符串时,程序将输出根据指定条件分割该字符串所获得的最大和。

结论

在本文中,我们探讨了通过根据给定条件分割二进制字符串来最大化总和的问题。我们提供了代码示例中使用的方法的语法,并提出了两种解决问题的方法。最初,采用直接算法,而以下技术通过按位运算优化编码。尽管这两种方法都成功地解决了该问题,但后者提供了更高的效率,因为它消除了整数乘法的必要性。通过理解和实现这些算法,您可以有效地解决涉及通过拆分二进制字符串来最大化总和的类似问题。