计数二进制子串

题目链接：https://leetcode-cn.com/problems/count-binary-substrings/

暴力超时了的代码：90个样例只过了37个

class Solution {
    public int countBinarySubstrings(String s) {
        int res = 0;
        for(int i=0;i<s.length();i++){
            for(int j=i+2;j<=s.length();j+=2){
                if(isValid(s.substring(i,j))) res++;
            }
        }

        return res;
    }
    private boolean isValid(String s){
        if(s.substring(0,s.length()/2).contains(s.charAt(s.length()/2)+""))
        return false;
        if(s.substring(s.length()/2,s.length()).contains(s.charAt(s.length()/2-1)+""))
        return false;
        return true;
    }
}

官方题解

将001100111这样的数串以2223的形式存到数组中然后进行两两比较，选较小的那个就是那个区域的所有满足条件的子串数目。

class Solution {
    public int countBinarySubstrings(String s) {
       List<Integer> cnts = new ArrayList<>(); 
       int n = s.length();
       int i = 0;
       while(i < n){
         char ch = s.charAt(i);
         int cnt = 0;
         while(i < n && s.charAt(i) == ch){
            i++;
            cnt++;
            }
            cnts.add(cnt);
        }
        int ans = 0;
        for(int j=0;j<cnts.size()-1;j++){
            ans += Math.min(cnts.get(j),cnts.get(j+1));
        }
        return ans;
    }
}

和官方给的题解一个意思，优化了空间消耗，因为后一个只与前一个有关
代码参考评论区

class Solution {
    public int countBinarySubstrings(String s) {
        int n = s.length();
        // pre 前一个数字连续出现的次数，cur 当前数字连续出现的次数
        int cur=1,pre=0,ans=0;
        for(int i=0;i<n-1;i++){
             // 判断当前数字是否与后一个数字相同
            if(s.charAt(i) == s.charAt(i+1)) cur++;// 相同，则当前数字出现的次数cur加1
            else{// 不同，则当前数字事实上变成了前一个数字，当前数字的次数重置为1
                pre = cur;
                cur = 1;
            }
            if(pre >= cur) ans++; // 前一个数字出现的次数 >= 后一个数字出现的次数，则一定包含满足条件的子串
        }
        return ans;
    }
}