共计 1993 个字符,预计需要花费 5 分钟才能阅读完成。
题目
给定一个字符串 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
正文完
发表至: javascript
2019-07-13