华为OD机试 - 最长的指定瑕疵度的元音子串（Python/JS/C/C++ 2024 E卷 100分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

开头和结尾都是元音字母（aeiouAEIOU）的字符串为元音字符串，其中混杂的非元音字母数量为其瑕疵度。

比如：

• “a” 、 “aa”是元音字符串，其瑕疵度都为0
• “aiur”不是元音字符串（结尾不是元音字符）
• “abira”是元音字符串，其瑕疵度为2

给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，如果找不到满足条件的元音字符子串，输出0。

子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。

二、输入描述

首行输入是一个整数，表示预期的瑕疵度flaw，取值范围[0, 65535]。

接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度(0, 65535]。

三、输出描述

输出为一个整数，代表满足条件的元音字符最长子串的长度。

四、测试用例

1、输入

2
nezhastudyjavaveryhard

2、输出

5

3、说明

掌握核心编程思想，让你的编程不再烦恼。

开头是元音，结尾是元音，中间出现的非元音字符是瑕疵度。

符合要求的子串有：

• ezha
• astu
• avave

最长的是avave，长度5。

五、解题思路

核心思想：

开头是元音，结尾是元音，中间出现的非元音字符是瑕疵度

这道题的关键是正则表达式的合理使用。

六、Python算法源码

import re

def main():
    import sys
    import sys

    # 读取标准输入的所有行
    input_lines = sys.stdin.read().splitlines()
    
    # 读取瑕疵度flaw
    flaw = int(input_lines[0])
    
    # 读取仅由字符a-z和A-Z组成的字符串
    str_input = input_lines[1]
    
    # 定义元音字母集合，包括大小写
    vowels = "aeiouAEIOU"
    
    # 构建正则表达式
    if flaw == 0:
        # 当瑕疵度为0时，匹配连续的至少一个元音字母
        regex = f"[{vowels}]+"
    else:
        # 当瑕疵度大于0时，匹配以元音字母开头和结尾，中间最多有flaw个非元音字母
        regex = f"[{vowels}](?:[^${vowels}]{{0,{flaw}}}[{vowels}])+"
    
    # 编译正则表达式
    pattern = re.compile(regex)
    
    # 寻找所有符合要求的子串
    matches = pattern.finditer(str_input)
    
    # 存储符合要求的子串的最大长度
    max_length = 0
    
    # 遍历所有匹配
    for match in matches:
        # 获取符合要求的子串
        matched_substring = match.group()
        
        # 更新最大长度
        if len(matched_substring) > max_length:
            max_length = len(matched_substring)
    
    # 输出符合要求的子串的最大长度
    print(max_length)

if __name__ == "__main__":
    main()

七、JavaScript算法源码

// 引入readline模块以读取输入
const readline = require('readline');

// 创建接口以读取标准输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
let currentLine = 0;

// 读取所有输入行
rl.on('line', (line) => {
    inputLines.push(line);
});

// 输入结束后执行的函数
rl.on('close', () => {
    // 读取瑕疵度flaw
    let flaw = parseInt(inputLines[0]);

    // 读取仅由字符a-z和A-Z组成的字符串
    let str = inputLines[1];

    // 定义元音字母集合，包括大小写
    const vowels = "aeiouAEIOU";

    // 构建正则表达式
    let regex = "";
    if (flaw === 0) {
        // 当瑕疵度为0时，匹配连续的至少一个元音字母
        regex = `[${vowels}]+`;
    } else {
        // 当瑕疵度大于0时，匹配以元音字母开头和结尾，中间最多有flaw个非元音字母
        regex = `[${vowels}](?:[^${vowels}]{0,${flaw}}[${vowels}])+`;
    }

    // 编译正则表达式
    const pattern = new RegExp(regex);

    // 寻找所有符合要求的子串
    const matches = str.matchAll(pattern);

    // 存储符合要求的子串的最大长度
    let maxLength = 0;

    // 遍历所有匹配
    for (const match of matches) {
        // 获取符合要求的子串
        let matchedSubstring = match[0];

        // 更新最大长度
        if (matchedSubstring.length > maxLength) {
            maxLength = matchedSubstring.length;
        }
    }

    // 输出符合要求的子串的最大长度
    console.log(maxLength);
});

八、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <regex.h>

int main(){
    int flaw;
    char str[1001]; // 假设输入字符串长度不超过1000
    
    // 读取瑕疵度flaw
    scanf("%d", &flaw);
    
    // 读取仅由字符a-z和A-Z组成的字符串
    scanf("%s", str);
    
    // 定义元音字母集合，包括大小写
    char vowels[] = "aeiouAEIOU";
    
    // 构建正则表达式
    char regex[2000] = ""; // 足够大的缓冲区
    if(flaw == 0){
        // 当瑕疵度为0时，匹配连续的至少一个元音字母
        sprintf(regex, "[%s]+", vowels);
    }
    else{
        // 当瑕疵度大于0时，匹配以元音字母开头和结尾，中间最多有flaw个非元音字母
        sprintf(regex, "[%s](?:[^%s]{0,%d}[%s])+", vowels, vowels, flaw, vowels);
    }
    
    // 编译正则表达式
    regex_t regex_compiled;
    int reti = regcomp(&regex_compiled, regex, REG_EXTENDED);
    if (reti) {
        fprintf(stderr, "Could not compile regex\n");
        exit(1);
    }
    
    // 寻找所有符合要求的子串
    regmatch_t pmatch[1];
    int max_length = 0;
    const char *p = str;
    int offset = 0;
    
    while(regexec(&regex_compiled, p, 1, pmatch, 0) == 0){
        // 计算匹配的起始和结束位置
        int start = pmatch[0].rm_so + offset;
        int end = pmatch[0].rm_eo + offset;
        
        // 计算匹配的子串长度
        int length = end - start;
        if(length > max_length){
            max_length = length;
        }
        
        // 移动指针，避免重复匹配
        p += pmatch[0].rm_eo;
        offset += pmatch[0].rm_eo;
    }
    
    // 输出符合要求的子串的最大长度
    printf("%d\n", max_length);
    
    // 释放正则表达式的内存
    regfree(&regex_compiled);
    
    return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
#include <regex>
using namespace std;

int main(){
    int flaw;
    string str;
    
    // 读取瑕疵度flaw
    cin >> flaw;
    
    // 读取仅由字符a-z和A-Z组成的字符串
    cin >> str;
    
    // 定义元音字母集合，包括大小写
    string vowels = "aeiouAEIOU";
    
    // 构建正则表达式
    string regex_str;
    if(flaw == 0){
        // 当瑕疵度为0时，匹配连续的至少一个元音字母
        regex_str = "[" + vowels + "]+";
    }
    else{
        // 当瑕疵度大于0时，匹配以元音字母开头和结尾，中间最多有flaw个非元音字母
        regex_str = "[" + vowels + "](?:[^" + vowels + "]{0," + to_string(flaw) + "}[" + vowels + "])+";
    }
    
    // 编译正则表达式
    regex pattern(regex_str);
    
    // 寻找所有符合要求的子串
    smatch match;
    string::const_iterator searchStart(str.cbegin());
    
    // 存储符合要求的子串的最大长度
    int max_length = 0;
    
    while(regex_search(searchStart, str.cend(), match, pattern)){
        // 获取符合要求的子串
        string matched_substring = match[0];
        
        // 更新最大长度
        if(matched_substring.length() > max_length){
            max_length = matched_substring.length();
        }
        
        // 移动搜索起始位置
        searchStart = match[0].second;
    }
    
    // 输出符合要求的子串的最大长度
    cout << max_length << endl;
    
    return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。