当前位置: 首页 > 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));}
}
http://www.lryc.cn/news/525330.html

相关文章:

  • HTTP 配置与应用(局域网)
  • ultralytics 是什么?
  • AI竞争:从技术壁垒到用户数据之争
  • MySQL 主从复制(单组传统复制,GTID复制。双主复制)
  • python学opencv|读取图像(四十)掩模:三通道图像的局部覆盖
  • vue3 中如何监听 props 中的值的变化
  • Scrapy之一个item包含多级页面的处理方案
  • hive 自动检测、自动重启、记录检测日志、自动清理日志
  • HFSS同轴替换波端口
  • 【2024年华为OD机试】 (C卷,100分)- 素数之积(JavaScriptJava PythonC/C++)
  • 【C++模板】:如何判断自定义类型是否实现某个函数
  • 基于微信小程序的汽车保养系统设计与实现(LW+源码+讲解)
  • 电子应用设计方案102:智能家庭AI鱼缸系统设计
  • 【Elasticsearch】RestClient操作文档
  • 内存条的构造、原理及性能参数
  • 鸿蒙模块概念和应用启动相关类(HAP、HAR、HSP、AbilityStage、UIAbility、WindowStage、window)
  • SQLark 百灵连接工具便捷功能之生成数据库测试数据
  • ChirpIoT技术的优势以及局限性
  • Jetpack架构组件学习——使用Glance实现桌面小组件
  • C++函数——fill
  • 二叉树(了解)c++
  • 备赛蓝桥杯之第十五届职业院校组省赛第三题:产品360度展示
  • 业余无线电 对讲机常用频率使用
  • 个性化的语言模型构建思路
  • QT开发技术【QFileDialog卡顿问题】
  • 关于为什么java中nextInt()和nextLine()不能混用 | nextInt()和nextInt()之类的可以一起用
  • Android OpenGL(六) 纹理
  • git和idea重新安装后提交异常
  • leetcode刷题记录(八十一)——236. 二叉树的最近公共祖先
  • STM32-CAN总线