最长的指定瑕疵度的元音子串
一、题目
最长的指定瑕疵度的元音子串
定义：开头和结尾都是元音字母（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;
这版代码应该是我参考别人答案写的吧。