【错题集-编程题】小红的子串(前置和 + 双指针)

牛客对应题目链接:小红的子串 (nowcoder.com)


一、分析题目

利用前缀和的思想,求种类个数在 [l, r] 区间内子串的个数,等于求 [1, r] 区间内个数 - [1, l - 1] 区间内个数。

求种类个数在 [1, count] 区间内子串的个数,可以用滑动窗口来求解。


二、代码

//值得学习的代码
#include <iostream>
#include <string>using namespace std;int n, l, r;
string s;// 找出字符种类在 [1, x] 之间的⼦串的个数
long long find(int x) 
{if(x == 0) return 0;// 滑动窗⼝int left = 0, right = 0;int hash[26] = { 0 }, kinds = 0; // 统计窗⼝内字符种类的个数long long ret = 0;while(right < n){if(hash[s[right] - 'a']++ == 0) kinds++;while(kinds > x){if(hash[s[left] - 'a']-- == 1) kinds--;left++;}ret += right - left + 1;right++;}return ret;
}int main()
{cin >> n >> l >> r >> s;cout << find(r) - find(l - 1) << endl;return 0;
}

三、反思与改进

想到了滑动窗口,但是一直想不明白其中一类子串要如何计算,原来是得配合前缀和使用。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/337588.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(深度学习记录)第TR3周:Transformer 算法详解

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制 文本的输入处理中&#xff0c;transformer会将输入文本序列的每个词转化为一个词向量&#xff0c;我们通常会选择一个合适的长度作为输入…

Linux系统监控

文章目录 一、系统监控基本介绍二、内存监控2.1、内存监控字段解析2.2、windows下查看内存2.2.1、通过cmd中命令查看内存条信息&#xff1a;2.2.2、通过cmd中命令查看物理内存信息&#xff1a;2.2.3、使用任务管理器查看内存2.2.4、使用资源监视器查看内存2.2.5、使用系统信息工…

Stable Diffusion Webui--安装与使用

最近进行的课程汇报&#xff0c;学习了2023年的CVPR文章《DreamBooth: Fine Tuning Text-to-Image Diffusion Models for Subject-Driven Generation》&#xff0c;因此尝试使用了几种方法对这篇文章的工作进行了一定的复现。本文主要介绍Stable Diffusion Web UI(webui)的安装…

锅炉智能制造工厂工业物联数字孪生平台,推进制造业数字化转型

在制造业快速发展的今天&#xff0c;数字化转型已经成为企业提升竞争力的关键途径。锅炉智能制造工厂工业物联数字孪生平台&#xff0c;作为一种创新的技术解决方案&#xff0c;正以其独特的优势&#xff0c;为制造业的数字化转型提供强大动力。锅炉智能制造工厂工业物联数字孪…

Git基本配置,使用Gitee(一)

1、设置Giter的user name和email 设置提交用户的信息 git config --global user.name "username" git config --global user.email "Your e-mail"查看配置 git config --list2、生成 SSH 公钥 通过命令 ssh-keygen 生成 SSH Key -t key 类型 -C 注释 ssh-…

Stable Diffusion生成图片的参数查看与抹除方法

前几天分享了几张Stable Diffusion生成的艺术二维码&#xff0c;有同学反映不知道怎么查看图片的参数信息&#xff0c;还有的同学问怎么保护自己的图片生成参数不会泄露&#xff0c;这篇文章就来专门分享如何查看和抹除图片的参数。 查看图片的生成参数 1、打开Stable Diffus…

Vxe UI vxe-upload 上传组件,显示进度条的方法

vxe-upload 上传组件 查看官网 https://vxeui.com 显示进度条很简单&#xff0c;需要后台支持进度就可以了&#xff0c;后台实现逻辑具体可以百度&#xff0c;这里只介绍前端逻辑。 上传附件 相关参数说明&#xff0c;具体可以看文档&#xff1a; multiple 是否允许多选 li…

解锁 JavaScript ES6:函数与对象的高级扩展功能

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;JavaScript 精粹 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; ES5、ES6介绍 文章目录 &#x1f4af;ES6函数扩展&#x1f353;1 默认参数&#x1f35…

【每日刷题】Day53

【每日刷题】Day53 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 1019. 链表中的下一个更大节点 - 力扣&#xff08;LeetCode&#xff09; 2. 116. 填充每个节点的下一…

[有监督学习]2.详细图解正则化

正则化 正则化是防止过拟合的一种方法&#xff0c;与线性回归等算法配合使用。通过向损失函数增加惩罚项的方式对模型施加制约&#xff0c;有望提高模型的泛化能力。 概述 正则化是防止过拟合的方法&#xff0c;用于机器学习模型的训练阶段。过拟合是模型在验证数据上产生的误…

DL/ML/RL/TL/FL机器学习框架总结

前言 本文总结了DL/深度学习、ML/机器学习、DML/分布式机器学习、AutoML/自动化机器学习、RL/强化学习、MLaaS/机器学习及服务、SR/语音识别领域的机器学习框架&#xff0c;可作为学习、研究、研发的参考资料。 1.DL/深度学习框架 PyTorch PyTorch是一个开源的Python机器学…

面试题:计算机网络中的七四五是什么?

面试题&#xff1a;计算机网络中的七四五是什么&#xff1f; 计算机网络中说的七四五是指&#xff1a;OSI 七层模型、TCP/IP 四层模型、OSI 与 TCP/IP 的综合五层模型 OSI 七层模型 OSI 将计算机网络分为了七层&#xff0c;每一层抽象底层的内容&#xff0c;并遵守一定的规则…

逆天工具一键修复图片,视频去码。本地部署超详细!!

上一篇文章&#xff1a;逆天工具一键修复图片&#xff0c;视频去码。简直不要太好用&#xff01;-CSDN博客 根据上一篇文章展示的效果&#xff0c;本文章主要讲如何部署本地github开源项目。博主走了无数弯路&#xff0c;最后精化下来的步骤&#xff0c;超级详细&#xff01;&a…

godot4.2 + GDextension c++在 vs code 中断点调试配置

游戏开发中如果做不到自己编写的代码做断点调试&#xff0c;无不是瞎子摸象&#xff0c;特别是C这么底层的语言。这2天开始在VS studio中折腾&#xff0c;一直折腾不出结果&#xff0c;几次想要放弃GODOT。最终今天在VS code中搞定了这断点调试C代码。 在上一篇文章我已经做好了…

LabVIEW调用外部DLL(动态链接库)

LabVIEW调用外部DLL&#xff08;动态链接库&#xff09; LabVIEW调用外部DLL&#xff08;动态链接库&#xff09;可以扩展其功能&#xff0c;使用外部库实现复杂计算、硬件控制等任务。通过调用节点&#xff08;Call Library Function Node&#xff09;配置DLL路径、函数名称和…

【机器学习】集成语音与大型语音模型等安全边界探索

探索集成语音与大型语言模型&#xff08;SLMs&#xff09;的安全边界 一、引言二、SLMs的潜在安全风险三、对抗性攻击与越狱实验四、提高SLMs安全性的对策五、总结与展望 一、引言 近年来&#xff0c;随着人工智能技术的飞速发展&#xff0c;集成语音与大型语言模型&#xff08…

Java筑基—String类

这里写目录标题 一、字符串的拼接二、获取字符串长度三、字符串转换四、去除前后空白字符五、比较字符串是否相等六、比较字符串是否包含七、字符串是否以某些开始、结尾八、字符串的替换九、字符串的转换十、空串和NULL串 一、字符串的拼接 Java语言允许使用 号拼接两个字符…

WordPress Country State City Dropdown CF7插件 SQL注入漏洞复现(CVE-2024-3495)

0x01 产品简介 Country State City Dropdown CF7插件是一个功能强大、易于使用的WordPress插件,它为用户在联系表单中提供国家、州/省和城市的三级下拉菜单功能,帮助用户更准确地填写地区信息。同时,插件的团队和支持也非常出色,为用户提供高质量的服务。 0x02 漏洞概述 …

Mybatis-plus 更新或新增时设置某些字段值为空

方式一 在实体中设置某个字段为的注解中 TableField(updateStrategy FieldStrategy.IGNORED)private Date xxxxxxTime;通过这种方式会指定更新时该字段的策略&#xff0c;通常情况下updateById这种会根据字段更新&#xff0c;通常都会判断null 以及空值 指定 updateStrategy …