成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Leetcode 696.計(jì)數(shù)二進(jìn)制子串(javascript)

Noodles / 2170人閱讀

摘要：題目給定一個(gè)字符串，計(jì)算具有相同數(shù)量和的非空連續(xù)子字符串的數(shù)量，并且這些子字符串中的所有和所有都是組合在一起的。示例輸入輸出解釋有個(gè)子串具有相同數(shù)量的連續(xù)和，，，，和。請(qǐng)注意，一些重復(fù)出現(xiàn)的子串要計(jì)算它們出現(xiàn)的次數(shù)。

題目

給定一個(gè)字符串?s，計(jì)算具有相同數(shù)量0和1的非空(連續(xù))子字符串的數(shù)量，并且這些子字符串中的所有0和所有1都是組合在一起的。

重復(fù)出現(xiàn)的子串要計(jì)算它們出現(xiàn)的次數(shù)。

示例1:

輸入: "00110011"
輸出: 6
解釋: 有6個(gè)子串具有相同數(shù)量的連續(xù)1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

請(qǐng)注意，一些重復(fù)出現(xiàn)的子串要計(jì)算它們出現(xiàn)的次數(shù)。

另外，“00110011”不是有效的子串，因?yàn)樗械?（和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
步驟:



動(dòng)態(tài)拼接reg


所有reg對(duì)應(yīng)的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
序號(hào) 過程
輸入 00110011
1 00110011
2 00110011
3 00110011
4 00110011
5 00110011
6 00110011

需要兩次循環(huán):
外循環(huán): 從頭到尾遍歷每個(gè)字母,
內(nèi)循環(huán): 第i輪: subStri = s.slice(i), 從頭開始匹配符合規(guī)則的子串
時(shí)間復(fù)雜度O($n^2$)

const countBinarySubstrings = (str) => {
  // 建立數(shù)據(jù)結(jié)構(gòu)，堆棧，保存數(shù)據(jù)
  let r = 0
  // 給定任意子輸入都返回第一個(gè)符合條件的子串
  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)控制程序運(yù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的個(gè)數(shù)表示 子串個(gè)數(shù)
00110011 2222 min(2, 2) + min(2, 2) + min(2, 2) = 6
001100 221 min(2, 2) + min(2, 1) = 3

步驟:

轉(zhuǎn)為連續(xù)子串個(gè)數(shù)形式 e.g. “1111000011010001011”轉(zhuǎn)化為[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 (標(biāo)記)

時(shí)間復(fù)雜度O($n$)

const countBinarySubstrings = (s) => {
  let last = 0 // last 上一次連續(xù)的個(gè)數(shù)
  let cur = 0 // cur  當(dāng)前數(shù)字連續(xù)的個(gè)數(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ā), 轉(zhuǎn)載請(qǐng)注明來自GivenCui

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/105606.html

相關(guān)文章

  • JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-String-(leetcode原題)

    摘要：重復(fù)出現(xiàn)的子串要計(jì)算它們出現(xiàn)的次數(shù)。示例輸入輸出解釋有個(gè)子串，，，，它們具有相同數(shù)量的連續(xù)和。注意在到之間。以此類推，剃掉原字符串的第一個(gè)字符后再調(diào)用一次方法，直到原字符串只剩下個(gè)字符，返回?cái)?shù)組的長(zhǎng)度，即為題解。 博客原文地址：https://finget.github.io/2019... 反轉(zhuǎn)整數(shù) 給出一個(gè) 32 位的有符號(hào)整數(shù)，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)。 示例 ...

    KoreyLee 評(píng)論0 收藏0

  • Leetcode PHP題解--D88 696. Count Binary Substrings

    摘要：則不算，因?yàn)閮蓚€(gè)被分割開了，不是連續(xù)的。思路只記錄前一組是還是，以及出現(xiàn)的次數(shù)。相同，則判斷是否與前一個(gè)字符相同。那么此時(shí)需要拋棄前一組的所有內(nèi)容。當(dāng)前一組未配對(duì)字符數(shù)量達(dá)到時(shí)，說明前一組已經(jīng)沒有可以匹配的字符。故把當(dāng)前組替換未前一組。 D88 696. Count Binary Substrings 題目鏈接 696. Count Binary Substrings 題目分析 給定一...

    lanffy 評(píng)論0 收藏0

  • LeetCode3.無(wú)重復(fù)字符的最長(zhǎng)子串JavaScript

    摘要：示例輸入輸出解釋因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是，所以其長(zhǎng)度為。請(qǐng)注意，你的答案必須是子串的長(zhǎng)度，是一個(gè)子序列，不是子串。 LeetCode3.無(wú)重復(fù)字符的最長(zhǎng)子串JavaScript 給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。 示例 1: 輸入: abcabcbb輸出: 3 解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 abc，所以其長(zhǎng)度為 3。 示例 2: 輸入: bbbbb輸出...

    vboy1010 評(píng)論0 收藏0

  • LeetCode5.最長(zhǎng)回文子串 JavaScript

    摘要：最長(zhǎng)回文子串給定一個(gè)字符串，找到中最長(zhǎng)的回文子串。你可以假設(shè)的最大長(zhǎng)度為。示例輸入輸出注意也是一個(gè)有效答案。 LeetCode5.最長(zhǎng)回文子串 JavaScript 給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。示例 1： 輸入: babad 輸出: bab 注意: aba 也是一個(gè)有效答案。 示例 2： 輸入: cbbd輸出: bb /*...

    philadelphia 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<