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

2019-07-13 admin

题目

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

序号 过程
输入 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

步骤:

  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
}

时间复杂度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://segmentfault.com/a/1190000019750696

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-69633.html

文章标题:Leetcode 696.计数二进制子串(javascript)

相关文章
javascript是什么意思
avaScript是Netscape开发的一个对象脚本语言,它使用在世界各地数以百万计的网页和服务器应用程序上。 网景的JavaScript是ecma - 262版的标准脚本语言,和公布的标准只有轻微的差异。 与广为流行的错误理解相反,Ja...
2015-11-12
21天学通javascript
简介: 本书是Javascript入门教程。Javascript是Web开发中应用最早、发展最成熟、用户最多的脚本语言。其语法简洁,代码可读性在众多脚本语言中最好,它在使用时不用考虑数据类型,是真正意义上的动态语言。本书总分为四篇,共21章...
2015-11-16
JavaScript的组成
一个完整的JavaScript由3个部分组成:核心(ECMAScript) 文档对象模型(DOM) 浏览器对象模型(BOM) ECMAScript 描述了该语言的语法和基本对象 ; DOM 描述了处理网页内容的方法和接口 ; BOM 描...
2015-11-12
javaScript+turn.js实现图书翻页效果实例代码
为了实现图书翻页的效果我们在网上可以看到很多教程 在这里推荐turn.js 网上的turn.js 有api 不过是英文的  很多人看起来不方便 .关于代码也是奇形怪状在这里我将详细讲解如何使用turn.js实现翻页效果 ,本篇文章只是讲解 ...
2017-03-16
JavaScript 事件流、事件处理程序及事件对象总结
JS与HTML之间的交互通过事件实现。事件就是文档或浏览器窗口中发生的一些特定的交互瞬间。可以使用监听器(或处理程序)来预定事件,以便事件发生时执行相应的代码。这种在传统软件工程中被称为观察员模式,支持页面的行为与页面的外观之间的松散耦合。...
2017-04-05
JavaScript变量的声明
声明变量 变量在脚本中的首次亮相是在其声明中。 在变量首次出现时将会在内存中设置它,因此您稍后可在脚本中引用它。 应在使用变量之前先声明变量。 可以使用 var 关键字实现此目的。 &lt;span id=“mt9” class=“sent...
2015-11-12
7个提高效率的JavaScript调试工具
鐜板湪鐨凧avaScript浜嬪疄涓婂凡鐒舵垚涓轰簡娴佽�岀殑web璇�瑷€锛屽嵆浣垮畠骞朵笉瀹岀編銆傚緢澶氱▼搴忓憳涓嶅枩娆㈢敤JavaScript鍐欎唬鐮侊紝鏄�鍥犱负鍐欏埌鍚庢潵鎬讳細鍑虹幇鍚勭�嶈帿鍚嶅叾濡欑殑bug锛岃€屼笖鍦ㄥ紑...
2015-11-11
JavaScript短路原理精简代码
js中||和&amp;&amp;的特性帮我们精简了代码的同时,也带来了代码可读性的降低,虽然高效,但请灵活使用。 在js逻辑运算中,0、&quot;&quot;、null、false、undefined、NaN都会判为false,其他都为t...
2015-11-12
React Native 用JavaScript编写原生ios应用
ReactNative 可以基于目前大热的开源JavaScript库React.js来开发iOS和Android原生App。而且React Native已经用于生产环境——Facebook Groups iOS 应用就是基于它开发的。 Re...
2015-11-12
《JavaScript快速查询手册》PDF
下载地址:《JavaScript快速查询手册》PDF下载 http://pan.baidu.com/s/130rP8’ 简介: JavaScript快速查询手册 目录 前言 第一部分 命令查询 第二部分 JavaScript语句与运算符 第...
2015-11-16
回到顶部