Mindestanzahl an Zeichen, die entfernt werden müssen, um eine Binärzeichenfolge in aufsteigender Reihenfolge zu sortieren

在计算机科学中，字符串操作是一个重要的主题，涉及到拼接、子串、反转等操作。与字符串操作相关的一个常见问题是从二进制字符串中移除所有的0。在本文中，我们将讨论一种使用最少数量的非相邻对翻转来解决这个问题的算法。

问题陈述

给定一个二进制字符串，我们必须使用最少次数的非相邻对翻转来删除字符串中的所有 0。翻转被定义为选择两个相邻的字符并交换它们。换句话说，我们需要找到使字符串中全0到字符串末尾所需的最少翻转次数。

方法

我们可以使用贪心算法来解决这个问题。我们可以从字符串的左边开始，并跟踪我们翻转0到末尾的最后一个索引。对于每个遇到的0，我们将其与最后一个翻转的0交换位置，将其移动到字符串的末尾。如果遇到1，我们只需移动到下一个索引。

让我们详细看一下算法 -

• 将两个变量“lastFlipped”和“flipCount”分别初始化为 -1 和 0。

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

• 如果当前字符为“0”，则将其与索引“lastFlipped + 1”处的字符交换，并递增“lastFlipped”变量。

• 为每个交换操作增加“flipCount”变量。

• 遍历完成后，所有 0 将位于字符串末尾，“flipCount”将包含删除所有 0 所需的最小翻转次数。

示例

这是用于实现上述算法的C++代码 -

#include <iostream>
#include <string>

using namespace std;

int minNonAdjacentPairFlips(string s) {
   int lastFlipped = -1;
   int flipCount = 0;
   
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == '0') {
         swap(s[i], s[lastFlipped + 1]);
         lastFlipped++;
         flipCount++;
      }
   }
   
   return flipCount;
}

int main() {
   string s = "100101000";
   cout << "Binary String: " << s << endl;
   cout << "Minimum Non-adjacent Pair Flips: " << minNonAdjacentPairFlips(s) << endl;
   return 0;
}

输出

Binary String: 100101000
Minimum Non-adjacent Pair Flips: 6

测试用例的解释

我们以二进制字符串“100101000”为例。我们必须使用最少次数的非相邻对翻转来删除该字符串中的所有 0。

• 最初，"lastFlipped" 和 "flipCount" 分别被设置为 -1 和 0。

• 我们开始从左到右遍历字符串。

• 在索引1处，我们遇到了一个'0'。我们将其与索引"lastFlipped + 1"（即索引0）处的字符交换，并将"lastFlipped"增加到0。字符串变为"010101000"。"flipCount"增加到1。

• 在索引4处，我们遇到另一个'0'。我们将其与索引"lastFlipped + 1"（即索引1）处的字符进行交换，并将"lastFlipped"增加到1。字符串变为"011010000"。"flipCount"增加到2。

• 在索引5处，我们遇到了一个'1'。我们只需移动到下一个索引

结论

在本文中，我们讨论了一种使用最少次数的非相邻对翻转从二进制字符串中删除所有 0 的算法。该算法使用的方法是贪婪的，这使得它高效且易于实现。我们还提供了用于实现该算法的 C++ 代码以及示例测试用例。

这个问题也可以使用动态规划来解决，但贪心算法提供了一个更简单和更快的解决方案。该算法的时间复杂度为O(n)，其中n是二进制字符串的长度。

总之，最小非相邻对翻转算法是字符串操作中的一个有用工具，可以应用于各种情境。

Das obige ist der detaillierte Inhalt vonMindestanzahl an Zeichen, die entfernt werden müssen, um eine Binärzeichenfolge in aufsteigender Reihenfolge zu sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!