数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究二进制字符串中满足条件的三元组计数，条件是S[i]、S[j]和S[j]、S[k]的按位与运算结果相同。
二进制字符串是一种只包含二进制字符“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
在这个程序中，我们将使用蛮力方法获取所有三元组，然后检查每个三元组是否满足给定条件。
首先，我们将创建一个函数，该函数将接收一个参数（即给定的字符串），并返回所需的结果。
在函数中，我们将获取字符串的大小，然后使用嵌套循环遍历字符串并获取所有三元组。
我们将维护一个变量来存储计数，如果任何三元组满足给定条件，则我们将增加计数。
在主函数中，我们将调用该函数并打印结果。
示例
#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是给定字符串的大小。在这里，我们使用嵌套循环三次遍历字符串，这使得时间复杂度很高。
我们在这里没有使用任何额外的空间，这使得以上代码的空间复杂度为O(1)或常数。
方法2
在这种方法中，我们将使用前缀和后缀数组来存储零的计数，以降低时间复杂度。
我们将维护这些数组，并遍历给定字符串以获取结果。
在遍历过程中，如果字符串的当前索引为“0”，则我们将简单地添加当前索引号乘以剩余索引减1的结果。
如果当前索引值为“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])。我们实现了两个程序，一个是使用嵌套循环并使用蛮力查找所有三元组，另一个是通过维护前缀和后缀和并数学地找到结果。
97 次查看
