สมมติว่าเรามีสตริง 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