计数二进制子串（ing）
一、题目描述
给定一个字符串 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。
提示
- s.length 在 1 到 50,000 之间。
- s 只包含“0”或“1”字符。
二、题解
1、结果辅助作图
2、思路一
- 利用 str.match(regexp) 返回匹配到的字符串，取到第一批起始值为连续的 0 或连续的 1 的值 =>
/^(0+|1+)/+[0] - 利用
^位运算符实现 0 和 1 的相互取反（0^1=> 1；1^1=> 0），配合 repeat() 取到拼接的同数量反向值组成子串。 - 利用 new RegExp() 显示创建以上面子串为内容的正则，用 regexObj.test(str) 检测该正则。
伪代码：
// 由题可得字符串总数为偶数，且子串数量需要 >=2，所以截止到倒数第二位
for i = 0; i < str.length - 1; i++
r = handle(str.slice(i))
if r
result.push(r)
解题：
var countBinarySubstrings = function (s) {
// 建立数据结构，堆栈，保存数据
let res = [];
// 找子串
// 给定任意输入，都返回第一个符合条件的子串
let handle = (str) => {
// 从字符串起始位置开始找到连续的 0 或 1
let j = str.match(/^(0+|1+)/g)[0];
// 紧挨着的字符应该是前面的取反（前面的是 0 则后面的是 1）
// j 应该是 0 或 00 或 1 或 11 这样的字符
// 取 j 中的一个字符，与 1 进行异或运算，得到 o 的一个字符
// 再将 o 的长度变为跟 j 一样的长度
// 其中 0^1=1、1^1=0 (异或运算，有且只有 1 个 1 时结果为 1)
let o = (j[0] ^ 1).toString().repeat(j.length);
// 符合的子串就是 j+o ，构造一个子串的正则
let reg = new RegExp(`^(${j}${o})`);
if (reg.test(str)) {
return RegExp.$1;
}
};
// 通过 for 循环控制程序运行的流程
// 从字符串第 0 个位置开始找子串，遍历到倒数第二位，因为子串最少两个字符
for (let i = 0; i < s.length - 1; i++) {
let sub = handle(s.slice(i));
if (sub) {
res.push(sub);
}
}
return res.length;
};
这种方式由于 new RegExp(^({j}j{o})) 构造的正则表达式超长，导致字符串过长，LeetCode 测试不通过，但实际上是可以用的。
3、思路二
- 将原始字符串拆分为由连续相同字符元素组成的数组，比如 “00110011” 拆分为
['00', '11', '00', '11']； - 遍历数组，两个相邻元素的长度中的最小值即这两个元素可以组成的子串数量；
- 累加即可得到最终子串的数量；
var countBinarySubstrings = function (str) {
// 将原始字符串拆为由连续字符元素组成的数组
// 01 或者 10 不是连续字符，所以可以先在它们中间加空格，然后根据空格来拆
let arr = str.replace(/01/g, "0 1").replace(/10/g, "1 0").split(" ");
// 遍历数组，两个相邻元素长度的最小值即它们能组成子串的数量
// 比如 ['00','111'] 只能组成 '0011' 或者 '01'
let count = 0; // 叠加器，用来计算最终满足条件的子串数量
let len = arr.length - 1; // 从 0 开始、只能遍历到倒数第 2 个元素
for (let i = 0; i < len; i++) {
count += Math.min(arr[i].length, arr[i + 1].length);
}
return count;
};
其实就做了三件事：
- 首先在原字符串中 01 或 10 做切割，分割成连续 0 和连续 1 单独组成的数组；
- 然后对这个数组的相邻元素进行组合，看组合后能得出的满足条件子串数量，最后累加所有满足条件子串的数量即可；
将数组中相邻元素组合后得出满足条件子串的规律是：相邻元素中长度较短的元素长度即为这两个元素组合后符合条件子串的数量，举个例子：
00 11
// 组合成 0011 后有2个满足条件的子串，分别为 0011、01
111 00
// 组合成 11100 后有2个满足条件的子串，分别为 1100、10
00 1111
// 组合成 0011 后有2个满足条件的子串，分别为 0011、01
1111 000000000000
// 组合成 1111000000000000 后有4个满足条件的子串
// 分别为 11110000、111000、1100、10
利用以上相邻元素组合后快速计算出满足条件子串的规律，遍历一遍数组，将所有满足条件的子串数量叠加就是最终结果了。