数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中统计二进制子串
假设我们有一个字符串s，我们需要找到包含相同数量的0和1的连续子串的数量，并且这些子串中的所有0和所有1都连续分组。如果子串出现多次，则计算其出现的次数。
因此，如果输入类似于“11001100”，则输出将为6，因为子串为“1100”、“10”、“0011”、“01”、“1100”、“10”。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个大小为2的数组cnt，并将其填充为0
- res := 0
- for 初始化 i := 0，当 i < s的长度，更新 (i增加1)，执行：
- num := s[i] - '0' 的ASCII码
- 如果 i 等于 0 或 s[i] 不等于 s[i - 1]，则：
- cnt[num] := 0
- (cnt[num] 增加1)
- 如果 cnt[num] <= cnt[1 - num]，则：
- (res 增加1)
- 返回 res
让我们来看下面的实现，以便更好地理解：
示例
#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
更新于：2020年7月4日
706 次浏览
广告