资讯专栏INFORMATION COLUMN

Leetcode 696.计数二进制子串(javascript)

Noodles / 2015人阅读

摘要:题目给定一个字符串,计算具有相同数量和的非空连续子字符串的数量,并且这些子字符串中的所有和所有都是组合在一起的。示例输入输出解释有个子串具有相同数量的连续和,,,,和。请注意,一些重复出现的子串要计算它们出现的次数。

题目

给定一个字符串 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
步骤:

动态拼接reg

所有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
序号 过程
输入 00110011
1 00110011
2 00110011
3 00110011
4 00110011
5 00110011
6 00110011

需要两次循环:
外循环: 从头到尾遍历每个字母,
内循环: 第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 (换一种表示)
字符串 用连续0或1的个数表示 子串个数
00110011 2222 min(2, 2) + min(2, 2) + min(2, 2) = 6
001100 221 min(2, 2) + min(2, 1) = 3

步骤:

转为连续子串个数形式 e.g. “1111000011010001011”转化为[4, 4, 2, 1, 1, 3, 1, 1, 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

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/105606.html

相关文章

  • JavaScript数据结构与算法-String-(leetcode原题)

    摘要:重复出现的子串要计算它们出现的次数。示例输入输出解释有个子串,,,,它们具有相同数量的连续和。注意在到之间。以此类推,剃掉原字符串的第一个字符后再调用一次方法,直到原字符串只剩下个字符,返回数组的长度,即为题解。 博客原文地址:https://finget.github.io/2019... 反转整数 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例 ...

    KoreyLee 评论0 收藏0
  • Leetcode PHP题解--D88 696. Count Binary Substrings

    摘要:则不算,因为两个被分割开了,不是连续的。思路只记录前一组是还是,以及出现的次数。相同,则判断是否与前一个字符相同。那么此时需要抛弃前一组的所有内容。当前一组未配对字符数量达到时,说明前一组已经没有可以匹配的字符。故把当前组替换未前一组。 D88 696. Count Binary Substrings 题目链接 696. Count Binary Substrings 题目分析 给定一...

    lanffy 评论0 收藏0
  • LeetCode3.无重复字符的最长子串JavaScript

    摘要:示例输入输出解释因为无重复字符的最长子串是,所以其长度为。请注意,你的答案必须是子串的长度,是一个子序列,不是子串。 LeetCode3.无重复字符的最长子串JavaScript 给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。 示例 1: 输入: abcabcbb输出: 3 解释: 因为无重复字符的最长子串是 abc,所以其长度为 3。 示例 2: 输入: bbbbb输出...

    vboy1010 评论0 收藏0
  • LeetCode5.最长回文子串 JavaScript

    摘要:最长回文子串给定一个字符串,找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。 LeetCode5.最长回文子串 JavaScript 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1: 输入: babad 输出: bab 注意: aba 也是一个有效答案。 示例 2: 输入: cbbd输出: bb /*...

    philadelphia 评论0 收藏0
  • sar —— Linux 上最为全面的系统性能分析工具之一

    摘要:系统活动情况报告是目前上最为全面的系统性能分析工具之一,可以从多方面对系统的活动进行报告,包括文件的读写情况系统调用的使用情况磁盘效率内存使用状况进程活动及有关的活动等。输出项说明表示统计信息为所有的平均值。 sar(System Activity Reporter 系统活动情况报告)是目前 Linux 上最为全面的系统性能分析工具之一,可以从多方面对系统的活动进行报告,包括:文件的...

    techstay 评论0 收藏0

发表评论

0条评论

Noodles

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<