一、题目粗心
给定一个字符串 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 忽如一夜秋风至，吹落黄花满地金