专栏首页Michael阿明学习之路LeetCode 696. 计数二进制子串

LeetCode 696. 计数二进制子串

1. 题目

给定一个字符串 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”字符。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/count-binary-substrings 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 一次遍历解题

题目的意思是:有多少对子串,其0,1个数相同,且其所有的0和0,1和1在一起的

  • 用prev记录前面相同的有多少(例如3个0)
  • 用cur记录后面相同的有多少(例如2个1)
  • 每当prev>=cur时就有一个满足题目的子串
class Solution {
public:
    int countBinarySubstrings(string s) {
        int prev = 0, cur = 1, ans = 0;
        for(int i = 1; i < s.size(); ++i)
        {
        	if(s[i-1] == s[i])
        		cur++;
        	else//不等了
        	{
        		prev = cur;
        		cur = 1;
        	}
        	if(prev >= cur)
        		ans++;
        }
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 872. 叶子相似的树

    请考虑一颗二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

    Michael阿明
  • LeetCode 1383. 最大的团队表现值(贪心,优先队列,难)

    公司有编号为 1 到 n 的 n 个工程师,给你两个数组 speed 和 efficiency ,其中 speed[i] 和 efficiency[i] 分别代...

    Michael阿明
  • LeetCode 430. 扁平化多级双向链表(DFS)

    您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如...

    Michael阿明
  • 老司机开车,教会女朋友什么是「马拉车算法」

    马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

    五分钟学算法
  • 老司机开车,教会女朋友什么是「马拉车算法」

    马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

    帅地
  • JavaScript实现图片懒加载

    1、 将图片真实路径赋值到img标签的data-src属性中,而不是src属性 2、 获取img节点距离浏览器顶部的距离,如果小于或等于浏览器窗口的可视高度,...

    Javanx
  • 极客资源丨那些被“慕课网”偷偷藏起来的“真·免费教程”!

    一川水巷
  • Spring(4)——面向切面编程(AOP模块)

    Spring AOP 简介 如果说 IoC 是 Spring 的核心,那么面向切面编程就是 Spring 最为重要的功能之一了,在数据库事务中切面编程被广泛使用...

    我没有三颗心脏
  • HTML的简介和历史发展过程

    这次写一篇对于HTML以及CSS的简介,平常我们大家都知道的编程语言有很多种,比如Java、C++、Python等等,每种编程语言都有其独具的特色,不论是语法格...

    泰斗贤若如
  • 文言文不能编程乎?中国大四小哥哥曰:非也

    这就是最近被盛传的:文言文编程语言“wenyan-lang”。GitHub上线5天时间,已经突破了6000星。

    新智元

扫码关注云+社区

领取腾讯云代金券