資訊專欄INFORMATION COLUMN
摘要：題目給定一個字符串，計算具有相同數(shù)量和的非空連續(xù)子字符串的數(shù)量，并且這些子字符串中的所有和所有都是組合在一起的。示例輸入輸出解釋有個子串具有相同數(shù)量的連續(xù)和，，，，和。請注意，一些重復出現(xiàn)的子串要計算它們出現(xiàn)的次數(shù)。
題目
給定一個字符串?s，計算具有相同數(shù)量0和1的非空(連續(xù))子字符串的數(shù)量，并且這些子字符串中的所有0和所有1都是組合在一起的。
重復出現(xiàn)的子串要計算它們出現(xiàn)的次數(shù)。
示例1:
輸入: "00110011" 輸出: 6 解釋: 有6個子串具有相同數(shù)量的連續(xù)1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。 請注意，一些重復出現(xiàn)的子串要計算它們出現(xiàn)的次數(shù)。 另外，“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
步驟:動態(tài)拼接reg
所有reg對應的s.match(reg).length求和就是所求子串的數(shù)量
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 |
需要兩次循環(huán):
外循環(huán): 從頭到尾遍歷每個字母,
內循環(huán): 第i輪: subStri = s.slice(i), 從頭開始匹配符合規(guī)則的子串
時間復雜度O($n^2$)
const countBinarySubstrings = (str) => {
// 建立數(shù)據(jù)結構，堆棧，保存數(shù)據(jù)
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循環(huán)控制程序運行的流程
for (let i = 0, len = str.length - 1; i < len; i++) {
let sub = match(str.slice(i))
if (sub) {
r++
}
}
return r
}
思路2 (換一種表示)
| 字符串 | 用連續(xù)0或1的個數(shù)表示 | 子串個數(shù) |
|---|---|---|
| 00110011 | 2222 | min(2, 2) + min(2, 2) + min(2, 2) = 6 |
| 001100 | 221 | min(2, 2) + min(2, 1) = 3 |
步驟:
轉為連續(xù)子串個數(shù)形式 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 上一次連續(xù)的個數(shù)
let cur = 0 // cur 當前數(shù)字連續(xù)的個數(shù)
let count = 0 // 符合規(guī)則子串的數(shù)量
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博客首發(fā), 轉載請注明來自GivenCui
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://m.hztianpu.com/yun/105606.html
摘要：重復出現(xiàn)的子串要計算它們出現(xiàn)的次數(shù)。示例輸入輸出解釋有個子串，，，，它們具有相同數(shù)量的連續(xù)和。注意在到之間。以此類推，剃掉原字符串的第一個字符后再調用一次方法，直到原字符串只剩下個字符，返回數(shù)組的長度，即為題解。 博客原文地址：https://finget.github.io/2019... 反轉整數(shù) 給出一個 32 位的有符號整數(shù)，你需要將這個整數(shù)中每位上的數(shù)字進行反轉。 示例 ...
摘要：則不算，因為兩個被分割開了，不是連續(xù)的。思路只記錄前一組是還是，以及出現(xiàn)的次數(shù)。相同，則判斷是否與前一個字符相同。那么此時需要拋棄前一組的所有內容。當前一組未配對字符數(shù)量達到時，說明前一組已經(jīng)沒有可以匹配的字符。故把當前組替換未前一組。 D88 696. Count Binary Substrings 題目鏈接 696. Count Binary Substrings 題目分析 給定一...
摘要：示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。 LeetCode3.無重復字符的最長子串JavaScript 給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。 示例 1: 輸入: abcabcbb輸出: 3 解釋: 因為無重復字符的最長子串是 abc，所以其長度為 3。 示例 2: 輸入: bbbbb輸出...
摘要：最長回文子串給定一個字符串，找到中最長的回文子串。你可以假設的最大長度為。示例輸入輸出注意也是一個有效答案。 LeetCode5.最長回文子串 JavaScript 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。示例 1： 輸入: babad 輸出: bab 注意: aba 也是一個有效答案。 示例 2： 輸入: cbbd輸出: bb /*...
閱讀 1127·2021-11-22 15:35
閱讀 1759·2021-10-26 09:49
閱讀 3303·2021-09-02 15:11
閱讀 2142·2019-08-30 15:53
閱讀 2698·2019-08-30 15:53
閱讀 2991·2019-08-30 14:11
閱讀 3585·2019-08-30 12:59
閱讀 3303·2019-08-30 12:53
