LeetCode696. 计数二进制子串-蒲公英云

LeetCode696. 计数二进制子串

末蓝、 2022-05-20 07:24 320阅读 0赞

给定一个字符串 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”字符。

思路：首先想到暴力解法，两层循环找出s的所有子串进行判断，结果跟预料的差不多，会超出时间限制。

解法一：（超出时间限制）

class Solution {
    public int countBinarySubstrings(String s) {
        if(s==null||s.length()==0) {
             return 0;
         }
         int count=0;
         for(int i=0;i<s.length();i++) {
             for(int j=i+1;j<=s.length();j++) {
                 String tempS=s.substring(i, j);
                // System.out.println(tempS);
                 if(isTrue(tempS)) {
                     count++;
                 }
             }
         }
         return count;
    }
    //判断s是否0,1组合且数量相同，0与0组合，1与1组合
    public static boolean isTrue(String s) {
        int len=s.length();
        if(len%2!=0) {
            return false;
        }
        if(s.charAt(0)==s.charAt(len-1)) {
            return false;
        }
        for(int i=0;i<len/2-1;i++) {
            if(s.charAt(i)!=s.charAt(i+1)) {
                return false;
            }
        }
        for(int i=len/2;i<len-1;i++) {
            if(s.charAt(i)!=s.charAt(i+1)) {
                return false;
            }
        }
    //    System.out.println(s);
        return true;
    }
}

解法二：将连续的0,1个数存入数组中，遍历数组取两两之间最小的个数求和。

class Solution {
    public int countBinarySubstrings(String s) {
         if(s==null||s.length()<=1) {
             return 0;
         }
         int count=0;
         int a[]=new int[s.length()]; //用来存储连续0,1的个数
         char ch[]=s.toCharArray();
         int temp=0;   //连续0,1的长度
         for(int i=0;i<s.length()-1;i++) {
             a[temp]++;
             if(ch[i]!=ch[i+1]) {
                 temp++;
             }
         }
         a[temp]++;
         for(int i=0;i<temp;i++) {
             count+=Math.min(a[i], a[i+1]);
         }
         return count;
    }
}