数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究二进制字符串中移除所有 0 所需的最小非相邻对翻转次数
在二进制字符串中，翻转一对相邻位可以轻松地从字符串中移除一个 0。但是，当我们需要从二进制字符串中移除所有 0 时，我们可能也需要翻转非相邻位对。在本文中，我们将讨论如何确定从二进制字符串中移除所有 0 所需的最小非相邻对翻转次数。
算法
为了解决这个问题，我们将使用一个简单的贪心算法。其思想是始终选择彼此距离最远且至少有一个 0 在它们之间的一对位。然后，我们可以翻转这两个位，有效地从字符串中移除一个 0。我们重复此过程，直到所有 0 都被移除。
现在让我们用 C++ 实现此算法。
示例
#include <iostream>
#include <cstring>
using namespace std;
int main() {
string s;
s="100101000";
int n = s.size();
int cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
cnt++;
if (i+2 < n && s[i+2] == '0') {
i += 2;
}
else {
i++;
}
}
}
cout << cnt << endl;
return 0;
}
输出
3
代码解释
以上代码将二进制字符串作为输入，并计算从字符串中移除所有 0 所需的最小非相邻对翻转次数。现在让我们详细了解一下代码。
首先，我们将二进制字符串作为输入，并将其存储在字符串变量 's' 中。我们还将字符串的大小存储在整数变量 'n' 中。
string s; cin >> s; int n = s.size();
接下来，我们初始化一个变量 'cnt' 来存储字符串中 0 的计数。然后，我们使用 for 循环遍历字符串。对于遇到的每个 0，我们增加 0 的计数，并检查接下来的两位是否也是 0。如果是，我们通过将索引增加 2 来翻转位对。否则，我们仅通过将索引增加 1 来翻转相邻位对。
int cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
cnt++;
if (i+2 < n && s[i+2] == '0') {
i += 2;
}
else {
i++;
}
}
}
最后，我们输出从字符串中移除所有 0 所需的非相邻对翻转次数。
cout << cnt << endl;
测试用例示例
让我们考虑二进制字符串 "100101000"。可以使用上述算法计算从该字符串中移除所有 0 所需的最小非相邻对翻转次数。
首先，我们在位置 2 遇到一个 0。我们翻转对 (1,3) 以获得字符串 "110101000"。然后，我们在位置 5 遇到下一个 0。我们翻转对 (1,7) 以获得字符串 "111101000"。然后，我们在位置 8 遇到下一个 0。我们翻转对 (1,9) 以获得字符串 "111111000"。现在，所有 0 都已从字符串中移除。
从字符串中移除所有 0 所需的非相邻对翻转次数为 3。我们可以通过对输入字符串 "100101000" 运行上述 C++ 代码来验证这一点。
结论
在本文中，我们讨论了如何确定从二进制字符串中移除所有 0 所需的最小非相邻对翻转次数。我们使用了一个简单的贪心算法来解决此问题，并用 C++ 代码实现了它。我们还提供了一个示例测试用例来说明算法的工作原理。
158 次浏览
