計算X:Y比例的0和1子字串

---

在這個問題中，我們將統計給定二進位制字串的子字串，這些子字串包含“0”和“1”字元的數量，且比例為X:Y。

樸素的方法是找到給定二進位制字串的所有子字串，統計“0”和“1”的數量，並檢查這些數量是否為X:Y比例。有效的方法使用字首和技術來解決問題。

問題陳述 - 我們給定一個長度為bin_len的二進位制字串。我們需要統計具有0和1的數量之比為X:Y的子字串。

示例

輸入

bin_str = "00111001100"; X = 2; Y = 3;

輸出

5

解釋 - 具有“1”和“0”之比為2:3的子字串為00111、01110、10011、11001和11100。

輸入

bin_str = "11111"; X = 2; Y = 3;

輸出

0

解釋 - 二進位制字串僅包含“1”。因此，無法找到包含“0”和“1”之比為2:3的子字串。

輸入

bin_str = "00100"; X = 2; Y = 1;

輸出

3

解釋 - 我們可以取001、010和100子字串。

方法1

在這種方法中，我們將使用兩個巢狀迴圈來找到二進位制字串的所有子字串。之後，我們將統計二進位制字串中“1”和“0”的數量。

如果以下條件對任何子字串都成立，則我們可以將該子字串考慮在答案中。

zeroCnt * Y == oneCnt * X

演算法

步驟1 - 將“ans”初始化為0，以儲存子字串的數量。

步驟2 - 使用for迴圈遍歷二進位制字串。另外，使用另一個迴圈獲取從當前索引開始的每個子字串。

步驟3 - 使用substr()方法獲取特定長度的子字串。

步驟4 - 將“zeroCnt”和“oneCnt”初始化為0，以儲存子字串中“1”和“0”的數量。

步驟5 - 使用第三個巢狀迴圈來統計“1”和“0”。如果當前字元為“1”，則遞增“oneCnt”。否則，遞增“ZeroCnt”。

步驟6 - 在第二個巢狀迴圈中，如果zeroCnt * Y == oneCnt * X為真，則將“ans”的值遞增1。

步驟7 - 最後，從函式返回“ans”值。

示例

#include <bits/stdc++.h>
using namespace std;

int subStrCnt(string &bin_str, int X, int Y) {
    int ans = 0;
    // Get all substrings of the binary string
    for (int p = 0; p < bin_str.length(); p++) {
        for (int q = 1; q <= bin_str.length() - p; q++) {
            string sub_str = bin_str.substr(p, q);
            // Counting the number of zeros and ones in the substring
            int zeroCnt = 0, oneCnt = 0;
            for (int p = 0; p < sub_str.length(); p++) {
                if (sub_str[p] == '0')
                    zeroCnt++;
                else
                    oneCnt++;
            }
            // Checking whether the count of zeros and ones in the X:Y ratio
            if (zeroCnt * Y == oneCnt * X)
                ans++;
        }
    }
    return ans;
}
int main() {
    string bin_str = "00111001100";
    int X = 2;
    int Y = 3;
    cout << "The total substrings having 0's and 1's in the ratio X:Y is " << subStrCnt(bin_str, X, Y);
    return 0;
}

輸出

The total substrings having 0's and 1's in the ratio X:Y is 5

時間複雜度 - O(N*N*N)，其中O(N*N)用於獲取所有子字串，O(N)用於統計子字串中的“1”和“0”。

空間複雜度 - O(N)用於儲存子字串。

方法2

在這種方法中，我們將“0”視為-Y，“1”視為-X。我們將根據“0”和“1”的數量找到-Y和X的和。如果和等於0，我們可以說我們找到了有效的子字串。

此外，我們將使用map資料結構來儲存字首和。每當我們第二次找到任何字首和值時，我們就可以獲取和為0的索引之間的子字串。

例如，二進位制字串為“00111001100”。我們在第0個和第5個索引處找到了相同的字首和。因此，我們可以獲取從第1個索引到第5個索引的子字串。

演算法

步驟1 - 初始化“binary”列表，以將二進位制字串轉換為-Y和X格式。

步驟2 - 遍歷字串。如果當前字元為“0”，則在列表中插入“-Y”。否則，在列表中插入“X”。

步驟3 - 定義“pref”map以儲存字首和作為鍵，以及其值的出現次數。

步驟4 - 另外，初始化“ans”以儲存子字串的數量，並將“sum”初始化為0以儲存字首和。

步驟5 - 開始遍歷字串。將binary[p]新增到sum中。

步驟6 - 如果“sum”為0，則將“ans”遞增1。

步驟7 - 如果sum鍵存在於map中，則將其值新增到“ans”中。

步驟8 - 將pref[sum]遞增1。

步驟9 - 返回“ans”值。

示例

#include <bits/stdc++.h>
using namespace std;

int subStrCnt(string &bin_str, int X, int Y) {
    vector<int> binary;
    for (auto ch : bin_str) {
        if (ch == '0') { 
            // Change '0' to -Y
            binary.push_back(-Y);
        } else { 
            // Change '1' to X
            binary.push_back(X);
        }
    }
    // To store prefix sum
    unordered_map<int, int> pref;
    int ans = 0;
    int sum = 0;
    // Traverse string
    for (int p = 0; p < binary.size(); p++) {
        // Add a current element to sum
        sum += binary[p];
        // When aX - bY = 0, we found the substring
        if (sum == 0)
            ans += 1;
        // When prefix sum exists, we add the value to ans
        if (pref.find(sum) != pref.end())
            ans += pref[sum];
        // Increment the count of prefix sum
        pref[sum] += 1;
    }
    return ans;
}
int main() {
    string bin_str = "00111001100";
    int X = 2;
    int Y = 3;
    cout << "The total substrings having 0's and 1's in the ratio X:Y is " << subStrCnt(bin_str, X, Y);
    return 0;
}

輸出

The total substrings having 0's and 1's in the ratio X:Y is 5

時間複雜度 - O(N)用於查詢字首和。

空間複雜度 - O(N)用於在map中儲存字首和。

最佳化後的方法有效地解決了問題，只需花費O(N)時間。但是，對於大型二進位制字串，它可能需要更多的空間。程式設計師可以嘗試解決問題，以找到在二進位制字串中具有相同數量的“0”和“1”的子字串。