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