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

每日OJ_牛客_小红的子串_滑动窗口+前缀和_C++_Java

目录

牛客_小红的子串_滑动窗口+前缀和

题目解析

C++代码

Java代码


牛客_小红的子串_滑动窗口+前缀和

小红的子串

描述:
        小红拿到了一个长度为nnn的字符串,她准备选取一段子串,满足该子串中字母的种类数量在[l,r]之间。小红想知道,一共有多少种选取方案?

输入描述:

第一行输入三个正整数 n,l,rn,
第二行输入一个仅包含小写字母的字符串。
1 ≤ n ≤ 200000
1 ≤ l ≤ r ≤ 26

输出描述:

合法的方案数。


题目解析

        利用前缀和的思想,求种类个数在 [l, r] 区间内子串的个数,等于求 [1, r] 区间内个数 - [1, l - 1] 区间内个数。求种类个数在 [1, count] 区间内子串的个数,可以用滑动窗口来求解。

C++代码

#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;
}

Java代码

import java.util.*;
public class Main
{public static int n, l, r;public static char[] s;// 找出字符种类在 [1, x] 之间的⼦串的个数public static long find(int x){// 滑动窗⼝int left = 0, right = 0;int[] hash = new int[26];int kinds = 0; // 统计窗⼝内字符的种类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;}public static void main(String[] args){Scanner in = new Scanner(System.in);n = in.nextInt(); l = in.nextInt(); r = in.nextInt();s = in.next().toCharArray();System.out.println(find(r) - find(l - 1));}
}

相关文章:

每日OJ_牛客_小红的子串_滑动窗口+前缀和_C++_Java

目录 牛客_小红的子串_滑动窗口前缀和 题目解析 C代码 Java代码 牛客_小红的子串_滑动窗口前缀和 小红的子串 描述&#xff1a; 小红拿到了一个长度为nnn的字符串&#xff0c;她准备选取一段子串&#xff0c;满足该子串中字母的种类数量在[l,r]之间。小红想知道&…...

HTTP 配置与应用(局域网)

想做一个自己学习的有关的csdn账号&#xff0c;努力奋斗......会更新我计算机网络实验课程的所有内容&#xff0c;还有其他的学习知识^_^&#xff0c;为自己巩固一下所学知识&#xff0c;下次更新HTTP 配置与应用&#xff08;不同网段&#xff09;。 我是一个萌新小白&#xf…...

ultralytics 是什么?

ultralytics 是一个用于计算机视觉任务的 Python 库&#xff0c;专注于提供高效、易用的目标检测、实例分割和图像分类工具。它最著名的功能是实现 YOLO&#xff08;You Only Look Once&#xff09; 系列模型&#xff0c;特别是最新的 YOLOv8。 1. YOLO 是什么&#xff1f; YO…...

AI竞争:从技术壁垒到用户数据之争

标题&#xff1a;AI竞争&#xff1a;从技术壁垒到用户数据之争 文章信息摘要&#xff1a; AI市场呈现开放模型与封闭模型并存的双轨发展态势&#xff0c;但核心竞争力已从模型技术转向用户数据积累和使用习惯培养。商业模式正在多元化发展&#xff0c;从早期的价格战转向subsc…...

MySQL 主从复制(单组传统复制,GTID复制。双主复制)

案例环境 单组复制 master&#xff1a; 192.168.180.143 slave01&#xff1a;192.168.180.144 双组复制 master01&#xff1a;192.168.180.143 master02&#xff1a;192.168.180.144 案例过程 准备工作 关闭所有防火墙 setenforce 0 && systemctl stop firewa…...

python学opencv|读取图像(四十)掩模:三通道图像的局部覆盖

【1】引言 前序学习了使用numpy创建单通道的灰色图像&#xff0c;并对灰色图像的局部进行了颜色更改&#xff0c;相关链接为&#xff1a; python学opencv|读取图像&#xff08;九&#xff09;用numpy创建黑白相间灰度图_numpy生成全黑图片-CSDN博客 之后又学习了使用numpy创…...

vue3 中如何监听 props 中的值的变化

在 Vue 3 中&#xff0c;你可以使用 watch 函数来监听组件的 props 值的变化。watch 函数允许你观察一个或多个响应式数据源&#xff0c;并在这些数据源发生变化时执行回调函数。 以下是一个示例&#xff0c;展示了如何在 Vue 3 中使用 watch 来监听 props 中的值的变化&#…...

Scrapy之一个item包含多级页面的处理方案

目标 在实际开发过程中&#xff0c;我们所需要的数据往往需要通过多个页面的数据汇总得到&#xff0c;通过列表获取到的数据只有简单的介绍。站在Scrapy框架的角度来看&#xff0c;实际上就是考虑如何处理一个item包含多级页面数据的问题。本文将以获取叶子猪网站的手游排行榜及…...

hive 自动检测、自动重启、记录检测日志、自动清理日志

最终效果 定时检测hive运行状态&#xff0c;进程不存在或者进程存在但是不监听端口的hiveserver2&#xff0c;自动重新拉起每次检测脚本执行的日志都会保存在log目录下.check文件&#xff0c;每一个月一个文件每月15日&#xff0c;删除2月前的检测日志开启hive自带日志输出后&…...

HFSS同轴替换波端口

波端口仿真正常 将波端口换成内径内径0.3mm外径0.6mm同轴之后 结果很不对 换成下面的尺寸就好了...

【2024年华为OD机试】 (C卷,100分)- 素数之积(JavaScriptJava PythonC/C++)

一、问题描述 RSA 因数分解问题 题目描述 RSA 加密算法在网络安全世界中无处不在&#xff0c;它利用了极大整数因数分解的困难度。数据越大&#xff0c;安全系数越高。给定一个 32 位正整数&#xff0c;请对其进行因数分解&#xff0c;找出是哪两个素数的乘积。 输入描述 …...

【C++模板】:如何判断自定义类型是否实现某个函数

一、引子 偶尔我们会面对这样的尴尬的场景&#xff0c;我们需要显示的去判断在某个自定义类型中&#xff0c;是否已经提供了我们期待的API接口&#xff0c;以避免产生“莫须有”的错误。阁下该如何破解此问题&#xff01; 这里&#xff0c;直接给出一种通用的方法&#xff0c;…...

基于微信小程序的汽车保养系统设计与实现(LW+源码+讲解)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

电子应用设计方案102:智能家庭AI鱼缸系统设计

智能家庭 AI 鱼缸系统设计 一、引言 智能家庭 AI 鱼缸系统旨在为鱼类提供一个健康、舒适的生活环境&#xff0c;同时为用户提供便捷的管理和观赏体验。 二、系统概述 1. 系统目标 - 自动维持水质稳定&#xff0c;包括水温、酸碱度、硬度和溶氧量等关键指标。 - 智能投食&…...

【Elasticsearch】RestClient操作文档

RestClient操作文档 新增文档实体类API语法 查询文档删除文档修改文档批量导入文档小结 新增文档 将数据库中的信息导入elasticsearch中 以商品数据为例 实体类 定义一个索引库结构对应的实体。 Data ApiModel(description "索引库实体") public class ItemDoc{…...

内存条的构造、原理及性能参数

内存条的构造、原理及性能参数 一、内存条的构造1.1 外观结构1.1.1 芯片&#xff1a;大脑1.1.2 PCB板&#xff1a;骨架1.1.3 金手指&#xff1a;接口1.1.4 电容电阻&#xff1a;稳压、稳流1.1.5 防呆缺口&#xff1a;防错 1.2 内部层次结构 二、内存条的工作原理2.1 数据的“搬…...

鸿蒙模块概念和应用启动相关类(HAP、HAR、HSP、AbilityStage、UIAbility、WindowStage、window)

目录 鸿蒙模块概念 HAP entry feature har shared 使用场景 HAP、HAR、HSP介绍 HAP、HAR、HSP开发 应用的启动 AbilityStage UIAbility WindowStage Window 拉起应用到显示到前台流程 鸿蒙模块概念 HAP hap包是手机安装的最小单元&#xff0c;1个app包含一个或…...

SQLark 百灵连接工具便捷功能之生成数据库测试数据

参考此文&#xff1a; SQLark百灵连接工具--数据生成...

ChirpIoT技术的优势以及局限性

ChirpIoT是一种由上海磐启微电子开发的国产无线射频通讯技术&#xff0c;ChirpIoT技术基于磐启多年对雷达等线性扩频信号的深入研究&#xff0c;并在此基础上对线性扩频信号的变化进行了改进&#xff0c;实现了远距离传输的一种无线通信技术。相关产品型号有E29-400T22D、E290-…...

Jetpack架构组件学习——使用Glance实现桌面小组件

基本使用 1.添加依赖 添加Glance依赖: // For AppWidgets supportimplementation "androidx.glance:glance-appwidget:1.1.0"// For interop APIs with Material 3implementation "androidx.glance:glance-material3:1.1.0"// For interop APIs with Mater…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...