全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：字符串解密
知识点：数组字符串排序
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：给定两个字符串string1和string2。string1是一个被加扰的字符串。string1由小写英文字母（’a’~’z’）和数字字符（’0’~’9’）组成，而加扰字符串由’0’~’9’、’a’~’f’组成。string1里面可能包含0个或多个加扰子串，剩下可能有0个或多个有效子串，这些有效子串被加扰子串隔开。
string2是一个参考字符串，仅由小写英文字母（’a’~’z’）组成。
你需要在string1字符串里找到一个有效子串，这个有效子串要同时满足下面两个条件：
1）这个有效子串里不同字母的数量不超过且最接近于string2里不同字母的数量，即小于或等于string2里不同字母的数量的同时且最大。
2）这个有效子串是满足条件（1）里的所有子串（如果有多个的话）里字典序最大的一个。
如果没有找到合适条件的子串的话，请输出”Not Found”
示例：
输入字符串string1为”thisisanewday111forme”，输入字符串string2为”good”。string1里有效子串和加扰子串分割后可表示为：”thisis”+”a”+”n”+”e”+”w”+”da”+”y”+”111f”+”orm”+”e”，去除加扰子串（”a”、”e”、”da”、”111f”、”e”）后的有效子串候选为(“thisis”, “n”, “w”, “y”, “orm”)。输入字符串string2里不同字母的数量为3（’g’、’o’、’d’），从有效子串候选里可以找出”orm”满足要求，其不同字母的数量为3，最接近于string2不同字母的数量。
输入描述：
input_string1
input_string2
说明：输入为两个字符串，第1行是题目里的string1（被加扰的字符串），第2行是题目里的string2（参考字符串）
输出描述：
output_string
说明：输出为一个字符串（有效字符串）
补充说明：
输入字符串string1的长度在1~100000之间，string2的长度在1~500之间
示例1
输入：
123admyffc79pt
ssyy
输出：
pt
说明：
将输入字符串1里的加扰子串”123ad”、”ffc79″去除后得到有效子串序列：”my”、”pt”，其中”my”里不同字母的数量为2（有’m’和’y’两个不同字母），”pt”里不同字母的数量为2（有’p’和’t’两个不同字母）；输入字符串2里不同字母的数量为2（有’s’和’y’两个不同字母）。
可得到最终输出结果为”pt”，其不同字母的数量最接近于”ssyy”里不同字母的数量的同时字典序最大。
示例2
输入：
123admyffc79ptaagghi2222smeersst88mnrt
ssyyfgh
输出：
mnrt
说明：
将输入字符串1里的加扰子串”123ad”、”ffc79″、”aa”、”2222″、”ee”、”88″去除后得到有效子串序列：”my”、”pt”、”gghi”、”sm”、”rsst”、”mnrt”；输入字符串2里不同字母的数量为5（有’s’、’y’、’f’、’g’、’h’ 5个不同字母）。
可得到最终输出结果为”mnrt”，其不同字母的数量（为4）最接近于”ssyyfgh”里不同字母的数量，其他有效子串不同字母的数量都小于”mnrt”。
示例3
输入：
abcmnq
rt
输出：
Not Found
说明：
将输入字符串1里的加扰子串”abc”去除后得到有效子串序列：”mnq”；输入字符串2里不同字母的数量为2（有’r’、’t’两个不同的字母）。
可得到最终的输出结果为”Not Found”，没有符合要求的有效子串，因有效子串的里不同字母的数量（为3），大于输入字符串2里的不同字母的数量
解题思路：
根据题意：string1的子串要求：
1、只包含字母 g – z
2、且子串中不同字母的数量小于等于string2中的不同字母数量
求字符串中不同字母数量可以使用set，set可以去重，set的长度则为不同字母的数量。
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.*;
/**
* @title 字符串解密
* @Description 给定两个字符串string1和string2。string1是一个被加扰的字符串。
* string1由小写英文字母（'a'~'z'）和数字字符（'0'~'9'）组成，而加扰字符串由'0'~'9'、'a'~'f'组成。
* string1里面可能包含0个或多个加扰子串，剩下可能有0个或多个有效子串，这些有效子串被加扰子串隔开。
* string2是一个参考字符串，仅由小写英文字母（'a'~'z'）组成。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/13
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String string1 = sc.nextLine();
String string2 = sc.nextLine();
String temp = "";
List<String> list = new ArrayList<>(); //符合要求的字符串集合
int max = 0;
int diffLen = length(string2); //string2不同字母的数量
for (int i = 0; i < string1.length(); i++) {
char c = string1.charAt(i);
if (c >= 'g' && c <= 'z') { //g到z属于有效字母
temp += c;
if (i != string1.length() - 1) continue; //需要考虑最后一个字母
}
if (!temp.equals("")) {
int len = length(temp); //子串中不同字母的数量
if (len <= diffLen && len >= max) { //数量必须要小于等于string2的不同字母数量
if (len > max) {
list.clear(); //有更接近string2的不同字母数量，清除list
}
max = Math.max(max, len); //更新max值
list.add(temp);
}
temp = ""; //temp已处理，需要置空
}
}
Collections.sort(list);
System.out.println(list.size() == 0 ? "Not Found" : list.get(list.size() - 1));
}
/**
* 求字符串中不同字母的数量
* @param s
* @return
*/
public static int length(String s) {
Set<Character> set = new HashSet<>();
for (char c : s.toCharArray()) {
set.add(c);
}
return set.size();
}
}
代码实现二：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
/**
* @title 字符串解密
* @Description 给定两个字符串string1和string2。string1是一个被加扰的字符串。
* string1由小写英文字母（'a'~'z'）和数字字符（'0'~'9'）组成，而加扰字符串由'0'~'9'、'a'~'f'组成。
* string1里面可能包含0个或多个加扰子串，剩下可能有0个或多个有效子串，这些有效子串被加扰子串隔开。
* string2是一个参考字符串，仅由小写英文字母（'a'~'z'）组成。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/13
*/
public class Main {
public static String an() {
Scanner sc = new Scanner(System.in);
String s1 = sc.nextLine();
String s2 = sc.nextLine();
HashSet<String> set = new HashSet<>();
for (char c : s2.toCharArray()) {
set.add(c + "");
}
String sub = "1234567890abcdef";
int index = 0;
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < s1.length(); i++) {
if (sub.contains(s1.charAt(i) + "")) {
list.add(s1.substring(index, i));
index = i + 1;
} else {
if (i == s1.length() - 1) {
list.add(s1.substring(index));
}
}
}
String end = "";
for (int i = 0; i < list.size(); i++) {
String cs = list.get(i);
if (cs.length() > 0) {
HashSet<String> cset = new HashSet<>();
for (int j = 0; j < cs.length(); j++) {
cset.add(cs.charAt(j) + "");
}
int len = cset.size();
if (len <= set.size()) {
HashSet<String> sset = new HashSet<>();
for (int j = 0; j < end.length(); j++) {
sset.add(end.charAt(j) + "");
}
int sslen = sset.size();
if (len > sslen) {
end = cs;
} else if (len == sslen && cs.compareTo(end) > 0) {
end = cs;
}
}
}
}
if (end.length() > 0) {
return end;
} else {
return "Not Found";
}
}
public static void main(String[] args) {
String answer = an();
System.out.println(answer);
}
}
相关文章
