开发者社区> 李博 bluemind> 正文

[LeetCode] Count Binary Substrings 统计二进制子字符串

简介:
+关注继续查看

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.

这道题给了我们一个二进制字符串,然后我们统计具有相同0和1的个数,且0和1各自都群组在一起(即0和1不能交替出现)的子字符串的个数,题目中的两个例子也很能说明问题。那么我们来分析题目中的第一个例子00110011,符合要求的子字符串要求0和1同时出现,那么当第一个1出现的时候,前面由于前面有两个0,所以肯定能组成01,再遇到下一个1时,此时1有2个,0有2个,能组成0011,下一个遇到0时,此时0的个数重置为1,而1的个数有两个,所以一定有10,同理,下一个还为0,就会有1100存在,之后的也是这样分析。那么我们可以发现我们只要分别统计0和1的个数,而且如果当前遇到的是1,那么只要之前统计的0的个数大于当前1的个数,就一定有一个对应的子字符串,而一旦前一个数字和当前的数字不一样的时候,那么当前数字的计数要重置为1。所以我们遍历元数组,如果是第一个数字,那么对应的ones或zeros自增1。然后进行分情况讨论,如果当前数字是1,然后判断如果前面的数字也是1,则ones自增1,否则ones重置为1。如果此时zeros大于ones,res自增1。反之同理,如果当前数字是0,然后判断如果前面的数字也是0,则zeros自增1,否则zeros重置为1。如果此时ones大于zeros,res自增1。参见代码如下:

解法一:

public:
    int countBinarySubstrings(string s) {
        int zeros = 0, ones = 0, res = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (i == 0) {
                (s[i] == '1') ? ++ones : ++zeros;
            } else {
                if (s[i] == '1') {
                    ones = (s[i - 1] == '1') ? ones + 1 : 1;
                    if (zeros >= ones) ++res;
                } else if (s[i] == '0') {
                    zeros = (s[i - 1] == '0') ? zeros + 1 : 1;
                    if (ones >= zeros) ++res;
                }
            }
        }
        return res;
    }
};

下面这种方法更加简洁了,不用具体的分0和1的情况来讨论了,而是直接用了pre和cur两个变量,其中pre初始化为0,cur初始化为1,然后从第二个数字开始遍历,如果当前数字和前面的数字相同,则cur自增1,否则pre赋值为cur,cur重置1。然后判断如果pre大于等于cur,res自增1。其实核心思想跟上面的方法一样,只不过pre和cur可以在0和1之间切换,参见代码如下:

解法二:

public:
    int countBinarySubstrings(string s) {
        int res = 0, pre = 0, cur = 1, n = s.size();
        for (int i = 1; i < n; ++i) {
            if (s[i] == s[i - 1]) ++cur;
            else {
                pre = cur;
                cur = 1;
            }
            if (pre >= cur) ++res;
        }
        return res;
    }
};

参考资料:

https://discuss.leetcode.com/topic/107096/java-o-n-time-o-1-space

本文转自博客园Grandyang的博客,原文链接:[LeetCode] Count Binary Substrings 统计二进制子字符串

,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
写一个函数对字符串数组排序,使所有变位词都相邻
题目 写一个函数对字符串数组排序,使得所有的变位词都相邻。 解答 首先,要弄清楚什么是变位词。变位词就是组成的字母相同,但顺序不一样的单词。 比如说:live和evil就是一对变位词。OK,那么这道题目的意思就很清楚了, 它并不要求我们将字符串数组中的字符串按字典序排序,否则我们直接调用STL中的sort 函数就可以了。
839 0
用二进制来编码字符串&quot;adceadaa&quot;,需要能够相据编码,解码回原来的字符串,则至少需要二进制字符的长度是?
利用哈夫曼编码,字符出现的频率越大,则使用越短的二进制进行编码,构建最优二叉树。
793 0
C实现特定字符串数据的排序与输出
一、案例完整代码 点击(此处)折叠或打开 /**************************************************************** * Name : sort_and_output.c * Author : dyli2000 * Date : 20121102 * Description :     对学生成绩由高到低输出案例。
912 0
二进制/十六进制转浮点数的编程(互转类似)
转换的程序: // 输入十进制整数,输出同样内存排布的float表示 inline float i2f(int i) { float f = 0; assert(sizeof(int) == sizeof(float...
883 0
给定一个字符串类型表示的小数,输出其二进制表示
题目 给定一个字符串类型(string)表示的小数,打印出它的二进制表示。 如果这个数无法精确地表示为二进制形式,输出”ERROR”。 解答 整数部分通过不断地对2取余然后除以2来得到其二进制表示, 或是不断地和1按位与然后除以2得到其二进制表示。
714 0
使用mysqlbinlog提取二进制日志
    MySQL binlog日志记录了MySQL数据库从启用日志以来所有对当前数据库的变更。binlog日志属于二进制文件,我们可以从binlog提取出来生成可阅读的SQL语句来重建当前数据库以及根据需要实现时点恢复或不完全恢复。
838 0
巧用JSON.stringify()生成漂亮格式的JSON字符串
巧用JSON.stringify()生成漂亮格式的JSON字符串 使用JavaScript处理XML基本上就是一个杯具,这也是JSON在程序开发中广受欢迎的原因。我曾经写过一个 JavaScript函数来将XML转换为JSON,那种~duang~duang~的痛点简直是折腾得你欲死欲仙。
863 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
2107
文章
1103
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载