Leetcode-696计数二进制子串javascript

题目

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例1:

输入: "00110011"输出: 6解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。请注意，一些重复出现的子串要计算它们出现的次数。另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

注意：

s.length 在1到50,000之间。s 只包含“0”或“1”字符。

思路1 (暴力枚举)

解1

e.g. s= '110011', s.length = 6
reg的可取值 /01/g 或/10/g, /0011/g或/1100/g, /000111/g或/111000/g
步骤:

1. 动态拼接reg
2. 所有reg对应的s.match(reg).length求和就是所求子串的数量

const countBinarySubstrings = function (s) {  const len = s.length  let count = 0  let s1 = ''  let s2 = ''  for (let index = 1; index <= Math.floor(len / 2); index++) {    s1 += '0'    s2 += '1'    let res1 = s.match(new RegExp(s1 + s2, 'g')) || []    let res2 = s.match(new RegExp(s2 + s1, 'g')) || []    count += res1.length    count += res2.length  }  return count}

解2

需要两次循环:
外循环: 从头到尾遍历每个字母,
内循环: 第i轮: subStri = s.slice(i), 从头开始匹配符合规则的子串
时间复杂度O($n^2$)

const countBinarySubstrings = (str) => {  // 建立数据结构，堆栈，保存数据  let r = 0  // 给定任意子输入都返回第一个符合条件的子串  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 true    }    return false  }  // 通过for循环控制程序运行的流程  for (let i = 0, len = str.length - 1; i < len; i++) {    let sub = match(str.slice(i))    if (sub) {      r++    }  }  return r}

思路2 (换一种表示)

步骤:

1. 转为连续子串个数形式 e.g. “1111000011010001011”转化为[4, 4, 2, 1, 1, 3, 1, 1, 2]
2. 相邻元素min求最小值再求和

const countBinarySubstrings = (s) => {  const resArr = []  let cnt = 0  let last = s.length - 1  // i属于 [0, last-1]  for (let i = 0; i < last; i++) {    cnt++    if (s[i] != s[i + 1]) {      resArr.push(cnt)      cnt = 0    }  }  // 最后一位特殊处理  if (s[last - 1] == s[last]) {    resArr.push(cnt + 1)  } else {    resArr.push(1)  }    // 相邻元素min求最小值再求和  let sum = 0  for (let i = 0; i < resArr.length - 1; i++) {    sum += Math.min(resArr[i], resArr[i + 1])  }  return sum}

思路3 (标记)

时间复杂度O($n$)

const countBinarySubstrings = (s) => {  let last = 0 // last 上一次连续的个数  let cur = 0 // cur  当前数字连续的个数  let count = 0  // 符合规则子串的数量  let len = s.length  for (let i = 0; i < len - 1; i++) {    cur++    if (last >= cur) {      count++    }    if (s[i] != s[i + 1]) {      last = cur      cur = 0    }  }  // 最后一位情况  // cur ==0 <=> 后两位不同  if (cur == 0) {    cur = 1  } else {    cur++  }  if (last >= cur) {    count++  }  return count}

givencui博客首发, 转载请注明来自GivenCui