一、题目描述

计数二进制子串

给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。

重复出现的子串要计算它们出现的次数。

示例1

输入: “00110011”
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例2

输入: “10101”
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

二、思路分析

• 首先原字符串是有相同数量0、1组成的非空字符串。需要我们筛选出相同数量0,1且连续的子串。
• 首先想到的是动态规划。但是在确定转移方程的时候需要考虑两个字符的存在而且两个字符的位置也是未知的，所以在很难书写出转移方程。
• 那么动态规划不好实现我们可以换种实现方式。
• 题目中对子串是有条件限制的，什么叫0,1数量相同、什么叫连续；针对这两个特性我们归纳出子串的特征是aaabbb型的
• 还有一点子串是从原字符串中截取出来的，所以原字符一定部分是和子串对应的。

• 在成对数量进行分割时会出现左右两边数量不对等的情况。这个时候肯定需要有人做出让步，那么谁让步呢？我们来看看下面三种情况

• 所以在成对出现的左右数量不等的情况，已少的一遍为准，如果已多的一遍为准的话，少的一遍就无法提供更多的数据进行匹配了。
• 在题目中提到的00110011 这个数据我们就可以根据0,1进行分组如下

• 然后我们在针对新分组的数据进行两两相邻比对，最终我们得到的数据为2+2+2=6 种情况

三、AC 代码

public int countBinarySubstrings(String s) {
    int pre = -1;
    int count = 0;
    List<Integer> resultList = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        int current = s.charAt(i) - '0';
        if (current == pre) {
            count++;
        } else {
            resultList.add(count);
            pre = current;
            count = 1;
        }
    }
    resultList.add(count);
    int result = 0;
    for (int i = 1; i < resultList.size(); i++) {
        result += Math.min(resultList.get(i - 1), resultList.get(i));
    }
    return result;
}

四、总结

• 算法就是需要不断的刷才能掌握其中的真理。本题实现上不是很难只需要我们能够发现数据的规律

点赞呗！！！