【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 连续字母长度(100分) - 三语言AC题解(Python/Java/Cpp)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1065
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁~
🍓OJ题目截图
文章目录
- 📎在线评测链接
- 🍓OJ题目截图
- 🏠 连续字母长度
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例解释
- 数据范围
- 题解
- 参考代码
🏠 连续字母长度
问题描述
K小姐有一个只包含大写字母的字符串,她想知道在所有包含同一字母的子串中,长度第 k k k 大的子串的长度是多少。注意,对于相同字母,只考虑最长的那个子串。
输入格式
第一行输入一个字符串 s s s,字符串长度满足 1 < ∣ s ∣ ≤ 1 0 5 1 < |s| \le 10^5 1<∣s∣≤105,且只包含大写字母。
第二行输入一个整数 k k k,表示要求的子串长度的排名。
输出格式
输出一个整数,表示第 k k k 长的子串的长度。如果不存在第 k k k 长的子串,则输出 − 1 -1 −1。
样例输入
AAAAHHHBBCDHHHH
3
样例输出
2
样例解释
在给定的样例中,同一字母连续出现次数最多的是 A A A 和 H H H,均为 4 4 4 次。第二多的是 H H H,有 3 3 3 次连续出现,但由于 H H H 已经有了更长的子串,因此不予考虑。下一个最长的子串是 B B BB BB,长度为 2 2 2。因此,最终答案为 2 2 2。
数据范围
1 < ∣ s ∣ ≤ 1 0 5 1 < |s| \le 10^5 1<∣s∣≤105
1 ≤ k ≤ 26 1 \le k \le 26 1≤k≤26
题解
本题可以通过统计每个字母出现的最长连续子串的长度,然后对这些长度进行排序来解决。具体步骤如下:
- 遍历字符串 s s s,统计每个字母出现的最长连续子串的长度,并用一个长度为 26 26 26 的数组 l e n len len 来存储,其中 l e n [ i ] len[i] len[i] 表示字母 i i i 出现的最长连续子串的长度。
- 对数组 l e n len len 进行降序排序。
- 判断排序后的数组 l e n len len 中第 k − 1 k-1 k−1 个元素(下标从 0 0 0 开始)是否为 0 0 0,如果为 0 0 0,说明不存在第 k k k 长的子串,输出 − 1 -1 −1;否则,输出 l e n [ k − 1 ] len[k-1] len[k−1] 即可。
时间复杂度: O ( n log n ) O(n \log n) O(nlogn),其中 n n n 为字符串 s s s 的长度。
空间复杂度: O ( 1 ) O(1) O(1)。
参考代码
- Python
def solve(s, k):n = len(s)len_arr = [0] * 26i = 0while i < n:j = iwhile j < n and s[j] == s[i]:j += 1c = ord(s[i]) - ord('A')len_arr[c] = max(len_arr[c], j - i)i = jlen_arr.sort(reverse=True)return len_arr[k - 1] if len_arr[k - 1] > 0 else -1s = input().strip()
k = int(input())
print(solve(s, k))
- Java
import java.util.Arrays;
import java.util.Scanner;public class Main {public static int solve(String s, int k) {int n = s.length();int[] lenArr = new int[26];int i = 0;while (i < n) {int j = i;while (j < n && s.charAt(j) == s.charAt(i)) {j++;}int c = s.charAt(i) - 'A';lenArr[c] = Math.max(lenArr[c], j - i);i = j;}Arrays.sort(lenArr);return lenArr[25 - k + 1] > 0 ? lenArr[25 - k + 1] : -1;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s = scanner.nextLine();int k = scanner.nextInt();System.out.println(solve(s, k));}
}
- Cpp
#include <iostream>
#include <string>
#include <algorithm>using namespace std;int solve(string s, int k) {int n = s.length();int lenArr[26] = {0};int i = 0;while (i < n) {int j = i;while (j < n && s[j] == s[i]) {j++;}int c = s[i] - 'A';lenArr[c] = max(lenArr[c], j - i);i = j;}sort(lenArr, lenArr + 26, greater<int>());return lenArr[k - 1] > 0 ? lenArr[k - 1] : -1;
}int main() {string s;int k;cin >> s >> k;cout << solve(s, k) << endl;return 0;
}
相关文章:

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 连续字母长度(100分) - 三语言AC题解(Python/Java/Cpp)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 …...

18 Shell编程规范与变量
目录 18.1 Shell脚本概述 18.1.1 Shell的作用 18.1.2 编写第一个Shell脚本 18.1.3 重定向与管道操作 18.2 Shell变量的作用、类型 18.2.1 自定义变量 18.2.2 特殊的Shell变量 18.1 Shell脚本概述 可以批量处理、自动化地完成一系列维护任务,大大减轻管理员的负担。…...

Linux基础命令大全(详解版)
Linux基础命令(详解版) 文章目录 Linux基础命令(详解版)1.Linux的目录结构**2.Linux路径的描述方式**3.Linux命令基础格式4.ls命令 隐藏文件、文件夹5.pwd命令6.cd命令 特殊路径符7.mkdir命令 文件操作命令8.touch命令9.cat命令10…...
python列表常见去重方法
列表去重在python实际运用中,十分常见,也是最基础的重点知识。 1. 使用for循环实现列表去重 此方法去重后,原顺序保持不变。 # for循环实现列表去重 list1 [a, 4, 6, 4, b, hello, hello, world, 9, 9, 4, a] list2 [] for l1 in list1:…...

usb摄像头应用编程
作者简介: 一个平凡而乐于分享的小比特,中南民族大学通信工程专业研究生在读,研究方向无线联邦学习 擅长领域:驱动开发,嵌入式软件开发,BSP开发 作者主页:一个平凡而乐于分享的小比特的个人主页…...

康谋分享 | 自动驾驶联合仿真——功能模型接口FMI(一)
功能模型接口FMI(Functional Mock-up Interface)是一个开放且与工具解耦的标准。FMI包含了一个C-API(接口),一个用于描述接口的XML文件以及可交换的功能模型单元FMU(Functional Mock-up Unit)&a…...
OPenCV中绘制多条多边形曲线函数polylines的使用
操作系统:ubuntu22.04OpenCV版本:OpenCV4.9IDE:Visual Studio Code编程语言:C11 功能描述 绘制多条多边形曲线 原型1 void cv::polylines ( InputOutputArray img, InputArrayOfArrays pts, bool isClosed, const Scalar & color…...

气膜球幕影院:娱乐体验的新高度—轻空间
气膜球幕影院以其独特的全景沉浸体验和丰富的娱乐内容,成为了现代娱乐产业的重要组成部分。轻空间带您来探索一下气膜球幕影院带来的独特娱乐体验。 全景沉浸式体验 气膜球幕影院的360度全景沉浸式体验,彻底改变了传统观影方式。观众被包围在一个球形屏幕…...

阿里CEO个人投资的智驾公司,走了不一样的路
佑驾创新在去年8月和11月完成两轮融资,在今年5月底递表港交所,目前拿到了29家车企88款车型的量产订单。自动驾驶赛道不缺明星,这些因素本不足以凸显它的差异化。但是在招股书中,一条特殊的发展路线,却让佑驾创新显得不…...

Arduino平台软硬件原理及使用——无源蜂鸣器模块的使用
文章目录 一、蜂鸣器发声原理 二、无源蜂鸣器与有源蜂鸣器的区分 三、无源蜂鸣器模块在Arduino中的使用 一、蜂鸣器发声原理 上图为常见的不同封装及规格的蜂鸣器。 同蜜蜂、知了等昆虫发声原理一样,蜂鸣器同样靠振动来发出声音; 如上图为无源蜂鸣器的内…...

【Go】用 DBeaver、db browser 和 SqlCipher 读取 SqlCipher 数据库
本文档主要描述如何用 DBeaver、db browser 和 SqlCipher 上打开加密的 SQLite3 数据库(用 SqlCipher v3 加密) 软件版本 DBeaver:v24.1.0 SQLite-driver: sqlite-jdbc-3.46.0.0.jar dbbrowser-for-sqlite-cipher:3.12.2 SqlCipher cli(ubuntun)&am…...

ROS操作过程中的报错
文章目录 错误:E: Unable to locate package ros-noetic-desktop-full报错问题报错原因解决方法 错误2:ERROR: cannot download default source list from:报错问题错误原因解决办法 错误:E: Unable to locate package ros-noetic-desktop-fu…...

Qt项目学习-20240617
Qt项目学习 1.0 文件构建 1.1 预处理命令 C预处理命令是编译过程中的第一步,发生在编译器进行实际编译之前。预处理器(preprocessor)执行这些命令,它们不是C语言的一部分,但对源代码的编译过程至关重要。以下是一些常…...

加密好的WPSword文档,忘记密码怎么办?
在日常办公和学习中,我们经常使用WPS Word等文档处理软件来创建和编辑重要文件。为了保护这些文件不被未经授权的人访问,我们通常会选择给文档设置密码。然而,有时我们可能会因为时间久远或其他原因而忘记自己设置的密码,这时该如…...

C# WPF 读写CAN数据
C# WPF 读写CAN数据 CAN 分析仪 分析仪资料下载 官方地址:https://www.zhcxgd.com/1.html CSDN: 项目配置 复制Dll库文件 文件在上面的资料里面 设置不安全代码 CAN C#工具类 CAN_Tool.cs using Microsoft.VisualBasic; using System; using Sys…...
力扣2517.礼盒的最大甜蜜度
力扣2517.礼盒的最大甜蜜度 二分答案求最小值 排完序判断是否有k个差距至少为mid的元素别用i遍历 可能会越界 用 : 有多少取多少 class Solution {public:int maximumTastiness(vector<int>& price, int k) {ranges::sort(price);auto check [&](int mid) -&…...

多模块存储器
随着计算机技术的发展,处理的信息量越来越多,对存储器的速度和容量要求也越来越高;而且随着CPU性能的不断提高、IO设备数量不断增加,导致主存的存取速度已经称为了整个计算机系统的性能瓶颈。这就要求我们必须提高主存的访问速度。…...

Windows反截屏开发实现
文章目录 Windows反截屏开发实现1. SetWindowDisplayAffinity2. 反截屏系统3. 总结 Windows反截屏开发实现 最近在我们云桌面中需要做到反截屏能力,所谓反截屏就是我们无法通过截图软件(微信,QQ,截图等程序)截取桌面的…...
Android.mk的用法
前言 Android.mk 文件是 Android 编译系统中用于描述项目源文件、库和模块的 Makefile。它采用 GNU Make 的语法,但也包含了一些特定于 Android 编译系统的规则和变量。以下是对其语法和使用方法的详细解释及示例。 一:模块种类 一个Android.mk file用来向编译系统描述你的源…...

android studio CreateProcess error=2, 系统找不到指定的文件
【问题记录篇】 在AndroidStudio编译开发jni相关工程代码的时候,编译遇到的这个报错: CreateProcess error2, 系统找不到指定的文件。排查处理步骤: 先查看Build Output的具体日志输出 2.了解到问题出在了NDK配置上,此时需要根据自己的gra…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...