华为OD机试算法题新老题库练习及源码

老题库
- 21.字符串序列判定
- 22.最长的指定瑕疵度的元音子串

郑重声明： 1.博客中涉及题目为网上搜索而来，若侵权，请联系作者删除。源码内容为个人原创，仅允许个人学习使用。
2.博客中涉及的源码非官方答案，不保证正确性。
3.切勿将博客内容用于官方考试，若应用于官方考试，后果自行承担，与原作者无关。
4.原作者保留知识版权，且有权向侵权者追究刑事责任

老题库

21.字符串序列判定

题目描述

输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。
判定S是否是L的有效子串。
判定规则：
S中的每个字符在L中都能找到（可以不连续），且S在Ｌ中字符的前后顺序与S中顺序要保持一致。
（例如，S=”ace”是L=”abcde”的一个子序列且有效字符是a、c、e，而”aec”不是有效子序列，且有效字符只有a、e）

输入描述

输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。
先输入S，再输入L，每个字符串占一行。

输出描述

S串最后一个有效字符在L中的位置。（首位从0开始计算，无有效字符返回-1）

输入	输出	说明
ace abcde	4	a出现的索引为0 c出现的索引为2 e出现的索引为4 ace索引顺序相同，因此ace为abcde的子串，其最后一位为e其索引为4
fgh abcde	-1	fgh三个字符不是abcde的有效子串

源码和解析
解析：

这个题其实理解起来蛮简单，但是有个点需要注意的是若某个字符在目标字符中出现了几次，这个时候该字符到底取哪个索引？总不能只取第一个索引吧。
例如：
输入第一个字符为ace 输入的第二个字符为abece
这个时候匹配的索引情况可能为a-0 c-3 e-[2|4]
很明显，这个ace仍然是abece的有效子串，因为0，3,4这组索引顺序与原字符ace顺序一致。
这个题可以使用正则快速完成，如果对正则不熟悉，也可以使用字符串的indexOf方法来完成

示例代码（正则写法）：

import java.util.regex.Matcher;
import java.util.regex.Pattern;public class T21 {public static void main(String[] args) {String input1 = "ace";String input2 = "abeceee";String regex = ""; // a[a-z]*c[a-z]*e[a-z]*for (int i = 0; i < input1.length(); i++) {regex += input1.charAt(i) + "[a-z]*";}System.out.println(regex);Pattern pattern = Pattern.compile(regex);Matcher matcher = pattern.matcher(input2);// public int end() 返回最后匹配字符之后的偏移量。if (matcher.find()) {System.out.println(matcher.end() - 1);}else{System.out.println(-1);}}
}

示例代码（逐个查找索引法）：

import java.util.ArrayList;
import java.util.List;public class T21 {public static void main(String[] args) {String input1 = "ace";String input2 = "abaeceece";// 解决思路：将input1的所有字符在2中出现的索引全部记录下来，将索引存起来 最后按顺序去判断List<List<Integer>> indexList = new ArrayList<List<Integer>>();for (int i = 0; i < input1.length(); i++) {char c = input1.charAt(i);List<Integer> indexItem = new ArrayList<>();StringBuilder stringBuilder = new StringBuilder(input2);while (stringBuilder.indexOf(c + "") != -1) {indexItem.add(stringBuilder.indexOf(c + ""));stringBuilder.setCharAt(stringBuilder.indexOf(c + ""), '_');}if (indexItem.size() != 0)indexList.add(indexItem);}// System.out.println(indexList); [[0], [3], [2, 4, 5, 6]]// 找出可能出现的排序 即逐个列表查找，若能找到合适的序列，则成功List<List<Integer>> resList = new ArrayList<>();for (int i = 0; i < indexList.size(); i++) {resList = mult2(resList, indexList.get(i));// System.out.println(resList);}System.out.println(resList);int finalMaxIndex = -1;// 最后的且最大的那个有序的for (List<Integer> indexList1 : resList) {boolean flag = true;// 是否出现是有序的Integer last = indexList1.get(0);// 上一个索引for (int i = 1; i < indexList1.size(); i++) {if (indexList1.get(i) <= last) {flag = false;break;}}if (flag) {// 出现一次有序的了if (indexList1.get(indexList1.size() - 1) > finalMaxIndex) {finalMaxIndex = indexList1.get(indexList1.size() - 1);}}}System.out.println(finalMaxIndex);}// 二维数组 乘以一维数组public static List<List<Integer>> mult2(List<List<Integer>> list1,List<Integer> list2) {List<List<Integer>> objList = new ArrayList<>();if (list1.size() == 0) {for (Integer item2 : list2) {List<Integer> item11 = new ArrayList<>();item11.add(item2);objList.add(item11);}return objList;}for (List<Integer> item : list1) {for (Integer item2 : list2) {List<Integer> item11 = new ArrayList<>();item11.addAll(item);item11.add(item2);objList.add(item11);}}return objList;}
}

[[0, 2], [4, 7], [3, 5, 6, 8]] 对应a c e出现的索引
[[0, 4, 3], [0, 4, 5], [0, 4, 6], [0, 4, 8], [0, 7, 3], [0, 7, 5], [0, 7, 6], [0, 7, 8], [2, 4, 3], [2, 4, 5], [2, 4, 6], [2, 4, 8], [2, 7, 3], [2, 7, 5], [2, 7, 6], [2, 7, 8]] 对应ace索引组合可能出现的情况

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

输入描述

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

输出描述