(C卷,100分)- 最长的指定瑕疵度的元音子串（Java & JS & Python & C）

题目描述

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

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

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

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

输入描述

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

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

输出描述

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

用例

题目解析

瑕疵度计算规则如上图注解所示。

当两指针之间划定的子串的瑕疵度diff  大于  指定的瑕疵度flaw时，则左指针 l++

当两指针之间划定的子串的瑕疵度diff  小于  指定的瑕疵度flaw时，则右指针 r++

当两指针之间划定的子串的瑕疵度diff  等于  指定的瑕疵度flaw时，则记录当前子串长度，并r++

按以上逻辑，直到r指针移动到idxs数组的尾部。

Java算法源码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int flaw = sc.nextInt();
    String s = sc.next();

    System.out.println(getResult(flaw, s));
  }

  public static int getResult(int flaw, String s) {
    char[] yuan = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
    HashSet<Character> set = new HashSet<>();
    for (char c : yuan) set.add(c);

    ArrayList<Integer> idxs = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
      if (set.contains(s.charAt(i))) idxs.add(i);
    }

    int ans = 0;
    int n = idxs.size();

    int l = 0;
    int r = 0;

    while (r < n) {
      // 瑕疵度计算
      int diff = idxs.get(r) - idxs.get(l) - (r - l);

      if (diff > flaw) {
        l++;
      } else if (diff < flaw) {
        r++;
      } else {
        ans = Math.max(ans, idxs.get(r) - idxs.get(l) + 1);
        r++;
      }
    }

    return ans;
  }
}

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 输入输出处理
void (async function () {
  const flaw = parseInt(await readline());
  const str = await readline();

  console.log(getResult(str, flaw));
})();

function getResult(str, flaw) {
  const set = new Set("aeiouAEIOU");

  const idxs = [];
  for (let i = 0; i < str.length; i++) {
    if (set.has(str[i])) idxs.push(i);
  }

  let ans = 0;
  let n = idxs.length;

  let l = 0;
  let r = 0;

  while (r < n) {
    // 瑕疵度计算
    let diff = idxs[r] - idxs[l] - (r - l);

    if (diff > flaw) {
      l++;
    } else if (diff < flaw) {
      r++;
    } else {
      ans = Math.max(ans, idxs[r] - idxs[l] + 1);
      r++;
    }
  }

  return ans;
}

Python算法源码

# 输入获取
flaw = int(input())
s = input()


# 算法入口
def getResult():
    yuanSet = set(list("aeiouAEIOU"))

    idxs = []
    for i in range(len(s)):
        if s[i] in yuanSet:
            idxs.append(i)

    ans = 0

    l = 0
    r = 0

    while r < len(idxs):
        # 瑕疵度计算
        diff = idxs[r] - idxs[l] - (r - l)

        if diff > flaw:
            l += 1
        elif diff < flaw:
            r += 1
        else:
            ans = max(ans, idxs[r] - idxs[l] + 1)
            r += 1

    return ans


# 算法调用
print(getResult())

C算法源码

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

#define MAX(a,b) ((a) > (b) ? (a) : (b))

#define MAX_SIZE 65535

int main() {
    int flaw;
    scanf("%d", &flaw);

    char s[MAX_SIZE];
    scanf("%s", s);

    char* yuan = "aeiouAEIOU";

    int idxs[MAX_SIZE];
    int idxs_size = 0;

    int i = 0;
    while (s[i] != '') {
        if(strchr(yuan, s[i]) != NULL) {
            idxs[idxs_size++] = i;
        }
        i++;
    }

    int ans = 0;
    int n = idxs_size;

    int l = 0;
    int r = 0;

    while(r < n) {
        // 瑕疵度计算
        int diff = idxs[r] - idxs[l] - (r - l);

        if(diff > flaw) {
            l++;
        } else if(diff < flaw) {
            r++;
        } else {
            ans = MAX(ans, idxs[r] - idxs[l] + 1);
            r++;
        }
    }

    printf("%dn", ans);

    return 0;
}