เราได้รับสตริงของตัวเลขไบนารี คือการรวมของ 0 และ 1 และค่าจำนวนเต็ม k งานคือคำนวณจำนวนซับสตริงที่สร้างจากสตริงไบนารีที่กำหนดซึ่งมี 1 จำนวน k ตัว
อินพุต − string str = '10000100000', k = 2
เอาต์พุต − จำนวนซับสตริงของสตริงไบนารีที่มี 1 จำนวน K ตัว คือ 6
คำอธิบาย − ซับสตริงที่สร้างจากสตริงที่กำหนดคือ 1, 10, 100, 1000, 10000, 010, 100001, 10001, 1001, 101, 11, 1000010 ดังนั้นมี 6 ซับสตริงที่มี 1 จำนวน k ตัว คือ 2 ตัวพอดี
อินพุต − string str = '10000100000', k = 3
เอาต์พุต − จำนวนซับสตริงของสตริงไบนารีที่มี 1 จำนวน K ตัว คือ 0
คำอธิบาย − เราได้รับค่า k เป็น 3 และถ้าตรวจสอบสตริงไบนารี พบว่ามี 1 เพียง 2 ตัว ไม่มีซับสตริงที่มี 1 จำนวน k ตัว
แนวทางที่ใช้ในโปรแกรม
- รับสตริงตัวเลขไบนารีที่มี 0 และ 1 และตัวแปรจำนวนเต็ม k
- คำนวณความยาวสตริงด้วย
length()ส่งไปฟังก์ชันประมวลผล - ประกาศตัวแปรชั่วคราว
countและtotalเป็น 0 สำหรับเก็บซับสตริงที่มี 1 จำนวน k - ประกาศอาเรย์เก็บความถี่ของ 1 ขนาดความยาวสตริง + 1 เริ่มต้นเป็น 0 และกำหนดอิลิเมนต์แรกเป็น 1
- ลูป FOR จาก 0 ถึงความยาวอาเรย์
- ในลูป กำหนด
total = total + str[i] - '0'ตรวจสอบถ้าtotal >= kกำหนดcount = count + arr[total-k] - คืนค่า
count - พิมพ์ผลลัพธ์
ตัวอย่างโค้ด C++
#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
