檢查是否存在可以透過二進位制字串迴圈旋轉將最多 M 個 0 分隔開的任意一對連續的 1

---

檢查是否存在可以透過二進位制字串迴圈旋轉將最多 M 個 0 分隔開的任意一對連續的 1，這是計算機程式設計和二進位制操作中的一個常見問題。任務是確定給定的二進位制字串是否可以以迴圈方式旋轉，使得字串中任何一對連續的 1 可以最多由 M 個 0 分隔。這個問題出現在各種應用中，例如影像處理、資料壓縮和資訊檢索。

在本教程中，我們將深入探討這個問題的細節，並提供一個使用 C++ 的解決方案。我們將討論演算法方法和實現細節，以有效地解決這個問題，以及必要的程式碼片段和示例來說明解決方案。所以，讓我們深入研究並開始學習新知識！

問題陳述

給定長度為 N 的二進位制字串和一個整數 M，任務是檢查二進位制字串是否可以透過迴圈旋轉的方式，使得字串中任何一對連續的 1 最多可以由 M 個 0 分隔。

示例

示例 1

Input: Binary string: "100101", M = 2
Output: Yes

解釋：在給定的輸入中，二進位制字串是“100101”，M 的值為 2。如果我們將字串向右迴圈旋轉 2 位，我們將得到“011001”。現在，任何一對連續的 1，即“11”，最多由 2 個 0 分隔，滿足給定條件。因此，輸出為“Yes”。

示例 2

Input: Binary string: "110011", M = 1
Output: No

解釋：在給定的輸入中，二進位制字串是“110011”，M 的值為 1。如果我們以任何數量的位置迴圈旋轉字串，我們將無法將連續的 1“11”最多由 1 個 0 分隔，因為它們之間有兩個 0。因此，輸出為“No”。

演算法

步驟 1：從輸入中讀取二進位制字串和 M 的值。

步驟 2：初始化一個計數器變數來跟蹤遇到的連續 1 的數量。

步驟 3：從左到右迴圈遍歷二進位制字串。

步驟 4：如果當前字元是'1'，則遞增計數器。

步驟 5：如果當前字元是'0'，則檢查計數器是否大於 M。如果是，則返回“No”，因為連續的 1 不能最多由 M 個 0 分隔。

步驟 6：繼續迴圈直到二進位制字串結束。

步驟 7：迴圈結束後，檢查計數器是否大於 M。如果是，則返回“No”，因為在迴圈旋轉中連續的 1 不能最多由 M 個 0 分隔。

步驟 8：否則，返回“Yes”，因為連續的 1 可以最多由 M 個 0 分隔。

注意：在步驟 5 和 7 中，條件“計數器 > M”用於檢查連續的 1 是否最多可以由 M 個 0 分隔，因為計數器表示遇到的連續 1 的數量。

現在讓我們使用 C++ 和示例來理解上述演算法的實現。

示例

使用 C++ 實現上述演算法

在下面的程式中，我們定義了一個函式'checkConsecutiveOnes'，它接受二進位制字串和整數 M 作為輸入，如果連續的 1 可以最多由 M 個 0 分隔，則返回“Yes”，否則返回“No”。然後，我們使用兩個示例輸入測試該函式，並在程式本身中顯示輸出。

#include <iostream>
#include <string>
using namespace std;
// Function to check if consecutive 1s can be separated by at most M 0s
string checkConsecutiveOnes(string binaryStr, int M) {
    int counter = 0; // Counter for consecutive 1s
    // Loop through the binary string
    for (int i = 0; i < binaryStr.length(); i++) {
        if (binaryStr[i] == '1') {
            counter++; // Increment counter for consecutive 1s
        } else {
            if (counter > M) {
                return "No"; // Consecutive 1s cannot be separated by at most M 0s
            }
            counter = 0; // Reset counter for consecutive 1s
        }
    }    
    if (counter > M) {
        return "No"; // Consecutive 1s cannot be separated by at most M 0s
    }    
    return "Yes"; // Consecutive 1s can be separated by at most M 0s
}
int main() {
    // Test Example 1
    string binaryStr1 = "100101";
    int M1 = 2;
    cout << "Binary String: " << binaryStr1 << ", M: " << M1 << ", Output: " << checkConsecutiveOnes(binaryStr1, M1) << endl;
    // Test Example 2
    string binaryStr2 = "110011";
    int M2 = 1;
    cout << "Binary String: " << binaryStr2 << ", M: " << M2 << ", Output: " << checkConsecutiveOnes(binaryStr2, M2) << endl;
    return 0;
}

輸出

Binary String: 100101, M: 2, Output: Yes
Binary String: 110011, M: 1, Output: No

結論

總而言之，可以使用本教程中提供的演算法和 C++ 程式有效地解決檢查是否存在可以透過二進位制字串迴圈旋轉將最多 M 個 0 分隔開的任意一對連續的 1 的問題。透過仔細考慮連續的 1 和允許的最大 0 的數量，我們可以確定給定條件是否滿足。此解決方案可用於需要分析二進位制字串迴圈旋轉的各種應用程式，例如模式匹配或資料壓縮演算法。