算法题目整理分析--计数二进制子串

题目

给定一个字符串 s,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例 1 :

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。

请注意,一些重复出现的子串要计算它们出现的次数。

另外,“00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。

示例 2 :

输入: "10101"
输出: 4
解释: 有4个子串:“10”,“01”,“10”,“01”,它们具有相同数量的连续1和0。

注意:

  • s.length 在1到50,000之间。
  • s 只包含“0”或“1”字符。

第一次测试

export default (str) => {
  let result = []
  for (let i = 0; i < str.length - 1; i++) {
    let code = str[i]
    let count = getSameCount(str, i, code)
    let toMatchString = ((i + count * 2 - 1) < str.length) ? str.substring(i + count, i + count * 2) : ''
    let isMatch = checkSameCount(toMatchString)
    if (isMatch) {
      result.push(str.substring(i, i + count + count))
    }
  }
  return result.length
}
// 获取相同字符的个数
function getSameCount (_string, _startIndex, _code) {
  let _count = 0
  for (let i = _startIndex; i < _string.length; i++) {
    if (_string[i] === _code) {
      _count++
    } else {
      break
    }
  }
  return _count
}
// 校验是否存在匹配的字符
function checkSameCount (_string) {
  if (!_string) {
    return false
  }
  let count = 0
  let _code = _string.substring(0, 1)
  for (let i = 0; i < _string.length; i++) {
    if (_string.charAt(i) === _code) {
      count++
    }
  }
  return count && (count === _string.length)
}

思路整理:

  • 1:找出当前字符一共重复了多少次
  • 2:得出对应的应该匹配的后续的字符
  • 3:检验后续字符与理论值是否匹配
  • 4:拿到结果

这是我觉得比较常规的思路,可以应对各种正常的业务逻辑,不限于0,1之间的匹配。但是性能还是偏低的。

第二次测试

export default (str) => {
  // 建立数据结构,堆栈,保存数据
  let result = []
  for (let i = 0; i < str.length - 1; i++) {
    let match = (s) => {
      let _startStr = s.match(/^0+|1+/)[0]
      let _toMatchCode = _startStr.charAt(0) === '0' ? '1' : '0'
      let _toMatchStr = _toMatchCode.repeat(_startStr.length)
      let reg = new RegExp(`^(${_startStr}${_toMatchStr})`)
      console.log(s, reg, reg.test(s))
      if (reg.test(s)) {
        return RegExp.$1
      } else {
        return ''
      }
    }
    let isMatch = match(str.slice(i))
    if (isMatch) {
      result.push(isMatch)
    }
  }
  return result.length
}

思路整理:

  • 1:创建一个方法,判断字符串是否匹配
  • 2:根据正则取到相同字符
  • 3:用正则去校验数据是否匹配。

思路跟上一个差别不大,只是用了正则,repeat方法等取巧的处理。问题是,正则是有长度限制的,长度过长的时候正则就报错了。

第三次测试

export default (s) => {
  let pre = 0, cur = 1, result = 0
  for (let i = 0, len = s.length - 1; i < len; i++) {
    if (s[i] === s[i + 1]) {
      cur++
    } else {
      pre = cur
      cur = 1
    }
    if (pre >= cur) {
      result++
    }
  }
  return result
}

思路整理:

  • 1:拿到当前字符串出现的次数
  • 2:对比当前字符串出现次数是否小于上一个字符串出现次数
  • 3:小于的话,肯定能匹配到。

这就有点思路上的取巧了。关键是次数判断这里。

随机浏览