資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究給定二進位制字串中唯一索引 10 或 01 子字串的最大數量
在這個問題中，我們將計算使用給定二進位制字串可以形成的 10 和 01 對的最大數量。
為了解決這個問題，我們可以檢查使用相鄰字元可以形成多少個 10 和 01 對，並且兩個對不能共享任何字元。
問題陳述
我們給定一個二進位制字串 bin_str。我們需要計算僅使用相鄰字元可以形成的 10 和 01 對的最大數量。此外，我們可以將一個字元用於任何單個對。兩個對不能共享同一個字元。
示例
Input – bin_str = "1100101" Output – 3
解釋
我們可以在第 1 個（基於 0 的索引）索引處形成一個“10”對，並在第 3 個和第 5 個索引處形成 01 對。
Input – bin_str = "111111"; Output – 0
解釋
該字串包含全部“1”。因此，我們無法形成任何 10 或 01 對。
Input – bin_str = "101"; Output – 1
解釋
我們不能在兩個對中共享同一個字元。因此，我們只能形成 10 或 01 對。
方法 1
在這種方法中，我們將使用布林變數來跟蹤前一個字元是否與前一個對一起使用。因此，我們可以形成唯一的 10 和 01 對，而不會共享相鄰的字元。
此外，我們將計算不同相鄰字元的數量以獲得 01 和 10 對的數量。
演算法
步驟 1 - 初始化“cnt”為 0 以儲存對的數量，並將“isPrev”初始化為 true 以跟蹤前一個字元是否可用以形成對。
步驟 2 - 從第 1 個索引開始遍歷二進位制字串。
步驟 3 - 如果索引 p 和 p – 1 處的字元不同且“isPrev”為 true，則將“cnt”值加 1，因為我們找到了 01 或 10 的對。此外，將“isPrev”更新為 false，因為當前字元不可用於與下一個字元形成對。
步驟 4 - 否則，將“isPrev”更新為 true。
步驟 5 - 最後，返回“cnt”值。
示例
#include <bits/stdc++.h>
using namespace std;
int countPairs(string bin_str) {
// To store the count of pairs
int cnt = 0;
// To track whether we can use the previous character in the pair
bool isPrev = true;
// Iterate the string
for (int p = 1; p < bin_str.size(); p++) {
// Check whether adjacent characters are different and previous characters available to make a pair
if (bin_str[p] != bin_str[p - 1] && isPrev) {
// Current character gets used
isPrev = false;
cnt++;
} else {
// Make the current character free for the next pair
isPrev = true;
}
}
return cnt;
}
int main() {
string bin_str = "1100101";
cout << "The maximum number of 01 and 10 cnt is " << countPairs(bin_str);
return 0;
}
輸出
The maximum number of 01 and 10 cnt is 3
時間複雜度 - 遍歷字串需要 O(N)。
空間複雜度 - O(1)
我們已經計算了可以使用二進位制字串的相鄰字元形成的 10 和 01 對的數量。程式設計師可能會計算在給定二進位制字串中可以形成的 100 和 001 對的最大數量。在這種情況下，我們需要使用整型變數來檢查前兩個字元是否可用，而不是使用單個布林值。
95 次檢視
