CountBinarySubstrings [source code]

public class CountBinarySubstrings {
static
/******************************************************************************/
class Solution {
    public int countBinarySubstrings(String s) {
        char[] chs = s.toCharArray ();
        if (chs.length == 0)
            return 0;
        Character curChar = null;
        int prevLen = -1, curLen = 0, resCount = 0;
        for (int i = 0; i < chs.length; i++) {
            if (curChar == null) {
                curChar = chs[i];
                curLen = 1;
            } else if (chs[i] != curChar) {
                if (prevLen > 0)
                    resCount += Math.min (prevLen, curLen);
                prevLen = curLen;
                curChar = chs[i];
                curLen = 1;
            } else {
                curLen++;
            }
        }
        if (prevLen > 0)
            resCount += Math.min (prevLen, curLen);
        return resCount;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        CountBinarySubstrings.Solution tester = new CountBinarySubstrings.Solution();
        String[] inputs = {
            "00110", "3",
            "00110011", "6",
            "10101", "4",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String s = inputs[2 * i];
            int ans = Integer.parseInt (inputs[2 * i + 1]);
            System.out.println (Printer.separator ());
            int output = tester.countBinarySubstrings (s);
            System.out.printf ("%s -> %s, expected: %d\n",
                s, Printer.wrapColor (output, output == ans ? "green" : "red"), ans
            );
        }
    }
}

看起来应该还是一个很简单的题目; 不过这个题目, 假如去掉说, 要求连续这个条件, 你怎么写? 应该能想到用sliding window来写;

这种分段类的stream算法其实我写的还是不够熟练, 不过我这里还是提醒一下自己, 反正循环body里面, 还是想清楚有都少种情况, 枚举一下就行了;

另外, 这种分段算法, 还是要记得收尾问题;

写了半天好像写错了, 我还以为这题要算的是max length, 但是后来一看题目, 要的是一个count, 好像这个就要稍微复杂一些了;

在写代码的过程中发现的一个技巧: 在char的0/1之间toggle:

java> c = '0'  
java.lang.Character c = 0  
java> c = 1 - (c - '0') + '0'  
java.lang.Integer c = 49  
java> c = 1 - (c - '0') + '0'  
java.lang.Integer c = 48  
java> c = 1 - (c - '0') + '0'  
java.lang.Integer c = 49  
java> c = 1 - (c - '0') + '0'  
java.lang.Integer c = 48

总体来说应该说还是一个很简单的题目, 可惜最后还是超时了, 还是基本功不够扎实; 分段算法我一般的套路就是:

initialize PREV to NULL
body has branches:
- first iteration
- maintaining iteration
- differing iteration
收尾

不过最后这题还是没有做到一次成功, 是因为忽略了假如只有一段的情况, 这种情况下我具体算法的写法就有问题了;

最后的速度是26ms (86%), 可以接受;

这个是editorial1:

class Solution {  
    public int countBinarySubstrings(String s) {  
        int[] groups = new int[s.length()];  
        int t = 0;  
        groups[0] = 1;  
        for (int i = 1; i < s.length(); i++) {  
            if (s.charAt(i-1) != s.charAt(i)) {  
                groups[++t] = 1;  
            } else {  
                groups[t]++;  
            }  
        }  

        int ans = 0;  
        for (int i = 1; i <= t; i++) {  
            ans += Math.min(groups[i-1], groups[i]);  
        }  
        return ans;  
    }  
}

虽然做了两个pass, 但是算法本身非常的易懂; 注意, 如果让你进行一个类似这里的统计段落的操作, 你能做到吗?

editorial2就是1pass:

public class Solution {  
    public int countBinarySubstrings(String s) {  
        int ans = 0, prev = 0, cur = 1;  
        for (int i = 1; i < s.length(); i++) {  
            if (s.charAt(i-1) != s.charAt(i)) {  
                ans += Math.min(prev, cur);  
                prev = cur;  
                cur = 1;  
            } else {  
                cur++;  
            }  
        }  
        return ans + Math.min(prev, cur);  
    }  
}

思路还是差不多的, 不过他避免了我习惯的initialization这一步; 然后body直接从[1]开始. 这个最后没有出问题, 是因为他ans初始化的比较好, 所以就算最后真的是一个长度只有1的s, 最后结果的答案也是保证正确的;

这个是discussion里面一个不需要用min的做法:

public int countBinarySubstrings(String s) {  
    int prevRunLength = 0, curRunLength = 1, res = 0;  
    for (int i=1;i<s.length();i++) {  
        if (s.charAt(i) == s.charAt(i-1)) curRunLength++;  
        else {  
            prevRunLength = curRunLength;  
            curRunLength = 1;  
        }  
        if (prevRunLength >= curRunLength) res++;  
    }  
    return res;  
}

稍微简化了一些. 这个通过直接比较来判断是否需要更新res的思路, 其实我也大概想到了; 不过最后本质上是类似的;

这题我拿到的时候我就感觉用正则可能比较好写, 但是不知道具体做法应该怎么实现, 结果果然就有人用一个类似的做法:

@lee215 said in Python easy and concise solution (only 2 lines):

First, I count the number of 1 or 0 grouped consecutively.
For example "0110001111" will be [1, 2, 3, 4].

Second, for any possible substrings with 1 and 0 grouped consecutively, the number of valid substring will be the minimum number of 0 and 1.
For example "0001111", will be min(3, 4) = 3, ("01", "0011", "000111")

def countBinarySubstrings(self, s):  
        s = map(len, s.replace('01', '0 1').replace('10', '1 0').split())  
        return sum(min(a, b) for a, b in zip(s, s[1:]))

注意看他怎么分段的: 这个replace挺有想法的;

submission最优解: 16(100):

class Solution {  
     public int countBinarySubstrings(String s) {  
        if(s==null || s.length()<=1){  
            return 0;  
        }     
        char[] array = s.toCharArray();  
        int sum = 0;  
        char previousChar = array[0];  
        int count = 1;  
        int previous_count = 0;  
        for(int i=1;i<array.length;i++){  
            if(previousChar==array[i]){  
                count++;  
                if(previous_count>=count){  
                    sum++;  
                }  
            }else{  
                previous_count = count;  
                previousChar = array[i];  
                count = 1;  
                sum++;  
            }  
        }  

        return sum;  
    }  
}

跟我的做法基本是没有区别的, 不过他也是从1开始, 避免了initialization这一步;

Problem Description

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"  
Output: 6  
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".  

Notice that some of these substrings repeat and are counted the number of times they occur.  

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"  
Output: 4  
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.
s will only consist of "0" or "1" characters.

Difficulty:Easy
Total Accepted:9.2K
Total Submissions:17.8K
Contributor:fishercoder
Companies
helix
Related Topics
string
Similar Questions
Encode and Decode Strings

Hide Hint 1

How many valid binary substrings exist in "000111", and how many in "11100"? What about "00011100"?

LC696 CountBinarySubstrings

CountBinarySubstrings [source code]

Problem Description

results matching ""

No results matching ""