关注Java领域相关技术 记录有趣的事情

LeetCode-696.计数二进制子串

US-B.Ralph
US-B.Ralph
2020-08-10

问题地址

LeetCode每日一题/2020-08-10

LeetCode696.计数二进制字串


问题描述

规则

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

示例

示例 1 :

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。
请注意,一些重复出现的子串要计算它们出现的次数。
另外,“00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。(作者注:全部组合在一起的意思是:0000011111,吗?)

示例 2 :

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

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


解析

解题思路

假设两个相邻连续字符串的长度分别是a和b,代表着a个0,b个1,或者a个1,b个0,由下图我们可以看出,这两个相邻字符串中他们能够满足条件的子串的数量是min{a,b}。故我们可以找出给定字符串中所有连续子串的长度,然后两两比较取小求和即可。

复杂度分析:

  1. 时间复杂度分析:假如我们采用最暴力的解法,使用双层循环:
    • 外层循环:遍历字符串中出现的字符,并存储内存循环中发现的连续字符数量的数量;
    • 内层循环:比较当前字符(第i个字符)与字符串中第i个之后出现的字符是否相同;

    • 注:虽然是两层循环,但是由于存在连续出现的0或1的条件,所以外层循环的指针在内层循环的过程中已经在移动了(字符相同则+1),故时间复杂度为O(n);

  2. 空间复杂度分析:遍历过程中需要保存连续字符出现的次数,空间复杂度为O(n);

定位问题:

统计相似子串的数量。

数据操作分析:

这个问题的本质就是寻找最近的相似子串,所以我们的点只是相邻子串,没有必要存储记录之前的子串,所以只需要在遍历的过程中相邻子串进行比对即可。

优化思考:
– 这个问题的时间复杂度最低是多少呢?分析一下就会知道,只有遍历到最后1个字符,才能确定最后一个字符与前一个字符是否相同。那么可不可以使用二分法呢?不可以,因为连续字串长度不固定且二分之后整个字串的结构都不同了,例如{“000011”}–>{“0011″,”01”},采用二分之后呢变成了{“000011”}->{“000”}+{“011”}很显然这样找出来的字串与我们想要的结果是不同的;
– 是否可以使用更少的空间呢?答案是可以的,上面我们的思路是使用1个容器存储发现的最大连续字符数,如果我们使用2个变量分别代表上一个出现的连续最大字符数,和当前发现的最大连续字符数;

编码实现:

  1. 存储中间数据
class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> lists = new ArrayList<>();
        int point=0;
        int n = s.length();
        int count;
        while(point<n){
            char c = s.charAt(point);
            count=0;
            while(point<n && s.charAt(point)==c){
                point++;
                count++;
            }
            lists.add(count);
        }

        int ans=0;
        for(int i=1; i<lists.size(); i++){
            ans += Math.min(lists.get(i), lists.get(i-1));
        }
        return ans;
    }

}
  1. 在遍历中统计符合条件的子串数
class Solution {
    public int countBinarySubstrings(String s) {
        int point = 0;
        int n = s.length();
        //前一个连续子串长度
        int preCharLen = 0;
        //当前连续子串长度;
        int curCharLen = 1;
        //记录符合要求的子串数量
        int count = 0;

        for(int i=0; i<n-1; i++){
            if(s.charAt(i) != s.charAt(i+1)){
                preCharLen = curCharLen;
                curCharLen = 1;
            }else{
                curCharLen++;
            }
            //每当preCurLen>=curCharLen时,说明能构成一个满足条件的子串
            if(preCharLen >= curCharLen) count++;
        }

        return count;
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

4 + 16 =