极客笔记C++ 计算二进制字符串中满足条件的三元组数量
二进制字符串是一种只包含二进制字符（’0’和’1’）的字符串。给定一个二进制字符串，我们需要找到满足以下条件的三元组：前两个字符的按位“与”等于后两个字符的按位“与”。
数学上的表达式为：
对于 0 <= i < j < k < length (给定的字符串)：(s[i] & s[j]) (s[j] & s[k])
按位”与”操作在两位都为真时返回真，否则对于任何一位为假或两位都为假时返回假。
示例
输入
“01010”
输出
8
解释
对于索引为0的位置上的0，我们可以有以下三元组：(0, 1, 0)，(0, 1, 0)，(0, 0, 1)，(0, 1, 0)，(0, 0, 0)。
对于下一个位置上的1，我们可以有以下三元组：(1, 0, 1)，(1, 0, 0)。
对于下一个位置上的0，我们可以有以下三元组：(0, 1, 0)。
方法1
在这个程序中，我们将使用暴力法的方法来获取所有的三元组，然后我们将检查它们是否符合给定的条件。
- 首先，我们将创建一个函数，该函数将接受一个参数，即给定的字符串，并返回所需的结果。
-
在函数中，我们将获取字符串的大小，然后使用嵌套的for循环来遍历字符串并获取所有的三元组。
-
我们将维护一个变量来存储计数，如果任何一个三元组满足给定条件，则将增加计数。
-
在主函数中，我们将调用该函数并打印结果。
例子
#include <bits/stdc++.h>
using namespace std;
// function to get the required solution
int countTriplets(string str){
int len = str.size(); // getting the size of string
int ans = 0; // variable to store the count
// use nested three for loops to get all the triplets
for (int i = 0; i < len; i++){
int a = str[i] -'0'; // current bit
for (int j = i + 1; j < len; j++){
int b = str[j] - '0'; // current bit
for (int k = j + 1; k < len; k++){
int c = str[k] - '0'; // current bit
if((a & b) == (b & c)){
ans++; // increasing the count
}
}
}
}
return ans; // return the final count
}
int main(){
string str = "01010"; // given string
cout<<"The number of triplets in the given string is: " << countTriplets(str) << endl;
return 0;
}
输出
The number of triplets in the given string is: 8
时间和空间复杂度
上述代码的时间复杂度是O(N^3)，其中N是给定字符串的长度。在这里，我们使用嵌套的for循环对字符串进行了三次遍历，使得时间复杂度较高。
我们这里没有使用额外的空间，这使得上述代码的空间复杂度为O(1)或常数。
方法2
在这种方法中，我们将使用前缀和后缀数组来存储零的计数，以减少时间复杂度。
我们将维护这些数组，并遍历给定的字符串以获得结果。
在遍历过程中，如果字符串的当前索引是’0’，那么我们将简单地将当前索引乘以剩余索引的个数减一加到结果中。
如果当前索引值为’1’，那么我们将使用前缀*后缀和索引减去前缀乘以剩余元素减去后缀，这将给我们最终的答案。
示例
#include <bits/stdc++.h>
using namespace std;
// function to ge the required solution
int countTriplets(string str){
int len = str.size(); // getting size of string
int ans = 0; // variable to store the count
int prefix[len], suffix[len];
// traversing over the string to get the prefix array
prefix[0] = str[0] == '0';
for (int i = 1; i < len; ++i) {
prefix[i] = prefix[i-1] + (str[i] == '0');
}
// traversing over the string to get the suffix array
suffix[len-1] = str[len-1] == '0';
for (int i = len - 2; i >= 0; --i) {
suffix[i] = suffix[i+1] + (str[i] == '0');
}
// iterating over the string to get the final answer
for (int i = 1; i < len - 1; i++) {
if (str[i] == '0') {
ans += i * (len - i - 1);
}
else {
ans += prefix[i - 1] * suffix[i + 1];
ans += (i - prefix[i - 1]) * (len - i - 1 - suffix[i + 1]);
}
}
return ans; // return the final count
}
int main(){
string str = "01010"; // given string
cout<<"The number of triplets in the given string is: "<<countTriplets(str)<<endl;
return 0;
}
输出
The number of triplets in the given string is: 8
时间和空间复杂度
以上代码的时间复杂度为O(N)，其中N是给定字符串的长度。
在以上代码中，我们使用额外的数组来存储前缀和后缀的零的个数，使得空间复杂度为线性的O(N)。
结论
在本教程中，我们实现了一个程序，用于找出给定二进制字符串中满足以下条件的三元组的数量：对于0 <= i < j < k < length(给定字符串)：(s[i] & s[j]) (s[j] & s[k])。我们实现了两个程序，一个是通过嵌套的for循环暴力查找所有三元组，另一个是通过维护前缀和后缀和并通过数学方式找到结果。