题目描述与示例
题目描述
给定两个字符串,从字符串2
中找出字符串1
中的所有字符,去重并按照ASCII
值从小到大排序。
输入字符串1
:长度不超过1024
输入字符串2
:长度不超过1000000
字符范围满足ASCII
编码要求,按照ASCII
的值由小到大排序
输入描述
bach
bbaaccedfg
输出描述
abc
输入字符串1
为给定字符串bach
,输入字符串2
为bbaaccedfg
,从字符串2
中找出字符串1
的字符,去除重复的字符,并且按照ASCII值从小到大排序,得到输出的结果为abc
。
字符串1
中的字符h
在字符串2
中找不到不输出
示例一
输入
fach
bbaaccedfg
输出
acf
说明
解题思路
本题非常简单,直接使用哈希集合的特性进行判断和去重即可。
代码
Python
# 题目:2023B-找出符合要求的字符串子串
# 分值:100
# 作者:许老师-闭着眼睛学数理化
# 算法:哈希集合
# 代码看不懂的地方,请直接在群上提问
# 输入字符串s1,并且转换为哈希集合
set1 = set(input())
# 输入字符串s2,并且转换为哈希集合
set2 = set(input())
# 遍历set2中的字符,如果位于set1,则加入答案列表
ans = [ch for ch in set2 if ch in set1]
# 对答案列表进行排序
ans.sort()
# 输出排序后的ans合并后的结果
print("".join(ans))
Java
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入字符串s1,并且转换为哈希集合
HashSet<Character> set1 = new HashSet<>();
String input1 = scanner.nextLine();
for (char ch : input1.toCharArray()) {
set1.add(ch);
}
// 输入字符串s2,并且转换为哈希集合
HashSet<Character> set2 = new HashSet<>();
String input2 = scanner.nextLine();
for (char ch : input2.toCharArray()) {
set2.add(ch);
}
// 遍历set2中的字符,如果位于set1,则加入答案列表
StringBuilder sb = new StringBuilder();
for (char ch : set2) {
if (set1.contains(ch)) {
sb.append(ch);
}
}
// 对答案列表进行排序
char[] ans = sb.toString().toCharArray();
java.util.Arrays.sort(ans);
// 输出排序后的ans合并后的结果
System.out.println(new String(ans));
scanner.close();
}
}
C++
“`C++
#include <iostream>
#include <unordered_set>
#include <algorithm>
int main() {
// 输入字符串s1,并且转换为哈希集合
std::unordered_set<char> set1;
std::string input1;
std::cin >> input1;
for (char ch : input1) {
set1.insert(ch);
}
<pre><code>// 输入字符串s2,并且转换为哈希集合
std::unordered_set<char> set2;
std::string input2;
std::cin >> input2;
for (char ch : input2) {
set2.insert(ch);
}
// 遍历set2中的字符,如果位于set1,则加入答案列表
std::string ans;
for (char ch : set2) {
if (set1.count(ch) > 0) {
ans += ch;
}
}
// 对答案列表进行排序
std::sort(ans.begin(), ans.end());
// 输出排序后的ans合并后的结果
std::cout << ans << std::endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度:O(``NlogN``)
。排序的时间复杂度。
空间复杂度:O(``N+M``)
。哈希集合所占空间。
N
为s1
的长度,M
为s2
的长度。
说明
华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。
机试分数越⾼评级越⾼,⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知
关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)