資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究統計可以透過替換“01”或“10”為1或0得到長度為1的子字串的數量
在這個問題中，我們將統計可以由替換‘10’和‘01’子字串為‘1’或‘0’字元得到的長度為1的子字串的數量。
當任何二進位制字串包含相同數量的‘0’和‘1’時，我們總是可以透過執行替換操作將其長度變為1。因此，問題可以透過查詢具有相同數量的‘0’和‘1’的子字串來解決。
問題陳述 − 我們給定一個名為 bin_str 的二進位制字串，長度為 bin_len。我們需要計算可以透過將‘10’或‘01’更改為‘1’或‘0’來得到長度為1的子字串的總數。
示例
輸入
bin_str = "01010";
輸出
6
解釋 − 子字串為 01、01、0101、10、10 和 1010。
輸入
bin_str = "01";
輸出
1
解釋 − 我們可以將 01 替換為 ‘1’ 或 ‘0’ 以使其長度為 1。
輸入
bin_str = "00000";
輸出
0
解釋 − 不存在任何子字串，經過替換後可以使其長度為 1。
方法 1
該問題可以透過統計具有相同數量的‘1’和‘0’的子字串的數量來解決。我們將找到字串的所有子字串，並統計字串中的‘1’和‘0’。如果‘1’和‘0’的計數相同，我們將把‘ans’加 1。
演算法
步驟 1 − 初始化 ‘cnt’ 為 0，以儲存有效子字串的數量。
步驟 2 − 同時，初始化 ‘cnt0’ 和 ‘cnt1’ 為 0，以儲存‘1’和‘0’的計數。
步驟 3 − 開始遍歷二進位制字串。
步驟 4 − 使用巢狀迴圈從索引 p 遍歷到最後一個索引。
步驟 5 − 如果當前字元是‘0’，則將 ‘cnt0’ 加 1。否則，將 ‘cnt1’ 加 1。
步驟 6 − 如果 cnt0 和 cnt1 相等，則將 ‘cnt’ 值加 1。
步驟 7 − 返回 ‘cnt’ 值。
示例
#include <bits/stdc++.h>
using namespace std;
int totalSubstrs(string &bin_str, int &bin_len) {
// To store a number of valid substrings
int cnt = 0;
// Couting number of substrings having equal 1's and 0's
for (int p = 0; p < bin_len; p++) {
// To store count of 1's and 0's in substring
int cnt0 = 0, cnt1 = 0;
for (int q = p; q < bin_len; q++) {
if (bin_str[q] == '0') {
cnt0++;
} else {
cnt1++;
}
// When the substring has an equal number of 0's and 1's
if (cnt0 == cnt1) {
cnt++;
}
}
}
return cnt;
}
int main() {
string bin_str = "01010";
int bin_len = bin_str.length();
cout << "The number of substrings according to the given problem statement is " << totalSubstrs(bin_str, bin_len);
return 0;
}
輸出
The number of substrings according to the given problem statement is 6
時間複雜度 − O(N*N)，遍歷二進位制字串的所有子字串。
空間複雜度 − O(1)，因為我們沒有使用任何額外的空間。
方法 2
在這種方法中，我們將使用字首和技術來統計具有相同數量的‘1’和‘0’的子字串的數量。我們將跟蹤每個索引處‘1’和‘0’計數的差值。
如果任何兩個索引處‘1’和‘0’計數的差值相同，我們可以取這兩個索引之間的子字串。
演算法
步驟 1 − 初始化 ‘cnt’ 和 ‘diff’ 為 0，以儲存有效子字串的數量和‘1’和‘0’計數的差值。
步驟 2 − 同時，初始化 ‘prefixSum’ 列表為 0，以儲存差值。
步驟 3 − 開始遍歷字串。如果當前字元是‘0’，則將 ‘diff’ 值加 1。否則，將 ‘diff’ 值減 1。
步驟 4 − 如果 ‘diff’ 為 ‘0’，則將 ‘cnt’ 加 1。
步驟 5 − 如果 ‘prefixSum’ 陣列中 ‘diff’ 索引處的值為大於 0，則將 prefixSum[diff] 加到 ‘cnt’ 中。
步驟 6 − 將 ‘prefixSum’ 列表中 ‘diff’ 索引處的值加 1。
步驟 7 − 返回 ‘cnt’ 值。
示例
#include <iostream>
#include <vector>
using namespace std;
int totalSubstrs(string bin_str, int bin_len) {
int cnt = 0;
int diff = 0; // To store the difference of count of 1's and 0's
vector<int> prefixSum(bin_len, 0);
for (char ch : bin_str) {
// For the '0' character
if (ch == '0') {
diff++;
} else if (ch == '1') {
// For '1' character
diff--;
}
if (diff == 0) {
// When the number of '0' and '1' are equal
cnt++;
}
if (prefixSum[diff] > 0) {
cnt += prefixSum[diff];
}
prefixSum[diff]++;
}
return cnt;
}
int main() {
string bin_str = "01010";
int bin_len = bin_str.length();
cout << "The number of substrings according to the given problem statement is - " << totalSubstrs(bin_str, bin_len);
return 0;
}
輸出
The number of substrings according to the given problem statement is 6
時間複雜度 − O(N)，獲取‘1’和‘0’計數差值的字首和。
空間複雜度 − O(N)，在 prefixSum 列表中儲存差值。
該問題類似於查詢具有相同數量的‘1’和‘0’的子字串。我們還使用了字首和技術透過在 prefix 陣列中儲存‘1’和‘0’計數的差值來解決問題。第二種方法是時間最佳化的，但對於較大的二進位制字串，它可能會佔用更多記憶體。
72 次瀏覽
