LeetCode696. 计数二进制子串

末蓝、 2022-05-20 07:24 221阅读 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;
        }
    }