【滑动窗口】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_aCharNums | iWindowWidth个字符,各字母的数量 |
代码
核心代码
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 满足以下条件,我们称它是 完全字符串: s 中每个字符…...
base64转PDF
今天做皖事通的对接,下载电子证照后发现回传的是base64,调试确认是个麻烦事,网上搜了一下没有base64转PDF的在线预览功能,只能自己写个调试工具了,以下是通过纯JS方式写的代码,可直接拿去使用: …...

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

第二证券:食品饮料板块拉升,乳业股亮眼,西部牧业“20cm”涨停
证券时报网讯,食物饮料板块5日盘中拉升走高,乳业股体现活跃,到发稿,骑士乳业涨超27%,西部牧业“20cm”涨停,阳光乳业亦涨停。 其它个股方面,盖世食物涨超20%,润普食物涨超18%&#…...
React 好用的工具库
1、html-react-parser HTML 到 React 解析器,适用于服务器 (Node.js) 和客户端(浏览器),适用于React节点修改过滤等需求 解析器将 HTML 字符串转换为一个或多个 React 元素。可以将一个元素替换为另一个元素…...

C++面试宝典第2题:逆序输出整数
题目 写一个方法,将一个整数逆序打印输出到控制台。注意:当输入的数字含有结尾的0时,输出不应带有前导的0。比如:123的逆序输出为321,8600的逆序输出为68,-609的逆序输出为-906。 解析 这道题本身并没有什么…...
Twincat功能块使用经验总结
控制全局变量: //轴控制指令 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、创建软链接,以替换当前的时区信息 ln -s /usr/share/zoneinfo/Universal /etc/localtime 解决方案2 手动设置硬件时钟 1、设置系…...

C++ 抽象类和接口 详解
目录 0 引言1 抽象类2 接口2.1 Java与C接口的区别 🙋♂️ 作者:海码007📜 专栏:C专栏💥 标题:C 抽象类和接口 详解❣️ 寄语:书到用时方恨少,事非经过不知难!…...

【Linux】awk 使用
awk 输出 // 打印所有列 $ awk {print $0} file // 打印第一列 $ awk {print $1} file // 打印第一和第三列 $ awk {print $1, $3} file // 打印第三列和第一列,注意先后顺序 $ cat file | awk {print $3, $1} …...

LeetCode力扣每日一题(Java):9、回文数
一、题目 二、解题思路 1、我的思路 当x<0时,x一定不是回文数,直接返回false 当x>0且x<10时,x一定是回文数,直接返回true x>10时,先将x转为字符串。将数字转成字符串方法挺多的,以下是&…...

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

更改AndroidStudio模拟器位置
C盘何等的珍贵,可是好多工具,软件非得默认安装在C盘。。导致C盘越来越紧张。。 在日常使用过程中,安装任何软件都会将其安装到非系统盘下,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 产品从模型抽象上来说都是一样的过程: 消费者(consumer)订阅某个队列。生产者(producer)创建消息,然后发布到队列(queue)中,最后将消息发送到监听的消费者。 上…...
记录111
在两台 RHEL 8 服务器上搭建 PostgreSQL 和 pgpool-II 环境涉及到安装 PostgreSQL、配置流复制(Streaming Replication)以及安装和配置 pgpool-II。以下是详细的步骤: ### 准备工作 1. **获取服务器**:确保你有两台运行 RHEL 8 的…...
振动和震动的区别?
问题描述:振动和震动的区别? 问题解决: 震动(Oscillation): 特点: 随机的、突发的、不经常的、无规律的运动。例子: 地壳震动、消息震动全国,强调的是运动的力度或幅度&…...

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() 函数,将字符串(或字节串,仅适用写入二进制文件中)写入文件中。 with open(example.txt,w,encodingutf-8) as f:f.write(春夜喜雨\n)f.write(杜甫 [唐代]\n)f.write(好雨知时节,当春乃发生。\n)f.write(…...
鸿蒙(HarmonyOS)应用开发——管理组件状态
状态管理 在应用中,界面通常都是动态的。 #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 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...