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