Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

นับซับสตริงไบนารีใน C ++


สมมติว่าเรามีสตริง s เราต้องหาจำนวนสตริงย่อยที่อยู่ติดกันซึ่งมีจำนวนเท่ากันของ 0 และ 1 และ 0 ทั้งหมดและ 1 ทั้งหมดในสตริงย่อยเหล่านี้จะถูกจัดกลุ่มตามลำดับ หากสตริงย่อยเกิดขึ้นหลายครั้งจะถูกนับจำนวนครั้งที่เกิดขึ้น

ดังนั้น หากอินพุตเป็น "11001100" เอาต์พุตจะเป็น 6 เนื่องจากสตริงย่อยคือ "1100", "10","0011", "01", "1100", "10"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • กำหนดอาร์เรย์ cnt ขนาด 2 และเติมค่านี้ด้วย 0
  • res :=0
  • สำหรับการเริ่มต้น i :=0, เมื่อ i <ความยาวของ s, อัปเดต (เพิ่ม i ขึ้น 1), ทำ −
    • num :=s[i] - ASCII ของ '0'
    • ถ้าฉันเหมือนกับ 0 หรือ s[i] ไม่เท่ากับ s[i - 1] แล้ว −
      • cnt[num] :=0
    • (เพิ่ม cnt[num] ขึ้น 1)
    • ถ้า cnt[num] <=cnt[1 - num] แล้ว −
      • (เพิ่มความละเอียดขึ้น 1)
  • ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int countBinarySubstrings(string s) {
      int cnt[2] = { 0 };
      int res = 0;
      for (int i = 0; i < s.length(); ++i) {
         int num = s[i] - '0';
         if (i == 0 || s[i] != s[i - 1])
            cnt[num] = 0;
         ++cnt[num];
         if (cnt[num] <= cnt[1 - num])
            ++res;
      }
      return res;
   }
};
main(){
   Solution ob;
   cout << (ob.countBinarySubstrings("11001100"));
}

อินพุต

"11001100"

ผลลัพธ์

6