資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中包含 K 個 1 的二進位制字串子字串計數
給定一個二進位制數字字串，即 0 和 1 的組合，以及一個整數 k，任務是計算由給定二進位制字串形成的、具有給定 k 個 1 的子字串的數量。
輸入 − 字串 str = ‘10000100000’，k = 2
輸出 − 包含 K 個 1 的二進位制字串的子字串數為 − 6
解釋 − 從給定字串可以形成的子字串有 1、10、100、1000、10000、010、100001、10001、1001、101、11、1000010。因此，有 6 個子字串包含 k 個 1，即正好 2 個 1。
輸入 − 字串 str = ‘10000100000’，k = 3
輸出 − 包含 K 個 1 的二進位制字串的子字串數為 − 0
解釋 − 我們給定一個整數 k 值為 3，如果我們檢查包含二進位制數字的字串，它只有 2 個 1。因此，不可能存在具有給定 k 個 1 的子字串。
下面程式中使用的方法如下
輸入一個包含 0 和 1 組合的二進位制數字字串和一個整數變數 k。
使用 length() 函式計算字串的長度，並將資料傳遞給函式以進行進一步處理。
宣告一個臨時變數 count 和 total 為 0，用於儲存包含 k 個 1 的子字串。
宣告一個數組，用於儲存大小為字串長度加一的 1 的頻率，並將其初始化為 0，並將陣列的第一個元素設定為 1。
從 0 到陣列長度開始迴圈 FOR
在迴圈內部，將 total 設定為 total + str[i] - ‘0’。檢查 IF total >= k，然後將 count 設定為 count + arr[total-k]。
返回 count
列印結果。
示例
#include <bits/stdc++.h>
using namespace std;
int sub_k_ones(string str, int length, int k){
int count = 0;
int total_1 = 0;
int arr_fre[length + 1] = {0};
arr_fre[0] = 1;
for (int i = 0; i < length; i++){
total_1 = total_1 + (str[i] - '0');
if (total_1 >= k){
count = count + arr_fre[total_1 - k];
}
arr_fre[total_1]++;
}
return count;
}
int main(){
string str = "10000100000";
int length = str.length();
int k = 2;
cout<<"Count of substrings of a binary string containing K ones are: "<<sub_k_ones(str, length, k) << endl;
return 0;
}輸出
如果我們執行上述程式碼，它將生成以下輸出：
Count of substrings of a binary string containing K ones are: 6
更新於: 2020-12-02
466 次瀏覽
廣告