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

【滑动窗口】LeetCode2953:统计完全子字符串

作者推荐

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

本题其它解法

【离散差分】LeetCode2953:统计完全子字符串

题目

给你一个字符串 word 和一个整数 k 。
如果 word 的一个子字符串 s 满足以下条件,我们称它是 完全字符串:
s 中每个字符 恰好 出现 k 次。
相邻字符在字母表中的顺序 至多 相差 2 。也就是说,s 中两个相邻字符 c1 和 c2 ,它们在字母表中的位置相差 至多 为 2 。
请你返回 word 中 完全 子字符串的数目。
子字符串 指的是一个字符串中一段连续 非空 的字符序列。
示例 1:
输入:word = “igigee”, k = 2
输出:3
解释:完全子字符串需要满足每个字符恰好出现 2 次,且相邻字符相差至多为 2 :igigee, igigee, igigee 。
示例 2:
输入:word = “aaabbbccc”, k = 3
输出:6
解释:完全子字符串需要满足每个字符恰好出现 3 次,且相邻字符相差至多为 2 :aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。
参数范围
1 <= word.length <= 105
word 只包含小写英文字母。
1 <= k <= word.length

滑动窗口

周赛的时候,忽略了:完全子字符串的长度是k的1到26倍。

时间复杂度

O(nmm)。n是字符串的长度,m的字符种类,也就是26。枚举字符结尾:O(n);枚举窗口长度:O(m);统计合法字符数量O(m)。

变量解析

m_aCharNumsiWindowWidth个字符,各字母的数量

代码

核心代码

class Solution {
public:
int countCompleteSubstrings(string word, int k) {
m_iK = k;
int pre = 0;
int iRet = 0;
for (int i = 0; i < word.length(); i++)
{
if (i && (abs(word[i] - word[i - 1]) > 2))
{
iRet += Do(word.data()+pre, i - pre);
pre = i;
}
}
iRet += Do(word.data() + pre, word.length() - pre);
return iRet;
}
int Do(const char* p ,int len)
{
int iRet = 0;
auto AddNum = &
{
for (int i = 0; i < 26; i++)
{
if ((0 != m_aCharNums[i]) && (m_iK != m_aCharNums[i]))
{
return;
}
}
iRet++;
};
int iWindowWidth = 0;
for (int i = 1; (i <= 26)&&((iWindowWidth=m_iK*i)<= len); i++)
{
memset(m_aCharNums, 0, sizeof(m_aCharNums));
int j = 0;
for (; j < iWindowWidth; j++)
{
m_aCharNums[p[j] - ‘a’]++;
}
AddNum();
for (;j < len; j++)
{
m_aCharNums[p[j] - ‘a’]++;
m_aCharNums[p[j - iWindowWidth] - ‘a’]–;
AddNum();
}
}
return iRet;
}
int m_aCharNums[26];
int m_iK;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
string s;
int k, res;
{
Solution slu;
s = “ba”;
k = 1;
auto res = slu.countCompleteSubstrings(s, k);
Assert(3, res);
}
{
Solution slu;
s = “gvgvvgv”;
k = 2;
auto res = slu.countCompleteSubstrings(s, k);
Assert(1, res);
}
{
Solution slu;
s = “igigee”;
k = 2;
auto res = slu.countCompleteSubstrings(s, k);
Assert(3, res);
}
{
Solution slu;
s = “aaabbbccc”;
k = 3;
auto res = slu.countCompleteSubstrings(s, k);
Assert(6, res);
}

//CConsole::Out(res);

}

优化

不用每次都判断无法字符的数量,只会修改两个字符的数量,只判断这两个字符就可以了。

时间复杂度

O(nm)。

代码

class Solution {
public:int countCompleteSubstrings(string word, int k) {m_iK = k;int pre = 0;int iRet = 0;for (int i = 0; i < word.length(); i++){if (i && (abs(word[i] - word[i - 1]) > 2)){iRet += Do(word.data()+pre, i - pre);pre = i;}}iRet += Do(word.data() + pre, word.length() - pre);return iRet;}int Do(const char* p ,int len){int iRet = 0;		int iWindowWidth = 0;for (int i = 1; (i <= 26)&&((iWindowWidth=m_iK*i)<= len); i++){memset(m_aCharNums,  0, sizeof(m_aCharNums));int j = 0;for (; j < iWindowWidth; j++){m_aCharNums[p[j] - 'a']++;}int iVilidCount = std::count(m_aCharNums, m_aCharNums + 26, 0) + std::count(m_aCharNums, m_aCharNums + 26, m_iK);if (26 == iVilidCount){iRet++;}auto Change = [&](int index, int iAdd){bool bOld = (0 == m_aCharNums[index]) || (m_iK == m_aCharNums[index]);m_aCharNums[index] += iAdd;bool bNew = (0 == m_aCharNums[index]) || (m_iK == m_aCharNums[index]);iVilidCount += (int)bNew - (int)bOld;};for (;j < len; j++){Change(p[j] - 'a',1);Change(p[j - iWindowWidth] - 'a', -1);iRet += (26 == iVilidCount);}}return iRet;}int m_aCharNums[26];int m_iK;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业

。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙,那算法就是他的是睛|

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:

VS2022 C++17

相关文章:

【滑动窗口】LeetCode2953:统计完全子字符串

作者推荐 [二分查找]LeetCode2040:两个有序数组的第 K 小乘积 本题其它解法 【离散差分】LeetCode2953:统计完全子字符串 题目 给你一个字符串 word 和一个整数 k 。 如果 word 的一个子字符串 s 满足以下条件&#xff0c;我们称它是 完全字符串&#xff1a; s 中每个字符…...

base64转PDF

今天做皖事通的对接&#xff0c;下载电子证照后发现回传的是base64&#xff0c;调试确认是个麻烦事&#xff0c;网上搜了一下没有base64转PDF的在线预览功能&#xff0c;只能自己写个调试工具了&#xff0c;以下是通过纯JS方式写的代码&#xff0c;可直接拿去使用&#xff1a; …...

clip-path,css裁剪函数

https://www.cnblogs.com/dzyany/p/13985939.html clip-path - CSS&#xff1a;层叠样式表 | MDN 我们看下这个例子 polygon里有四个值分别代表这四个点相对于原图左上方的偏移量。 裁剪个五角星...

第二证券:食品饮料板块拉升,乳业股亮眼,西部牧业“20cm”涨停

证券时报网讯&#xff0c;食物饮料板块5日盘中拉升走高&#xff0c;乳业股体现活跃&#xff0c;到发稿&#xff0c;骑士乳业涨超27%&#xff0c;西部牧业“20cm”涨停&#xff0c;阳光乳业亦涨停。 其它个股方面&#xff0c;盖世食物涨超20%&#xff0c;润普食物涨超18%&#…...

React 好用的工具库

1、html-react-parser HTML 到 React 解析器&#xff0c;适用于服务器 &#xff08;Node.js&#xff09; 和客户端&#xff08;浏览器&#xff09;&#xff0c;适用于React节点修改过滤等需求 解析器将 HTML 字符串转换为一个或多个 React 元素。可以将一个元素替换为另一个元素…...

C++面试宝典第2题:逆序输出整数

题目 写一个方法&#xff0c;将一个整数逆序打印输出到控制台。注意&#xff1a;当输入的数字含有结尾的0时&#xff0c;输出不应带有前导的0。比如&#xff1a;123的逆序输出为321&#xff0c;8600的逆序输出为68&#xff0c;-609的逆序输出为-906。 解析 这道题本身并没有什么…...

Twincat功能块使用经验总结

控制全局变量&#xff1a; //轴控制指令 bi_Power: BOOL; //使能 bi_Reset: BOOL; //复位 bi_Stop: BOOL; //停止 bi_JogForward: BOOL; //正向点动 bi_JogBackwards: BOOL; //反向点动 bi_MoveAdditive: BOOL; //增量位…...

香港服务器时间不准,差8小时

解决方案1 1、timedatectl查看系统时间 2、查看系统时区 ls /usr/share/zoneinfo 3、删除当前系统所处时区 rm /etc/localtime 4、创建软链接&#xff0c;以替换当前的时区信息 ln -s /usr/share/zoneinfo/Universal /etc/localtime 解决方案2 手动设置硬件时钟 1、设置系…...

C++ 抽象类和接口 详解

目录 0 引言1 抽象类2 接口2.1 Java与C接口的区别 &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;C专栏&#x1f4a5; 标题&#xff1a;C 抽象类和接口 详解❣️ 寄语&#xff1a;书到用时方恨少&#xff0c;事非经过不知难&#xff01;&#x1f…...

【Linux】awk 使用

awk 输出 // 打印所有列 $ awk {print $0} file // 打印第一列 $ awk {print $1} file // 打印第一和第三列 $ awk {print $1, $3} file // 打印第三列和第一列&#xff0c;注意先后顺序 $ cat file | awk {print $3, $1} …...

LeetCode力扣每日一题(Java):9、回文数

一、题目 二、解题思路 1、我的思路 当x<0时&#xff0c;x一定不是回文数&#xff0c;直接返回false 当x>0且x<10时&#xff0c;x一定是回文数&#xff0c;直接返回true x>10时&#xff0c;先将x转为字符串。将数字转成字符串方法挺多的&#xff0c;以下是&…...

WPF前端实现人脸扫描动画效果

前言 本章实现的效果主要通过OpacityMask与LinearGradientBrush(径向渐变) 的组合应用来实现。最终实现效果如下: LinearGradientBrush线性渐变画刷 LinearGradientBrush其实很简单,我们只需要关注5个属性,使用这5个属性你就可以完成这个画刷几乎所有的变化。 属性介…...

更改AndroidStudio模拟器位置

C盘何等的珍贵&#xff0c;可是好多工具&#xff0c;软件非得默认安装在C盘。。导致C盘越来越紧张。。 在日常使用过程中&#xff0c;安装任何软件都会将其安装到非系统盘下&#xff0c;Android模拟器也不能例外。保护好C盘也是日常一个良好的习惯。 Android AVD默认路径&…...

Dash 协议介绍

<?xml version"1.0" encoding"utf-8"?> <MPD xmlns"urn:mpeg:dash:schema:mpd:2011" minBufferTime"PT1.5S" type"static" mediaPresentationDuration"PT0H1M0.3S" maxSegmentDuration"PT0H0M2.0…...

RabbitMQ的消息发送和接收机制

所有 MQ 产品从模型抽象上来说都是一样的过程&#xff1a; 消费者&#xff08;consumer&#xff09;订阅某个队列。生产者&#xff08;producer&#xff09;创建消息&#xff0c;然后发布到队列&#xff08;queue&#xff09;中&#xff0c;最后将消息发送到监听的消费者。 上…...

记录111

在两台 RHEL 8 服务器上搭建 PostgreSQL 和 pgpool-II 环境涉及到安装 PostgreSQL、配置流复制&#xff08;Streaming Replication&#xff09;以及安装和配置 pgpool-II。以下是详细的步骤&#xff1a; ### 准备工作 1. **获取服务器**&#xff1a;确保你有两台运行 RHEL 8 的…...

振动和震动的区别?

问题描述&#xff1a;振动和震动的区别&#xff1f; 问题解决&#xff1a; 震动&#xff08;Oscillation&#xff09;&#xff1a; 特点&#xff1a; 随机的、突发的、不经常的、无规律的运动。例子&#xff1a; 地壳震动、消息震动全国&#xff0c;强调的是运动的力度或幅度&…...

3DMM模型

目录 BFMBFM_200901_MorphableModel.matexp_pca.bintopology_info.npyexp_info.npy BFM BFM_2009 01_MorphableModel.mat from scipy.io import loadmat original_BFM loadmat("01_MorphableModel.mat") # dict_keys: [__header__, __version__, __globals__, # …...

Python 3 使用 write()、writelines() 函数写入文件

1 使用 write() 函数&#xff0c;将字符串&#xff08;或字节串&#xff0c;仅适用写入二进制文件中&#xff09;写入文件中。 with open(example.txt,w,encodingutf-8) as f:f.write(春夜喜雨\n)f.write(杜甫 [唐代]\n)f.write(好雨知时节&#xff0c;当春乃发生。\n)f.write(…...

鸿蒙(HarmonyOS)应用开发——管理组件状态

状态管理 在应用中&#xff0c;界面通常都是动态的。 #mermaid-svg-DrPNsglFkyLqn7Lw {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-DrPNsglFkyLqn7Lw .error-icon{fill:#552222;}#mermaid-svg-DrPNsglFkyLqn7Lw …...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...