当前位置: 首页 > news >正文

LeetCode 每日一题 统计满足 K 约束的子字符串数量 I

统计满足 K 约束的子字符串数量 I

给你一个 二进制 字符串 s 和一个整数 k。
如果一个 二进制字符串 满足以下任一条件,则认为该字符串满足 k 约束:
字符串中 0 的数量最多为 k。
字符串中 1 的数量最多为 k。
返回一个整数,表示 s 的所有满足 k 约束 的子字符串的数量。
示例 1:
输入:s = “10101”, k = 1
输出:12
解释:
s 的所有子字符串中,除了 “1010”、“10101” 和 “0101” 外,其余子字符串都满足 k 约束。
示例 2:
输入:s = “1010101”, k = 2
输出:25
解释:
s 的所有子字符串中,除了长度大于 5 的子字符串外,其余子字符串都满足 k 约束。
示例 3:
输入:s = “11111”, k = 1
输出:15
解释:
s 的所有子字符串都满足 k 约束。

题解

需要统计所有满足条件的子串

由于子串的长度是不定的,所以不能直接用到滑动窗口去遍历

我们可以枚举子串的右端点 i ,寻找以 i 为右端点的子串有多少满足条件

将 i 从 0 遍历到字符串长度的 n-1 就可以找到所有满足条件的子串

只要某一点为左端点的子串满足条件,那么从这个左端点到右端点的所有点都可以作为子串的左端点并且满足条件

所以我们需要找到对于右端点 i 满足条件的最小左端点

根据题意,我们不难发现,只要子串的长度越小,就越有可能满足条件

也就是说,当 i 越大,满足的最小左端点就越大

最小左端点是单调的

也就是说,最小左端点只能增大

所以我们就可以使用滑动窗口来维护子串

  • 对于一个右端点 i
  • 如果此时的最小最左端点 l 与 右端点形成的子串满足条件
  • 则说明右端点为 i 的满足条件的子串有 r-l+1 个
  • 如果此时最小最左端点 l 与 右端点形成的子串不满足条件
  • 则 l++,直到满足条件
  • 右端点为 i 的满足条件的子串有 r-l+1 个

代码如下↓

int countKConstraintSubstrings(char* s, int k) {int l=0;int res=0;int a0=0;int a1=0;int n=strlen(s);for(int i=0;i<n;i++){if(s[i]=='0'){a0++;}else{a1++;}while(a0>k && a1>k){if(s[l]=='0'){a0--;}else{a1--;}l++;}res+=i-l+1;}return res;
}

时间复杂度为 O(n)
虽然有两层循环,但是由于 l 只能进行 ++
所以内层循环总共最多执行 n 次
时间复杂度为 O(n)


http://www.mrgr.cn/news/75212.html

相关文章:

  • 深入探索:Scrapy深度爬取策略与实践
  • C++20 概念与约束(1)—— SFINAE
  • aws申请ssl证书的方法【该证书仅供aws】
  • Spring学习笔记_37——@RequestMapping衍生注解
  • 3216. 交换后字典序最小的字符串
  • Chrome使用IE内核
  • AI视觉小车基础--2.按键读取
  • 【MYSQL】数据库日志 (了解即可)
  • Linux 驱动
  • 机器学习(1)
  • [DB]
  • [ICML 2024]Learning High-Order Relationships of Brain Regions
  • 超全面!一文带你快速入门HTML,CSS和JavaScript!
  • pip install volcengine-python-sdk报错
  • 【027B】基于51单片机模拟电梯(点阵)【Proteus仿真+Keil程序+报告+原理图】
  • Spring Validation参数校验
  • CDA LEVEL 2考试大纲
  • 从源码一把聊清楚nacos2.x的事件驱动架构,从迷茫到精通!!
  • 【easily-openJCL】要尝试下用 显卡 做数据对称加密吗?
  • Netty之EventLoop自定义任务
  • 自动驾驶系列—从数据采集到存储:解密自动驾驶传感器数据采集盒子的关键技术
  • Ubuntu 的 ROS 操作系统 turtlebot3 导航仿真
  • 输出1~100内的所有偶数C++
  • SpringSecurity入门
  • ubuntu连接orangepi-zero-2w桌面的几种方法
  • 深入浅出C#编程语言