( 字符串) 696. 计数二进制子串 ——【Leetcode每日一题】

news/2024/2/21 3:39:27

❓696. 计数二进制子串

难度:简单

给定一个字符串 s,统计并返回具有相同数量 01 的非空(连续)子字符串的数量,并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现(不同位置)的子串也要统计它们出现的次数。

示例 1:

输入:s = “00110011”
输出:6
解释:6 个子串满足具有相同数量的连续 1 和 0 :“0011”、“01”、“1100”、“10”、“0011” 和 “01” 。
注意,一些重复出现的子串(不同位置)要统计它们出现的次数。
另外,“00110011” 不是有效的子串,因为所有的 0(还有 1 )没有组合在一起。

示例 1:示例 2:

输入:s = “10101”
输出:4
解释:有 4 个子串:“10”、“01”、“10”、“01” ,具有相同数量的连续 1 和 0 。

提示:

  • 1 < = s . l e n g t h < = 1 0 5 1 <= s.length <= 10^5 1<=s.length<=105
  • s[i]'0''1'

💡思路:

法一:中心扩展法

  • 从字符串的某一位置为中心,尝试着在两边扩展子字符串。

和 647. 回文子串 类似。

法二:

由于要求子字符串中的所有 0 和所有 1 都是成组连续的,所以只需统计字符串 s 中相对 01 连续出现的个数,然后只需比较相邻的连续01

从左往右遍历数组 s,记录和当前位置数字相同且连续的长度cur,以及其之前连续的不同数字的 长度pre

  • 如果当前字符和前一个字符相等,则cur++
  • 如果不相等,则取precur的最小值,此最小值,就是可以拼成满足条件的字串个数。
    • 例如111001,当遍历到最后一个1时,于前面的0不同,则比较precur,此时的pre = 3 (最前面的连续的3个1)cur = 2 (中间的连续的2个0)
    • 取最小值,即有两个满足条件的字串,分别为:101100

🍁代码:(Java、C++)

Java

class Solution {public int countBinarySubstrings(String s) {int cnt = 0;for(int i = 0; i < s.length() - 1; i++){if(s.charAt(i) != s.charAt(i + 1)){cnt++;int l = i - 1, r = i + 2;while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(l + 1) &&s.charAt(r) == s.charAt(r - 1)){cnt++;l--;r++;}}}return cnt;}
}

C++

class Solution {
public:int countBinarySubstrings(string s) {int cnt = 0;for(int i = 0; i < s.size() - 1; i++){if(s[i] != s[i + 1]){cnt++;int l = i - 1, r = i + 2;while(l >= 0 && r < s.size() && s[l] == s[l + 1] && s[r] == s[r - 1]){cnt++;l--;r++;}}}return cnt;}
};

法二:
Java

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

C++

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

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为字符串s的长度;而中心扩展法为 O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/58362.html

相关文章

c#笔记-运算符

一元运算符 数字运算 正负 在数字前面&#xff0c;或数字类型的变量前面使用正负号&#xff0c;可以表示这个数值取自己&#xff0c;或是取相反数。 int i1 3; int i2 -3; int i3 i2;//-3 int i4 -i2;//3自增 一个数字类型在自己前面或后面连写两个或-&#xff0c;可以…

PySpark基础入门(3):RDD持久化

RDD的持久化 RDD 的数据是过程数据&#xff0c;因此需要持久化存储&#xff1b; RDD之间进行相互迭代的计算&#xff0c;新的RDD的生成代表着旧的RDD的消失&#xff1b;这样的特性可以最大化地利用资源&#xff0c;老旧地RDD可以及时地从内存中清理&#xff0c;从而给后续地计…

Android逆向实战(一)腾讯新闻去开屏广告

上次反编译一个工具类app失败&#xff0c;原因是使用了360加固&#xff0c;回编译后无法启动。一般来讲&#xff0c;大厂的app考虑到性能、兼容性、包体积等&#xff0c;通常不用加固。因此&#xff0c;本次我们选一个大一些的app-腾讯新闻。写在前面&#xff1a;本篇博客仅用来…

【LeetCode股票买卖系列:122. 买卖股票的最佳时机 II | 贪心 | 暴力递归=>记忆化搜索=>动态规划】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

PHP面试宝典之Mysql数据库基础篇

字符类型&#xff1a; tinyint(4)&#xff1a;占1个字节&#xff0c;4代表字段值长度&#xff0c;用0填充&#xff0c;搭配zero fill使用 有符号&#xff1a;取值范围 负128 &#xff5e; 正127&#xff1b; 无符号&#xff1a;取值范围 0 &#xff5e; 255&#xff1b; 默认无…

APK文件结构

文件结构 assets文件用来存放需要打包到Android 应用程序的静态资源文件&#xff0c;例如图片资源文件&#xff0c;JSON配置文件&#xff0c;渠道配置文件&#xff0c;二进制数据文件&#xff0c;HTML5离线资源文件等 与res/raw目录不同的数&#xff0c;assets目录支持任意深度…

【数据分析之道-NumPy(四)】numpy广播机制

文章目录 专栏导读1、广播机制2、一维数组和二维数组的广播3、二维数组和三维数组的广播4、标量和数组的广播5、形状不兼容的数组不能进行广播 专栏导读 ✍ 作者简介&#xff1a;i阿极&#xff0c;CSDN Python领域新星创作者&#xff0c;专注于分享python领域知识。 ✍ 本文录入…

【LeetCode】221.最大正方形

221.最大正方形&#xff08;中等&#xff09; 题解 对于在矩阵内搜索正方形或长方形的题型&#xff0c;一种常见的做法是&#xff1a;定义一个二维 dp 数组&#xff0c;其中 dp[i][j] 表示满足题目条件的、以&#xff08;i,j&#xff09;为右下角的正方形或长方形属性。在本题中…

day11 TCP连接管理与UDP协议

目录 ​编辑 连接的建立——”三次握手” 连接的释放——“四次挥手” 保活计时器 用户数据报协议 UDP​编辑 连接的建立——”三次握手” TCP 建立连接的过程叫做握手。 采用三报文握手&#xff1a;在客户和服务器之间交换三个 TCP 报文段&#xff0c;以防止已失效的连接…

使用pg_basebackup备份

参考文档&#xff1a; http://postgres.cn/docs/14/app-pgbasebackup.html http://postgres.cn/docs/12/runtime-config-wal.html postgres版本 test# select version(); version …

ChatGPT技术原理 第八章:GPT与对话生成

目录 8.1 GPT在对话生成中的应用 8.2 基于GPT的对话生成模型 8.3 对话历史表示方法 8.4 策略学习

C#,生信软件实践(02)——DNA数据库EMBL格式详解及转为FASTA格式文件的源代码

>生信老白写的基础代码.fasta MAYBENOANYUSAGE 1 EMBL 1.1 EMBL组织 欧洲分子生物学实验室EMBL&#xff08;European Molecular Biology Laboratory&#xff09;1974年由欧洲14个国家加上亚洲的以色列共同发起建立&#xff0c;现在由欧洲30个成员国政府支持组成&#xf…

程序员都有哪些就业方向?不是所有人都能去互联网公司的!

程序员有哪些借给方向呢 不是所有人都能进互联网公司 就算你进互联网大厂 具体的工作内容 可能跟你想象的也不一样 今天咱们就聊聊程序员 都有哪些可以选择的方向吧 主要是我是刚才想了想 梳理梳理这个程序员主要就业方向 主要有四个方向 一个是互联网公司 再一个第二个就是软件…

REMIX:重构·连接·进化|徐亚波博士D3大会演讲实录

“欢迎大家和数说故事一起来到新世界&#xff0c;和我们一起&#xff0c;来玩一个AI普适场景的无限游戏。” 在数说故事第六届D3智能营销峰会上&#xff0c;数说故事创始人兼CEO徐亚波博士带来「REMIX——重构连接进化」的主题分享&#xff0c;聚焦“ChatGPT开启的AGI时代有什么…

docker容器:本地私有仓库、harbor私有仓库部署与管理

一、本地私有仓库 1、本地私有仓库简介 docker本地仓库&#xff0c;存放镜像&#xff0c;本地的机器上传和下载&#xff0c;pull/push。 使用私有仓库有许多优点&#xff1a; ①节省网络带宽&#xff0c;针对于每个镜像不用每个人都去中央仓库上面去下载&#xff0c;只需要从…

第二十七章 Unity碰撞体Collision(下)

本章节我们继续研究碰撞体&#xff0c;并且探索一下碰撞体与刚体之间的联系。我们回到之前的工程&#xff0c;然后给我们的紫色球体Sphere1也添加一个刚体组件。如下所示 此时&#xff0c;两个球体都具备了碰撞体和刚体组件。接下来&#xff0c;我们Play运行查看效果 我们发现&…

用于无线传感器网络路由的改进leach协议(Matlab代码实现)

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f468;‍&#x1f4bb;4 Matlab代码 &#x1f4a5;1 概述 当前&#xff0c;无线传感器由于技术的发展得到更加广泛的应用&#xff0c;针对无线传感器网络&#xff08;WSN&#xff09;的…

SpringCloud:微服务保护之雪崩问题及解决方案

1.雪崩问题 微服务中&#xff0c;服务间调用关系错综复杂&#xff0c;一个微服务往往依赖于多个其它微服务。 如图&#xff0c;如果服务提供者I发生了故障&#xff0c;当前的应用的部分业务因为依赖于服务I&#xff0c;因此也会被阻塞。此时&#xff0c;其它不依赖于服务I的业…

Redis 实战篇:巧用 Bitmap 实现亿级海量数据统计

目录 二值状态统计判断用户登陆态SETBIT 命令GETBIT 命令第一步&#xff0c;执行以下指令&#xff0c;表示用户已登录。第二步&#xff0c;检查该用户是否登陆&#xff0c;返回值 1 表示已登录。第三步&#xff0c;登出&#xff0c;将 offset 对应的 value 设置成 0。 用户每个…

测试工程师用了3个月从月薪8k涨到12k,我是这么做到的?

先说一下自己的个人情况&#xff0c;大专生&#xff0c;18年通过校招进入湖南金蝶软件公司&#xff0c;干了接近3年的测试工程师&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01; 而我已经在一个企…
最新文章