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

最长的指定瑕疵度的元音子串

一、题目

最长的指定瑕疵度的元音子串
定义:开头和结尾都是元音字母(aeiouAEIOU)的字符串为 元音字符串 ,其中混杂的非元音字母数量为其 瑕疵度 。比如:
“a” 、 "aa"是元音字符串,其瑕疵度都为0
"aiur"不是元音字符串(结尾不是元音字符)
"abira"是元音字符串,其瑕疵度为2
给定一个字符串str和瑕疵度flaw,请找出瑕疵度等于 flaw 的最长元音字符子串,并输出其长度,如果找不到满足条件的元音字符子串,输出0。
子串:字符串中任意个连续的字符组成的子序列称为该字符串的子串。

输入
首行输入一个整数 flaw,取值范围 [0, 65535]。
接下来一行是字符串str,仅由字符a-z和A-Z组成,字符串长度 (0, 65535]。
输出
输出为一个整数,代表满足条件的元音字符子串的长度。

样例1
复制输入:
0
“asdbuiodevauufgh”
复制输出:
3
解释:
满足条件的最长元音字符子串有两个,分别为uio和auu,长度为3。

样例2
复制输入:
2
“aeueo”
复制输出:
0
解释:
没有满足条件的元音字符子串,输出0

样例3
复制输入:
1
“aabeebuu”
复制输出:
5
解释:
满足条件的最长元音字符子串有两个,分别为aabee和eebuu,长度为5

二、解题

代码一

static int GetFlawLength(const char* str, int slow, int fast)
{int len = 0;for (int i = slow; i <= fast; i++) {char c = tolower(str[i]);if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {continue;} else {len++;}}return len;
}static int GetLongestFlawedVowelSubstrLen(int flaw, const char* str)
{int max = 0;int len = strlen(str);int slow = 0;int fast = slow;while (fast < len) {int flawLen = GetFlawLength(str, slow, fast);if (flawLen == flaw) {max = max > fast - slow ? max : fast - slow + 1;fast++;} else if (flawLen < flaw) {fast++;} else if (flawLen > flaw) {if (slow == fast) {fast++;}slow++;}}return max;
}

上述代码可以通过题目3个用例,下面的用例执行失败

1
"ab"
// 预期输出
0
// 实际输出
2

经过调试发现是因为判断是否是元音子串还有个条件是结尾的字符的是元音字符,增加对这个条件的判断。修改代码如下

static bool IsTargetCharacter(char c)
{if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {return true;}return false;
}static int GetFlawLength(const char* str, int slow, int fast)
{int len = 0;for (int i = slow; i <= fast; i++) {char c = tolower(str[i]);if (IsTargetCharacter(c)) {continue;} else {len++;}}return len;
}static int GetLongestFlawedVowelSubstrLen(int flaw, const char* str)
{int max = 0;int len = strlen(str);int slow = 0;int fast = slow;while (fast < len) {int flawLen = GetFlawLength(str, slow, fast);if (flawLen == flaw) {if(fast < len && IsTargetCharacter(str[fast])) {max = max > fast - slow ? max : fast - slow + 1;}fast++;} else if (flawLen < flaw) {fast++;} else if (flawLen > flaw) {if (slow == fast) {fast++;}slow++;}}return max;
}

可以通过上述实例,但是下述用例无法通过

0
"NA"
// 预期输出
1
// 实际输出
0

经过调试发现代码有点小问题

将IsTargetCharacter函数修改如下:

static bool IsTargetCharacter(char tempC)
{char c = tolower(tempC);if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {return true;}return false;
}

可以通过上述用例,但是下面的测试用例失败

3
"asdbuiodevauufghA"
// 预期输出
7
// 实际输出10

经过调试发现是元音子串还需要满足第一个字符是元音字符,在GetLongestFlawedVowelSubstrLen函数增加此条件,修改GetLongestFlawedVowelSubstrLen函数代码如下

static int GetLongestFlawedVowelSubstrLen(int flaw, const char* str)
{int max = 0;int len = strlen(str);int slow = 0;int fast = slow;while (fast < len) {int flawLen = GetFlawLength(str, slow, fast);if (flawLen == flaw) {if (fast < len && IsTargetCharacter(str[fast]) && IsTargetCharacter(str[slow])) {max = max > fast - slow ? max : fast - slow + 1;}fast++;} else if (flawLen < flaw) {fast++;} else if (flawLen > flaw) {if (slow == fast) {fast++;}slow++;}}return max;
}

上述代码通过通过上述用例,但是执行一个特别长的字符串报错"CPU资源占用过高"

检查代码,需要确定是哪里的代码占用资源过高。经过判断是因为GetLongestFlawedVowelSubstrLen函数中的这条语句

int flawLen = GetFlawLength(str, slow, fast);

这段代码等于是fast指针每加一次,都要对slow和fast之间的字符串进行遍历计数。这样时间复杂度就能达到O(n2),对这行代码进行修改,看了之前的代码,是对瑕疵字符进行同步计数的,所以优化方向就是取消对字符串的重复多次计数。

修改代码后,程序果然可以执行通过,看到耗时的代码就是GetFlawLength函数。

Aced代码

static bool IsTargetCharacter(char tempC)
{char c = tolower(tempC);if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {return true;}return false;
}static int GetLongestFlawedVowelSubstrLen(int flaw, const char* str)
{int max = 0;int len = strlen(str);int slow = 0;int fast = slow;int flawLength = 0;while (fast < len) {//int flawLen = GetFlawLength(str, slow, fast);if (flawLength == flaw) {if (fast < len && IsTargetCharacter(str[fast]) && IsTargetCharacter(str[slow])) {max = max > fast - slow ? max : fast - slow + 1;}if (!IsTargetCharacter(str[fast])) {flawLength++;}fast++;} else if (flawLength < flaw) {if (!IsTargetCharacter(str[fast])) {flawLength++;}fast++;} else if (flawLength > flaw) {if (slow == fast) {if (!IsTargetCharacter(str[fast])) {flawLength++;}fast++;}if (!IsTargetCharacter(str[slow])) {flawLength--;}slow++;}}return max;
}

之前的Aced代码

#include <stdio.h>
#include "securec.h"
#include "stdbool.h"#define MAX_LEN 65536_Bool isTargetCharacter(char* c)
{int copy = tolower(c);if(copy == 'a' || copy == 'e' || copy == 'i' || copy == 'o' || copy == 'u'){return true;}return false;
}int getFlaw(char* str, int l, int r)
{int flawCount = 0;for(int i = l; i < r; i++){if(!isTargetCharacter(str[i])){flawCount++;}}//printf("flawCount:%d\n", flawCount);return flawCount;
}int getCount(int flaw, char* str)
{int maxCount = 0;int length = 0;int len = strlen(str);int l = 0, r = 0;while(r < len){if(!isTargetCharacter(str[r])){length++;}while(length > flaw){if(!isTargetCharacter(str[l])){length--;}l++;}if(flaw == length){if(isTargetCharacter(str[l]) && isTargetCharacter(str[r])){int count = r - l + 1;maxCount = maxCount > count ? maxCount : count;}}r++;}return maxCount;
}//1
//asdbuiodevauufghA
//例子不符
int getCount4(int flaw, char* str)
{int maxCount = 0;int length = 0;int len = strlen(str);int l = 0, r = 0;while(r < len){int realFlaw = getFlaw(str, l, r);while(l <= r){if(flaw == getFlaw(str, l, r) && isTargetCharacter(str[l])){break;}l++;}if(flaw == realFlaw){if(isTargetCharacter(str[l]) && isTargetCharacter(str[r])){int count = r - l + 1;maxCount = maxCount > count ? maxCount : count;}}r++;}return maxCount;
}//
//0
//a
//例子不符
int getCount3(int flaw, char* str)
{int maxCount = 0;int length = 0;int len = strlen(str);int l = 0, r = 1;while(r < len){int realFlaw = getFlaw(str, l, r);while(l < r){if(flaw == realFlaw){break;}l++;}if(flaw == realFlaw){if(isTargetCharacter(str[l]) && isTargetCharacter(str[r])){int count = r - l + 1;maxCount = maxCount > count ? maxCount : count;}}r++;}return maxCount;
}int getCount2(int flaw, char* str)
{int maxCount = 0;int length = 0;int len = strlen(str);int l = 0, r = 1;while(l < r && r < len){if(isTargetCharacter(str[r])){printf("r:%d", r);while(l < r){if(isTargetCharacter(str[l])){printf("l:%d", l);if(flaw == getFlaw(str, l, r)){int count = r - l + 1;maxCount = maxCount > count ? maxCount : count;}else if(flaw < getFlaw(str, l, r)){l++;}else if(flaw > getFlaw(str, l, r)){r++;}}else{l++;}}}else{r++;}}return maxCount;
}int GetLongestFlawedVowelSubstrLen(int flaw, char* str)      
{                     // 添加你的代码int count = 0;count = getCount(flaw, str);return count;
}                     int main(void) 
{ int flaw = 0;  if (scanf_s("%d\n", &flaw) != 1) { return -1; }   char str[MAX_LEN];   if (NULL == gets_s(str, sizeof(str))) { return -1; }   int result = GetLongestFlawedVowelSubstrLen(flaw, str);(void)printf("%d", result); return 0;           

这版代码应该是我参考别人答案写的吧。

相关文章:

最长的指定瑕疵度的元音子串

一、题目 最长的指定瑕疵度的元音子串 定义&#xff1a;开头和结尾都是元音字母&#xff08;aeiouAEIOU&#xff09;的字符串为 元音字符串 &#xff0c;其中混杂的非元音字母数量为其 瑕疵度 。比如: “a” 、 "aa"是元音字符串&#xff0c;其瑕疵度都为0 "aiu…...

每日算法Day15【组合、组合总和III、电话号码的字母组合】

77. 组合 算法链接: 77. 组合 - 力扣&#xff08;LeetCode&#xff09; 类型: 回溯 难度: 中等 回溯三步法&#xff1a; 1、确定参数返回值 2、确定终止条件 3、单层搜索逻辑 剪枝操作&#xff1a; 当path容量超过k时的数据可以不用遍历&#xff0c;故遍历边界条件判断: …...

C语言教程——指针进阶(2)

目录 一、函数指针数组 1.1函数指针数组写法 1.2函数指针用途 二、指向函数指针数组的指针 2.1概念 三、回调函数 3.1用法 3.2qsort排序 总结 前言 我们接着上一篇的函数指针往下学习。 一、函数指针数组 1.1函数指针数组写法 我们都知道指针数组&#xff0c;里面可以…...

调和级数不为整数的证明

文章目录 1. 问题引入2. 证明2.1 引理12.2 引理22.3 引理3&#xff1a;2.4 核心证明&#xff1a; 3. 参考 1. 问题引入 s ( n ) 1 1 2 1 3 ⋯ 1 n , n ∈ N ∗ , n ≥ 2 s(n) 1\frac{1}{2}\frac{1}{3}\cdots\frac{1}{n}, \quad \\n \in N^*, n \ge2 s(n)121​31​⋯n1​,…...

基于微信小程序的在线学习系统springboot+论文源码调试讲解

第4章 系统设计 一个成功设计的系统在内容上必定是丰富的&#xff0c;在系统外观或系统功能上必定是对用户友好的。所以为了提升系统的价值&#xff0c;吸引更多的访问者访问系统&#xff0c;以及让来访用户可以花费更多时间停留在系统上&#xff0c;则表明该系统设计得比较专…...

基于 Boost.Asio 和 Boost.Beast 的异步 HTTP 服务器(学习记录)

已完成功能&#xff1a; 支持 GET 和 POST 请求的路由与回调处理。 解析URL请求。 单例模式 管理核心业务逻辑。 异步 I/O 技术和 定时器 控制超时。 通过回调函数注册机制&#xff0c;可以灵活地为不同的 URL 路由注册处理函数。 1. 项目背景 1.1 项目简介 本项目是一个基于…...

有机物谱图信息的速查技巧有哪些?

谱图信息是化学家解读分子世界的“语言”&#xff0c;它们在化学研究的各个领域都发挥着不可或缺的作用。它们是理解和确定分子结构的关键&#xff0c;对化学家来说极为重要&#xff0c;每一种谱学技术都提供了不同的视角来观察分子&#xff0c;从而揭示其独特的化学和物理特性…...

Eureka缓存机制

一、Eureka的CAP特性 Eureka是一个AP系统&#xff0c;它优先保证可用性&#xff08;A&#xff09;和分区容错性&#xff08;P&#xff09;&#xff0c;而不保证强一致性&#xff08;C&#xff09;。这种设计使得Eureka在分布式系统中能够应对各种故障和分区情况&#xff0c;保…...

【LC】78. 子集

题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集&#xff08;幂集&#xff09;。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1…...

协同过滤算法私人诊所系统|Java|SpringBoot|VUE|

【技术栈】 1⃣️&#xff1a;架构: B/S、MVC 2⃣️&#xff1a;系统环境&#xff1a;Windowsh/Mac 3⃣️&#xff1a;开发环境&#xff1a;IDEA、JDK1.8、Maven、Mysql5.7 4⃣️&#xff1a;技术栈&#xff1a;Java、Mysql、SpringBoot、Mybatis-Plus、VUE、jquery,html 5⃣️…...

Docker部署Naocs-- 超细教程

Docker 拉取镜像 docker pull nacos/nacos-server:v2.2.0 挂载目录 如果不是root账号 前面加sudo 或者 切换root账号 su root&#xff08;命令&#xff09; mkdir -p /mydata/nacos/logs/ #新建logs目录 mkdir -p /mydata/nacos/conf/ #新建conf目录 启动容器…...

[java基础-集合篇]优先队列PriorityQueue结构与源码解析

优先队列PriorityQueue 优先级队列表示为平衡二进制堆&#xff1a; queue[n] 的两个子级是 queue[2*n1] 和 queue[2*&#xff08;n1&#xff09;]。 注&#xff1a;左子节点index2*parentIndex1,右子节点index2*parentIndex2,源码中计算parent位置时就是这样反过来计算的 优…...

12. C语言 数组与指针(深入理解)

本章目录: 前言1. 什么是数组&#xff1f;2. 数组的声明与初始化声明数组初始化数组 3. 访问数组元素遍历数组 4. 获取数组长度使用 sizeof 获取长度使用宏定义简化 5. 数组与指针数组名与指针的区别使用指针操作数组 6. 多维数组遍历多维数组 7. 数组作为函数参数8. 高级技巧与…...

Postman接口测试基本操作

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 Postman-获取验证码 需求&#xff1a;使用Postman访问验证码接口&#xff0c;并查看响应结果。 地址&#xff1a;http://kdtx-test.itheima.net/api/captchaIm…...

MySQL--2.1MySQL的六种日志文件

大家好&#xff0c;我们来说一下MySQL的6中日志文件。 1.查询日志 查询日志主要记录mysql的select查询的&#xff0c;改配置是默认关闭的。不推荐开启&#xff0c;因为会导致大量查询日志文件储存占用你的空间。 举例查询一下 select * from class&#xff1b; 开启查询日志的命…...

spring task使用

Spring Task 简介 Spring Task 是 Spring 框架原生自带的任务调度框架&#xff0c;它犹如一把瑞士军刀&#xff0c;为开发者提供了丰富多样的功能&#xff0c;助力轻松创建和管理定时任务。相较于其他一些第三方任务调度框架&#xff0c;Spring Task 最大的优势在于其与 Sprin…...

【FPGA】时序约束与分析

设计约束 设计约束所处环节&#xff1a; 约束输入 分析实现结果 设计优化 设计约束分类&#xff1a; 物理约束&#xff1a;I/O接口约束&#xff08;例如引脚分配、电平标准设定等物理属性的约束&#xff09;、布局约束、布线约束以及配置约束 时序约束&#xff1a;设计FP…...

LLM的MoE由什么构成:门控网络,专家网络

LLM的MoE由什么构成:门控网络,专家网络 目录 LLM的MoE由什么构成:门控网络,专家网络专家网络门控网络MoE在联邦学习中的使用及原理专家网络 定义与特点:是一组独立的模型,每个模型都负责处理某个特定的子任务或学习输入空间的特定部分。这些专家可以是简单的线性回归模型…...

HTML-多媒体标签

除了图像&#xff0c;网页还可以放置视频和音频。 1.<video> <video>标签是一个块级元素&#xff0c;用于放置视频。如果浏览器支持加载的视频格式&#xff0c;就会显示一个播放器&#xff0c;否则显示<video>内部的子元素。 <video src"example.…...

MySQL笔记大总结20250108

Day2 1.where (1)关系运算符 select * from info where id>1; select * from info where id1; select * from info where id>1; select * from info where id!1;(2)逻辑运算符 select * from info where name"吴佩奇" and age19; select * from info wh…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...