一、题目粗心

给定一个字符串 s，统计并返回具备雷同数量 0 和 1 的非空（间断）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组间断的。

反复呈现（不同地位）的子串也要统计它们呈现的次数。

示例 1：

输出：s = "00110011"
输入：6
解释：6 个子串满足具备雷同数量的间断 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
留神，一些反复呈现的子串（不同地位）要统计它们呈现的次数。
另外，"00110011" 不是无效的子串，因为所有的 0（还有 1 ）没有组合在一起。

示例 2：

输出：s = "10101"
输入：4
解释：有 4 个子串："10"、"01"、"10"、"01" ，具备雷同数量的间断 1 和 0 。

提醒：

  • 1 <= s.length <= 105
  • s[i] 为 '0' 或 '1'

起源：力扣（LeetCode）
链接：https://leetcode.cn/problems/...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

二、解题思路

思路1:从左往右遍历数组，记录和以后地位数字雷同中且间断的长度，以及其之前间断的不同数字的长度。举例来说，对于00110的最初一位，咱们记录的雷同数字长度是1，因为只有一个间断0；咱们记录的不同数字长度是2，因为在0之前有两个间断的1。若不同数字的间断长度大于等于以后数字的间断长度，则阐明存在一个且只存在一个以后数字结尾的满足条件的子字符串。

思路2:还能够从字符串的每个地位开始，向左向右缩短，判断存在多少以后地位为中轴的由01间断二进制字符串。

三、解题办法

3.1 Java实现

public class Solution {    public int countBinarySubstrings(String s) {        // 输出：s = "00110011"        // 输入：6        int ans = 0;        for (int i = 0; i < s.length() - 1; i++) {            ans += extendSubstrings(s, i, i + 1);        }        return ans;    }    private int extendSubstrings(String s, int l, int r) {        char lc = s.charAt(l);        char rc = s.charAt(r);        if (!((lc == '1' && rc == '0') || (lc == '0' && rc == '1'))) {            return 0;        }        int count = 0;        while (l >= 0 && r < s.length() && lc == s.charAt(l) && rc == s.charAt(r)) {            count++;            l--;            r++;        }        return count;    }}

四、总结小记

  • 2202/8/28 忽如一夜秋风至，吹落黄花满地金