当前位置: 首页 > 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 …...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...