# [LeetCode] Count Binary Substrings 统计二进制子字符串

+关注继续查看

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. 

Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's. 

Note:

• s.length will be between 1 and 50,000.
• s will only consist of "0" or "1" characters.

public:
int countBinarySubstrings(string s) {
int zeros = 0, ones = 0, res = 0;
for (int i = 0; i < s.size(); ++i) {
if (i == 0) {
(s[i] == '1') ? ++ones : ++zeros;
} else {
if (s[i] == '1') {
ones = (s[i - 1] == '1') ? ones + 1 : 1;
if (zeros >= ones) ++res;
} else if (s[i] == '0') {
zeros = (s[i - 1] == '0') ? zeros + 1 : 1;
if (ones >= zeros) ++res;
}
}
}
return res;
}
};

public:
int countBinarySubstrings(string s) {
int res = 0, pre = 0, cur = 1, n = s.size();
for (int i = 1; i < n; ++i) {
if (s[i] == s[i - 1]) ++cur;
else {
pre = cur;
cur = 1;
}
if (pre >= cur) ++res;
}
return res;
}
};

https://discuss.leetcode.com/topic/107096/java-o-n-time-o-1-space

，如需转载请自行联系原博主。

839 0

793 0
C实现特定字符串数据的排序与输出

912 0

883 0

714 0

MySQL binlog日志记录了MySQL数据库从启用日志以来所有对当前数据库的变更。binlog日志属于二进制文件，我们可以从binlog提取出来生成可阅读的SQL语句来重建当前数据库以及根据需要实现时点恢复或不完全恢复。
838 0

863 0
+关注

2107

1103

JS零基础入门教程（上册）