数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查二进制字符串是否包含 A 对 0 和 B 个独立的 0
检查二进制字符串是否包含 A 对 0 和 B 个独立的 0 是计算机科学中常见的问题，尤其是在算法和数据结构领域。问题陈述非常简单，并在密码学、网络安全和机器学习等各个领域发挥着重要作用。
在本教程中，我们将讨论使用 C++ 解决此问题的方法。我们将首先概述该方法，从定义问题陈述并提供一些示例开始，然后深入探讨实现细节。所以让我们开始吧！
问题陈述
给定一个长度为 n 的二进制字符串，由 0 和 1 组成，我们需要确定它是否包含 A 对相邻的 0 (00) 和 B 个独立的 0 (不与其他 0 相邻的 0)。
示例
示例 1
Input: s = "100101000" A = 2 B = 1 Output: Yes
说明：在输入字符串中，有两对相邻的 0：“10|010|1000”。此外，还有一个独立的 0：“100|1|01000”。因此，输出为“Yes”，因为输入字符串包含两对相邻的 0 和一个独立的 0。
示例 2
Input: s = "110010010" A = 3 B = 2 Output: No
说明：在输入字符串中，有三对相邻的 0：“1|100|100|10”。但是，只有两个独立的 0：“1100|1|0010”。因此，输出为“No”，因为输入字符串不包含两个独立的 0。
算法
将 pairs 和 singles 计数器初始化为零。
使用循环遍历输入字符串 s，索引 i 从 0 到 n-2。
检查当前字符和下一个字符是否均为 '0'。
如果是，则将 pairs 加 1，并通过将 i 加 1 跳过下一个字符。
否则，检查当前字符是否为 '0' 且下一个字符是否为 '1'。
如果是，则将 singles 加 1。
检查 s 的最后一个字符是否为 '0'。
如果是，则将 singles 加 1。
如果 pairs 的数量大于或等于 A 且 singles 的数量大于或等于 B，则返回 true，否则返回 false。
示例
使用 C++ 实现上述算法
在此实现中，我们定义了一个名为 'contains_zeros' 的函数，它接收一个二进制字符串 's' 和两个整数 'A' 和 'B' 作为输入。如果字符串包含至少 'A' 对相邻的零和 'B' 个独立的零，则该函数返回 'true'；否则，它返回 'false'。
为了确定字符串中 pairs 和 independent zeros 的数量，我们遍历字符串并跟踪遇到的 pairs 和 independent zeros 的数量。如果我们找到一对相邻的零，则跳过下一个字符。在循环结束时，我们检查最后一个字符是否为零，并相应地增加 independent zeros 的计数。
最后，在 'main' 函数中，我们使用输入字符串 's' 和 'A' 和 'B' 的值调用 'contains_zeros'。如果函数返回 'true'，则打印“Yes”，否则打印“No”。
#include <iostream>
#include <string>
using namespace std;
bool contains_zeros(string s, int A, int B) {
int n = s.size();
int pairs = 0;
int singles = 0;
for (int i = 0; i < n - 1; i++) {
if (s[i] == '0' && s[i+1] == '0') {
pairs++;
i++; // Skip the next character
} else if (s[i] == '0' && s[i+1] == '1') {
singles++;
}
}
if (s[n-1] == '0') {
singles++;
}
return pairs >= A && singles >= B;
}
int main() {
string s = "100101000";
int A = 2;
int B = 1;
bool result = contains_zeros(s, A, B);
cout << "Input:" << endl;
cout << "s = \"" << s << "\"" << endl;
cout << "A = " << A << endl;
cout << "B = " << B << endl;
cout << endl;
cout << "Output:" << endl;
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
输出
执行上述 C++ 程序将产生以下输出
Input: s = "100101000" A = 2 B = 1 Output: Yes
结论
总之，我们讨论了如何使用 C++ 程序检查二进制字符串是否包含给定数量的 0 对和独立的 0。我们提供了一个算法并实现了一个函数，该函数以字符串 's' 和两个整数 'A' 和 'B' 作为输入，并返回一个布尔值，指示 's' 是否包含至少 'A' 对 0 和 'B' 个独立的 0。
该算法的时间复杂度为 O(n)，其中 n 是输入字符串 's' 的长度，因为我们需要遍历 's' 一次以计算 pairs 和 singles 的数量。
91 次浏览
