LeetCode | US.B

问题地址

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}。故我们可以找出给定字符串中所有连续子串的长度，然后两两比较取小求和即可。

复杂度分析：

时间复杂度分析：假如我们采用最暴力的解法，使用双层循环：
- 外层循环：遍历字符串中出现的字符，并存储内存循环中发现的连续字符数量的数量；
- 内层循环：比较当前字符（第i个字符）与字符串中第i个之后出现的字符是否相同；
- 注：虽然是两层循环，但是由于存在连续出现的0或1的条件，所以外层循环的指针在内层循环的过程中已经在移动了（字符相同则+1），故时间复杂度为O(n)；
空间复杂度分析：遍历过程中需要保存连续字符出现的次数，空间复杂度为O(n)；

定位问题：

统计相似子串的数量。

数据操作分析：

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

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

编码实现：

存储中间数据

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;
    }

}

在遍历中统计符合条件的子串数

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;
    }
}

LeetCode-696.计数二进制子串