資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查二進位制字串是否包含 A 對 0 和 B 個獨立的 0
檢查二進位制字串是否包含 A 對 0 和 B 個獨立的 0 是計算機科學中常見的問題，尤其是在演算法和資料結構領域。問題陳述非常簡單，並在密碼學、網路安全和機器學習等各個領域發揮著重要作用。
在本教程中，我們將討論使用 C++ 解決此問題的方法。我們將首先概述該方法，從定義問題陳述並提供一些示例開始，然後深入探討實現細節。所以讓我們開始吧！
問題陳述
給定一個長度為 n 的二進位制字串，由 0 和 1 組成，我們需要確定它是否包含 A 對相鄰的 0 (00) 和 B 個獨立的 0 (不與其他 0 相鄰的 0)。
示例
示例 1
Input: s = "100101000" A = 2 B = 1 Output: Yes
說明：在輸入字串中，有兩對相鄰的 0：“10|010|1000”。此外，還有一個獨立的 0：“100|1|01000”。因此，輸出為“Yes”，因為輸入字串包含兩對相鄰的 0 和一個獨立的 0。
示例 2
Input: s = "110010010" A = 3 B = 2 Output: No
說明：在輸入字串中，有三對相鄰的 0：“1|100|100|10”。但是，只有兩個獨立的 0：“1100|1|0010”。因此，輸出為“No”，因為輸入字串不包含兩個獨立的 0。
演算法
將 pairs 和 singles 計數器初始化為零。
使用迴圈遍歷輸入字串 s，索引 i 從 0 到 n-2。
檢查當前字元和下一個字元是否均為 '0'。
如果是，則將 pairs 加 1，並透過將 i 加 1 跳過下一個字元。
否則，檢查當前字元是否為 '0' 且下一個字元是否為 '1'。
如果是，則將 singles 加 1。
檢查 s 的最後一個字元是否為 '0'。
如果是，則將 singles 加 1。
如果 pairs 的數量大於或等於 A 且 singles 的數量大於或等於 B，則返回 true，否則返回 false。
示例
使用 C++ 實現上述演算法
在此實現中，我們定義了一個名為 'contains_zeros' 的函式，它接收一個二進位制字串 's' 和兩個整數 'A' 和 'B' 作為輸入。如果字串包含至少 'A' 對相鄰的零和 'B' 個獨立的零，則該函式返回 'true'；否則，它返回 'false'。
為了確定字串中 pairs 和 independent zeros 的數量，我們遍歷字串並跟蹤遇到的 pairs 和 independent zeros 的數量。如果我們找到一對相鄰的零，則跳過下一個字元。在迴圈結束時，我們檢查最後一個字元是否為零，並相應地增加 independent zeros 的計數。
最後，在 'main' 函式中，我們使用輸入字串 's' 和 'A' 和 'B' 的值呼叫 'contains_zeros'。如果函式返回 'true'，則列印“Yes”，否則列印“No”。
#include <iostream>
#include <string>
using namespace std;
bool contains_zeros(string s, int A, int B) {
int n = s.size();
int pairs = 0;
int singles = 0;
for (int i = 0; i < n - 1; i++) {
if (s[i] == '0' && s[i+1] == '0') {
pairs++;
i++; // Skip the next character
} else if (s[i] == '0' && s[i+1] == '1') {
singles++;
}
}
if (s[n-1] == '0') {
singles++;
}
return pairs >= A && singles >= B;
}
int main() {
string s = "100101000";
int A = 2;
int B = 1;
bool result = contains_zeros(s, A, B);
cout << "Input:" << endl;
cout << "s = \"" << s << "\"" << endl;
cout << "A = " << A << endl;
cout << "B = " << B << endl;
cout << endl;
cout << "Output:" << endl;
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
輸出
執行上述 C++ 程式將產生以下輸出
Input: s = "100101000" A = 2 B = 1 Output: Yes
結論
總之，我們討論瞭如何使用 C++ 程式檢查二進位制字串是否包含給定數量的 0 對和獨立的 0。我們提供了一個演算法並實現了一個函式，該函式以字串 's' 和兩個整數 'A' 和 'B' 作為輸入，並返回一個布林值，指示 's' 是否包含至少 'A' 對 0 和 'B' 個獨立的 0。
該演算法的時間複雜度為 O(n)，其中 n 是輸入字串 's' 的長度，因為我們需要遍歷 's' 一次以計算 pairs 和 singles 的數量。
91 次瀏覽
