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

### 题目

``````输入: "00110011"

``````

``````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

1 00110011
2 00110011
3 00110011
4 00110011
5 00110011
6 00110011

``````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 (换一种表示)

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
}

``````

``````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

javascript是什么意思
avaScript是Netscape开发的一个对象脚本语言，它使用在世界各地数以百万计的网页和服务器应用程序上。 网景的JavaScript是ecma - 262版的标准脚本语言,和公布的标准只有轻微的差异。 与广为流行的错误理解相反,Ja...
2015-11-12
21天学通javascript

2015-11-16
JavaScript的组成

2015-11-12
javaScript+turn.js实现图书翻页效果实例代码

2017-03-16
JavaScript 事件流、事件处理程序及事件对象总结
JS与HTML之间的交互通过事件实现。事件就是文档或浏览器窗口中发生的一些特定的交互瞬间。可以使用监听器(或处理程序)来预定事件，以便事件发生时执行相应的代码。这种在传统软件工程中被称为观察员模式，支持页面的行为与页面的外观之间的松散耦合。...
2017-04-05
JavaScript变量的声明

2015-11-12
7个提高效率的JavaScript调试工具

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

2015-11-16