696. 计数二进制子串

解题过程

INFO

题目链接给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。重复出现（不同位置）的子串也要统计它们出现的次数

javascript

/**
 * @link https://leetcode.cn/problems/count-binary-substrings/
 * @title 696. 计数二进制子串
 * @description 给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。
 * 重复出现（不同位置）的子串也要统计它们出现的次数
 * @param {string} s
 * @return {number}
 */
// 解法一
// 思路：正则表达式思路错误，没写出来，思路作废
var countBinarySubstrings = function (s) {
  const num01 = s.match(/0+1+/g)?.filter(item => item.length % 2 === 0) || []
  const num10 = s.match(/1+0+/g)?.filter(item => item.length % 2 === 0) || []
  let fix01 = s.match(/01/g) || []
  let fix10 = s.match(/10/g) || []

  if (num01[0] === fix01[0]) {
    fix01 = []
  }

  if (num10[0] === fix10[0]) {
    fix10 = []
  }

  return num01.length + num10.length + fix01.length + fix10.length
}

// 解法二
// 思路：来源评论区解法，总结是错位遍历统计字符串累计递增原则
// 第一步：循环遍历字符串，统计当前字符是否与上一个字符相等，记录当前字符统计数
// 第二步：统计当前字符与上一个字符不相等时，赋值当前记录数为之前记录数，方便下次统计字符数直到出现不一样字符为止重新赋值
// 第三步：判断之前记录数是否大于当前记录数，是则增加相同数量的子字符串出现的次数（这个需要有点抽象思维才好理解）
var countBinarySubstrings = function (s) {
  let pre = 0
  let cur = 1
  let num = 0

  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i - 1]) {
      cur++
    } else {
      pre = cur
      cur  = 1
    }

    if (pre >= cur) {
      num++
    }
  }

  return num
}

// 解法三
// 思路：跟解法二有点类似，优化代码及思路
// 第一步：统计连续相同字符的数量，注意最后需要单独添加一次统计（因为最后一次统计没有记录到）
// 第二步：遍历统计的的数组判断当前次跟上一次数量对比取最小的一个计数
// 缺点：执行效果比解法二稍差一点，但总体不错，思路清晰很多
var countBinarySubstrings = function (s) {
  let count = 1
  let total = 0
  const res = []

  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i - 1]) {
      count++
    } else {
      res.push(count)
      count  = 1
    }
  }

  res.push(count)

  for (let i = 1; i < res.length; i++) {
    // total += res[i] <= res[i - 1] ? res[i] : res[i - 1]
    // 优化👆🏻代码
    total += Math.min(res[i], res[i - 1])
  }

  return total
}

// 解法四
// 思路：通过正则匹配连续的字符然后遍历对比前后字符数量的最小值叠加即可
// 最喜欢的一种方法，解法一就是大概这个思路结果没做出来卡壳了
// 缺点：没有前两种解法执行效果好，但是思路是最清晰易懂的
var countBinarySubstrings = function (s) {
  let total = 0
  const nums = s.match(/0+|1+/g) // 这样写法有一个好处就是已经是根据字符串顺序匹配连续相同的字符数组了
  for (let i = 1; i < nums.length; i++) {
    total += Math.min(nums[i].length, nums[i - 1].length)
  }

  return total
}

// const result = countBinarySubstrings('00110011') // 6
// const result = countBinarySubstrings('10101') // 4
// const result = countBinarySubstrings('00110') // 3
const result = countBinarySubstrings('000111000') // 6
console.log(result)

解题感受

解法一想用正则表达式做的，结果没做出来，有点可惜，然后暂时没想出好方法。解法二是根据评论区一个 Java 解法思路做的，确实思路是正确的，官方题解也是这么做的。然后解法三根据解法二改编优化了一下思路做的。解法四根据题解区一个解法想到的，醍醐灌顶的感觉，这不就是我想要的思路嘛，哈哈哈，然后自己做了一遍，难怪自己解法一卡壳是因为忽略了某一点一直死揪着其他点

696. 计数二进制子串 ​

解题过程 ​

解题感受 ​

优质题解 ​

696. 计数二进制子串

解题过程

解题感受

优质题解