696.Count Binary Substrings

约定不等于承诺〃 2022-05-30 06:38 114阅读 0赞

> 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.

**题目描述**：给定一个由0和1组成的非空字符串，计算出由相同0和1且0和1分别连续的子串的个数。子串可以重复。

**思路**：使用2个变量来存储当前数字前的数字连续次数pre以及当前数字的连续次数cur。  
如果当前数字与前一个数字连续，则计算出当前数字连续的次数cur，否则统计当前数字之前的数字连续次数pre并令当前数字连续次数cur为1。  
接着通过判断统计子数组的个数，如果这时该数字之前的数字连续次数pre大于等于当前数字连续次数cur，则令子数组个数res加1。

如果不理解，按照该代码自行调试一遍，列出每次res加1所对应的子数组方便理解。

例如 “00110”，存在连续子数组“01”，“0011”，“10”。

Your runtime beats 25.49 % of java submissions.

--------------------

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;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，114人围观）

还没有评论，来说两句吧...

相关阅读

相关 1638. Count Substrings That Differ by One Character

Given two strings `s` and `t`, find the number of ways you can choose a non-empty substr

梦里梦外;/ 2024年03月23日 15:58/ 0 赞/ 29 阅读

相关 C++ STL常用算法-62-查找算法_binary_search/count/count_if

前面一篇学习了常用查找算法的三个方法，现在接着学习剩下三个查找相关的算法。binary\_search，这个二分查找，在任何语言中都是重点需要掌握的，面试经常被考察。二分查找是

骑猪看日落/ 2022年11月29日 14:29/ 0 赞/ 111 阅读

相关 LeetCode - Easy - 696. Count Binary Substrings

Topic String Description [https://leetcode.com/problems/count-binary-substring

Dear 丶/ 2022年11月16日 08:04/ 0 赞/ 30 阅读

相关 php之substr_count判断一个字符串是否包含另一个字符串

If you only want to look, if a string appears in another string - even at position 0 - ,

偏执的太偏执、/ 2022年07月11日 15:20/ 0 赞/ 292 阅读

相关 leetcode 696. Count Binary Substrings 连续出现相同次数0或1子串数量 + 很棒的做法

Give a string s, count the number of non-empty (contiguous) substrings that have the sam

灰太狼/ 2022年06月03日 08:39/ 0 赞/ 132 阅读

相关 696.Count Binary Substrings

> Give a string s, count the number of non-empty (contiguous) substrings > that have t

约定不等于承诺〃/ 2022年05月30日 06:38/ 0 赞/ 115 阅读

相关 uva 696 - How Many Knights

[题目链接：uva 696 - How Many Knights][uva 696 - How Many Knights] 题目大意：给出一个n \ m的网格，计算

刺骨的言语ヽ痛彻心扉/ 2022年05月12日 23:26/ 0 赞/ 101 阅读

相关 LeetCode之Count Binary Substrings（Kotlin）

> 问题： Give a string s, count the number of non-empty (contiguous) substrings that have t

- 日理万妓/ 2022年03月16日 14:14/ 0 赞/ 119 阅读

相关 substr_count() 函数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlbmd5

傷城~/ 2022年03月15日 15:58/ 0 赞/ 216 阅读

相关 Leetcode PHP题解--D88 696. Count Binary Substrings

D88 696. Count Binary Substrings 题目链接 [696. Count Binary Substrings][] 题目分析给定

桃扇骨/ 2022年01月12日 00:47/ 0 赞/ 135 阅读