排序二进制字符串所需删除的最小字符数，以使其按升序排列-C++-PHP中文网

排序二进制字符串所需删除的最小字符数，以使其按升序排列

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

问题陈述

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

方法

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

让我们详细看一下算法 -

将两个变量“lastFlipped”和“flipCount”分别初始化为 -1 和 0。
从左到右遍历二进制字符串。
如果当前字符为“0”，则将其与索引“lastFlipped + 1”处的字符交换，并递增“lastFlipped”变量。
为每个交换操作增加“flipCount”变量。
遍历完成后，所有 0 将位于字符串末尾，“flipCount”将包含删除所有 0 所需的最小翻转次数。

示例

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

#include  #include  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'。我们只需移动到下一个索引