leetcode696、计数二进制子串

    xiaoxiao2022-07-15  167

    题目

    给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

    示例 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。


    方法1:

    以00110011为例,从第一位开始,逐渐向后移,找到第一个含0的子串或含1的子串,然后拼接对应相反的子串,如先找到00,然后取反得11,拼接成0011,然后看看00110011是否是从0011开始的,是的话则表示找到这个子串然后继续从第二位开始,找到0,然后取反为1,拼接成01,看看从第二位开始看看0110011是否是以01开头,是的话就找到子串,以此类推,代码如下: const countBinarySubstrings = function(s) { let count = 0 const match = str => { let s1 = str.match(/(0+|1+)/)[0] let s2 = (s1[0] ^ 1).toString().repeat(s1.length) let s3 = s1 + s2 if (s3 === str.slice(0, s1.length * 2)) { return true } else { return false } } for (var i = 0; i < s.length - 1; i++) { var sub = match(s.slice(i)) if (sub) { count++ } } return count };

    缺点:

    重复计算太多,如000111是一个合格的子串,那么表示0011也是,01也是,其实遍历步长不需要为1使用太多API,性能低下

    方法2:解决重复计算

    以000111000为例,确认000111为合格子串之后,增加合格子串数目为 6 / 2 = 3,遍历下标直接跳到1处,从111000开始 const countBinarySubstrings = function(s) { let count = 0 const match = str => { let s1 = str.match(/(0+|1+)/)[0] let s2 = (s1[0] ^ 1).toString().repeat(s1.length) let s3 = s1 + s2 if (s3 === str.slice(0, s1.length * 2)) { return s3 } else { return '' } } for (let i = 0; i < s.length - 1;) { let goodStr = match(s.slice(i)) if (goodStr.length > 0) { count += goodStr.length / 2 i += goodStr.length / 2 } else { i++ } } return count };

    缺点:

    使用太多API,性能低下

    方法3:解决用太多API方法

    const countBinarySubstrings = function(s) { if (s.length <= 1) return 0 let preRun = 0 let curRun = 1 let count = 0 for (let i = 1; i < s.length; i++) { if (s[i - 1] === s[i]) { curRun++ } else { preRun = curRun curRun = 1 } if (preRun >= curRun) { count++ } } return count };

    性能最优

    最新回复(0)