資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
