数据结构与算法之字符串: Leetcode 696. 计数二进制子串 (Typescript版)-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法之字符串: Leetcode 696. 计数二进制子串 (Typescript版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

计数二进制子串

https://leetcode.cn/problems/count-binary-substrings/

描述

给定一个字符串 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 <= $10^5$
s[i] 为 ‘0’ 或 ‘1’

算法实现

1 ）方案1

function countBinarySubstrings(s: string): number {
  // 建立数据结构，队列，用于保存数据
  const r = []
  // 给定任意子输入都返回第一个符合条件的子串
  const match = (s:string) => {
    // 找到含有0或1一次或多次的匹配字符串
    const j:string = s.match(/^(0+|1+)/)[0]
    // 生成第一个字符异或得到相反的字符，并且长度和匹配字符串保持一致
    const o:string = (Number(j[0]) ^ 1).toString().repeat(j.length)
    // 构造出新的正则，用于过滤当前切片的规则
    const reg = new RegExp(`^(${j}${o})`)
    // 符合条件，拿到 () 中的匹配字符串
    if (reg.test(s)) {
      return RegExp.$1
    } else {
      return ''
    }
  }
  // 通过for循环控制程序运行的流程
  for (let i = 0, len = s.length - 1; i < len; i++) {
    const sub = match(s.slice(i))
    if (sub) {
      r.push(sub)
    }
  }
  return r.length
};

思路：

对字符串做切片处理，从第一位到倒数第二位，左闭右开，此处需要一个for循环
对每一个切片进行单一处理，每个切片只找一个，避免循环到后面出现重复
将找到符合规则的切片存入数组
统计最终数组的长度，即答案

注意：

这个方案在 leetcode上是通不过的，错误发生在 new RegExp 的时候，错误信息是：SyntaxError: Invalid regular expression，Regular expression too large 这个错误在实际应用场景中是不会出现的，用例有些极端了

2 ）方案2文章来源地址https://www.toymoban.com/news/detail-428209.html

function countBinarySubstrings(s: string): number {
  let count:number = 0 // 用于统计最终符合要求的长度
  let last:string = '_'; // 最后添加的一个字符
  let pre:number = 0; // 
  let cur:number = 0;
  let i:number = 0;
  s += last
  while(i < s.length) {
    const c:string = s[i] // 获取当前切片字符串
    // 当不是最后一个时，将判断逻辑写在一起
    if(last !== c) {
        // 遇到下一个不同字符更新,用pre保留cur值
        last = c; // 保留当前字符串
        count += Math.min(pre, cur); // 比较前2个不同字符出现次数的最小值
        pre = cur; // pre 保留前一个字符出现的次数
        cur = 0; // 
    }
    cur ++; // 当前字符出现的次数
    i ++
  }
  return count;
}