LeetCode：计数二进制子串的解题思路与代码实现

"LeetCode 计数二进制子串" 在 LeetCode 上有一道名为“计数二进制子串”的题目，该题目要求计算一个给定的二进制字符串中，有多少个非空子串，这些子串内0和1的数量相同，并且0和1都是连续出现的。例如，对于输入字符串 "00110011"，输出应为 6，因为有六个这样的子串："0011"、"01"、"1100"、"10"、"0011" 和 "01"。 在解题过程中，一种常见的方法是使用“01压缩”策略。首先，将连续的0和1进行压缩，例如字符串 "110001101110000" 压缩成 "232134"。接着，计算压缩后字符串中相邻数字的最小值之和，这将给出满足条件的子串数量。这是因为对于符合条件的子串，我们只需要知道0或1的连续数量，就可以确定子串的总数。例如，在压缩后的字符串中，如果当前数字小于前一个数字，表示找到了一个新的子串起始点，此时 count++；如果当前数字大于前一个数字，则用当前数字替换前一个数字，并继续检查下一个数字。 算法的时间复杂度为 O(n)，其中 n 是输入字符串的长度，因为它只需遍历一次字符串。空间复杂度为 O(1)，因为我们只需要常量级别的额外空间来存储计数变量和当前的连续数字。 以下是使用 Java 实现的算法源码示例： ```java public class Solution { public int countBinarySubstrings(String s) { int count = 0, pre = 0, cur = 0; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { cur++; } else { count += Math.min(pre, cur) + 1; pre = cur; cur = 1; } } count += Math.min(pre, cur); return count; } } ``` 在这个算法中，`pre` 存储上一组相同数字的长度，`cur` 存储当前组相同数字的长度，`count` 用于累计符合条件的子串数量。每次遇到不同数字时，会根据 `pre` 和 `cur` 的最小值增加计数，并更新 `pre` 和 `cur` 的值。 这个题目考察了对字符串处理和动态累积的概念，同时也涉及到了时间复杂度和空间复杂度的分析。它是一个典型的计算机科学问题，对于提升编程能力特别是算法设计能力非常有帮助。