华为OD刷题C卷 - 每日刷题 17（字符串序列判定，最长的指定瑕疵度的元音子串）

本文主要是介绍华为OD刷题C卷 - 每日刷题 17（字符串序列判定，最长的指定瑕疵度的元音子串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、（字符串序列判定）：

这段代码是解决“字符串序列判定”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，用于判断字符串S是否是字符串L的有效子串。

main方法首先读取两个字符串S和L，然后调用getResult方法并打印最后一个有效字符在L中的位置。

getResult方法使用双指针技术，初始化两个指针i和j分别遍历字符串S和L。如果两个指针所指向的字符相同，则两个指针都向前移动；如果不同，则只有j指针向前移动。这样，ans变量记录了S中最后一个字符在L中的索引位置。如果S中的所有字符在L中都未找到，则返回-1。

2、（最长的指定瑕疵度的元音子串）：

这段代码是解决“最长的指定瑕疵度的元音子串”的问题。它提供了一个Java类Main，其中包含main方法和getMaxVowel方法，以及一个辅助方法getFlaw，用于找出给定字符串中最长的、具有指定瑕疵度的元音子串。

main方法首先读取预期的瑕疵度flaw和字符串str，然后调用getMaxVowel方法并打印最长元音子串的长度。

getMaxVowel方法使用双指针技术，通过两层循环遍历字符串str的所有可能子串。使用正则表达式Pattern来检查子串是否为元音字符串，即开头和结尾都是元音字母。同时，使用getFlaw方法来计算子串的瑕疵度。如果找到满足条件的子串，则返回其长度；如果没有找到，则返回0。

getFlaw方法通过替换掉所有元音字母，计算剩余非元音字母的长度，即为瑕疵度。

3、（最长的指定瑕疵度的元音子串 - 优化版）：

这段代码是第二段代码的优化版本，它提供了一个Java类Simple，其中包含main方法和getMaxVowel方法，用于更高效地找出给定字符串中最长的、具有指定瑕疵度的元音子串。

main方法的实现与第二段代码相同。

getMaxVowel方法首先将所有元音字母存储在一个HashSet中，然后遍历字符串str，记录所有元音字母的索引。接着，使用双指针技术，通过维护一个滑动窗口来找出满足瑕疵度条件的最长元音子串。与第二段代码相比，这种方法减少了不必要的子串检查，提高了效率。

package OD258;import java.util.Scanner;/*** @description 字符串序列判定* @level 6* @score 100*//*** 题目描述* 输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。* <p>* 判定S是否是L的有效子串。* <p>* 判定规则：* <p>* S中的每个字符在L中都能找到（可以不连续），且S在Ｌ中字符的前后顺序与S中顺序要保持一致。* <p>* （例如，S=”ace”是L=”abcde”的一个子序列且有效字符是a、c、e，而”aec”不是有效子序列，且有效字符只有a、e）* <p>* 输入描述* 输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。* <p>* 先输入S，再输入L，每个字符串占一行。* <p>* 输出描述* S串最后一个有效字符在L中的位置。（首位从0开始计算，无有效字符返回-1）*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//字符串sString s = sc.nextLine();//字符串lString l = sc.nextLine();System.out.println(getResult(s, l));}//返回字符串s最后一个有效字符在字符串l中的下标public static int getResult(String s, String l) {char[] ss = s.toCharArray();char[] ls = l.toCharArray();//双指针int ans = -1;int i = 0;int j = 0;while (i < ss.length && j < ls.length) {//如果相同，则i++ j++if (ss[i] == ls[j]) {ans = j;i++;j++;} else {j++;}}return ans;}}

package OD265;import java.util.Scanner;
import java.util.regex.Pattern;/*** @description 最长的指定瑕疵度的元音子串* @level 6* @score 100*//*** 题目描述* 开头和结尾都是元音字母（aeiouAEIOU）的字符串为元音字符串，其中混杂的非元音字母数量为其瑕疵度。比如:* <p>* “a” 、 “aa”是元音字符串，其瑕疵度都为0* “aiur”不是元音字符串（结尾不是元音字符）* “abira”是元音字符串，其瑕疵度为2* 给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，如果找不到满足条件的元音字符子串，输出0。* <p>* 子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。* <p>* 输入描述* 首行输入是一个整数，表示预期的瑕疵度flaw，取值范围[0, 65535]。* <p>* 接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度(0, 65535]。* <p>* 输出描述* 输出为一个整数，代表满足条件的元音字符子串的长度。*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//预期瑕疵度int n = Integer.parseInt(sc.nextLine());//字符串String str = sc.nextLine();System.out.println(getMaxVowel(str, n));}//寻找一个字符串中满足预期瑕疵度的最长元音子串，返回最长元音子串的长度public static int getMaxVowel(String s, int flaw) {//如果长度为1if (s.length() == 1) {if (s.charAt(0) == 'a' || s.charAt(0) == 'e' || s.charAt(0) == 'i' || s.charAt(0) == 'o' || s.charAt(0) == 'u' && getFlaw(s) == flaw) {return 1;} else {return 0;}}//双指针Pattern p = Pattern.compile("^[AEIOUaeiou].*[AEIOUaeiou]$");for (int i = 0; i < s.length(); i++) {for (int j = s.length(); j > i; j--) {String temp = s.substring(i, j);//一找到就返回，一定是最大长度if (p.matcher(temp).find() && getFlaw(temp) == flaw) {return temp.length();}}}//没找到的话return 0;}//返回一个元音字符串中的瑕疵度public static long getFlaw(String s) {//开头和末尾一定是元音String newStr = s.replaceAll("[AEIOUaeiou]", "");return newStr.length();}
}

package OD265;import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.regex.Pattern;/*** @description 最长的指定瑕疵度的元音子串* @level 6* @score 100*//*** 题目描述* 开头和结尾都是元音字母（aeiouAEIOU）的字符串为元音字符串，其中混杂的非元音字母数量为其瑕疵度。比如:* <p>* “a” 、 “aa”是元音字符串，其瑕疵度都为0* “aiur”不是元音字符串（结尾不是元音字符）* “abira”是元音字符串，其瑕疵度为2* 给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，如果找不到满足条件的元音字符子串，输出0。* <p>* 子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。* <p>* 输入描述* 首行输入是一个整数，表示预期的瑕疵度flaw，取值范围[0, 65535]。* <p>* 接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度(0, 65535]。* <p>* 输出描述* 输出为一个整数，代表满足条件的元音字符子串的长度。*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Simple {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//预期瑕疵度long n = Integer.parseInt(sc.nextLine());//字符串String str = sc.nextLine();System.out.println(getMaxVowel(str, n));}//寻找一个字符串中满足预期瑕疵度的最长元音子串，返回最长元音子串的长度public static long getMaxVowel(String s, long flaw) {//所有元音字母char[] vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};//添加到set中Set<Character> vowelSet = new HashSet<>();for (char c : vowels) {vowelSet.add(c);}//存放字符串s中元音字符的下标ArrayList<Integer> vowelIndex = new ArrayList<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);//如果set中含有c，则记录该元音字母的下标if (vowelSet.contains(c)) {vowelIndex.add(i);}}//保存瑕疵度相同的最长元音子串长度int maxLen = 0;int n = vowelIndex.size();//双指针int left = 0;int right = 0;while (right < n) {//瑕疵度 后一个元音字母在s中的下标-前一个元音字母在s中的下标 - left与right中间的元音字母数量int diff = vowelIndex.get(right) - vowelIndex.get(left) - (right - left);//判断瑕疵度if (diff < flaw) {right++;} else if (diff > flaw) {left++;} else {//与预期瑕疵度相等maxLen = Math.max(maxLen, vowelIndex.get(right) - vowelIndex.get(left) + 1);//right++有可能瑕疵度也相等，但长度+1right++;}}return maxLen;}}