这是悦乐书的第293次更新,第311篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第161题(顺位题号是696)。给定一个字符串s,计算具有相同数字0和1的非空且连续子串的数量,并且这些子串中的所有0和所有1都是连续的。重复出现的子串也计算在内。例如:

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

输入:“00110011”

输出:6

说明:有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011”和“01”。其中一些子字符串重复出现了,但是也需要计算它们出现的次数。此外,“00110011”不是有效的子字符串,因为所有0(和1)都没有组合在一起。


输入:“10101”

输出:4

说明:有4个子串:“10”,“01”,“10”,“01”具有相同数量的连续1和0。


注意:

  • 字符串长度将介于1到50,000之间。

  • s只包含“0”或“1”字符。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

题目的意思是在给定的字符串中找到连续的0和1组成的子串个数,其中0和1是挨着的,可以有多个连续的0与多个连续的1。比如,0011,其中就有两个子串符合,一是第二位与第三位组成的01,二是其本身,两个0和两个1。再比如00111,同样也只有两个子串符合,一是01,二是0011。所以,我们的判断标准就变成了,在一个由0和1组成的连续子串中,0的个数与1的个数,取其中的较小值,就是可能的子串数。

对此,我们将原字符串中,将每段连续的0或者1的个数统计出来,然后比较相邻的两段的值,取其中较小的进行累加,最后就是该字符串所有可能的子串数。

此解法的时间复杂度是O(n),空间复杂度是O(n)。

public int countBinarySubstrings(String s) {
    int[] arr = new int[s.length()];
    arr[0] = 1;
    int index = 0;
    for (int i=1; i<s.length(); i++) {
        if (s.charAt(i) != s.charAt(i-1)) {
            arr[++index] = 1;
        } else {
            arr[index]++;
        }
    }
    int count = 0;
    for (int i=1; i <= index; i++) {
        count += Math.min(arr[i], arr[i-1]);
    }
    return count;
}


03 第二种解法

第一种解法中,我们将每段分组的值存到了新数组中,在分段完后,再去计算总数,但是我们也可以不使用新数组,直接在统计分段时,就将值累加起来。我们使用两个临时变量,一个存储当前这段分组的长度,一个存储上一段分组的长度,在循环字符串中的字符时,如果当前字符和前一个字符不相等,说明该分段了,此时需要先比较两个临时变量的值,取较小的累加到count上去,然后将上一段的长度赋值给另外一个变量,当前新段的长度重置为1。在循环结束后,还需要再取两者之间的较小值再累加一次,因为有可能最后一段就是连续的,而不能在循环里进行判断了。

public int countBinarySubstrings(String s) {
    int currentLength = 1, prevLength = 0, count = 0;
    for (int i=1; i<s.length(); i++) {
        if (s.charAt(i) != s.charAt(i-1)) {
            count += Math.min(prevLength, currentLength);
            prevLength = currentLength;
            currentLength = 1;
        } else {
            currentLength++;
        }    
    }
    count += Math.min(prevLength, currentLength);
    return count;
}


04 小结

算法专题目前已日更超过四个月,算法题文章161+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄