计数二进制子串

难度：简单
描述：
给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数

示例 1:

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

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

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

1
2
3
4
5
6
7

思路分析：
思路一： 1.遍历字符串，比较前一个数字出现的次数和后一个数字出现的次数，
2.当前一个数字出现的次数大于等于后一个数字出现的次数，则一定包含满足条件的子串
思路二：1.遍历字符串，利用正则找出第一个符合条件的子串
2.判断当前字符串是否匹配该子串，如果匹配则返回该子串

代码实现：

var countBinarySubstrings = function(s) {
    // pre 前一个数字连续出现的次数，cur 当前数字连续出现的次数，result 结果子串个数
    let pre = 0, cur = 1, result = 0
    for (let i = 0, len = s.length - 1; i < len; i++) {
        // 判断当前数字是否与后一个数字相同
        if (s[i] === s[i+1]) { // 相同，则当前数字出现的次数cur加1
            cur++ 
        } else { // 不同，则当前数字事实上变成了前一个数字，当前数字的次数重置为1
            pre = cur
            cur = 1
        }
        if (pre >= cur) { // 前一个数字出现的次数 >= 后一个数字出现的次数，则一定包含满足条件的子串
            result++
        }
    }
    return result
};

// 利用正则
export default (str) => {
  // 建立数据结构，堆栈，保存数据
  let r = []
  // 给定任意子输入都返回第一个符合条件的子串
  let match = (str) => {
    let j = str.match(/^(0+|1+)/)[0]
    let o = (j[0] ^ 1).toString().repeat(j.length)
    let reg = new RegExp(`^(${j}${o})`)
    if (reg.test(str)) {
      return RegExp.$1
    } else {
      return ''
    }
  }
  // 通过for循环控制程序运行的流程
  for (let i = 0, len = str.length - 1; i < len; i++) {
    let sub = match(str.slice(i))
    if (sub) {
      r.push(sub)
    }
  }
  return r.length
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

← 反转字符串有效的括号 →

# 计数二进制子串

计数二进制子串