题目描述与示例
题目描述
小强正在参加《密室逃生》游戏,当前关卡要求找到符合给定密码 K
(升序的不重复小写字母组成)的箱子,并给出箱子编号,箱子编号为 1~N
。
每个箱子中都有一个字符串 s
,字符串由大写字母,小写字母,数字,标点符号,空格组成,需要在这些字符串中找出所有的字母,忽略大小写且去重后排列出对应的密码串,并返回匹配密码的箱子序号。
注意:满足条件的箱子不超过 1
个。
输入描述
第一行为表示密码 K
的字符串
第二行为一系列箱子 boxes
,为字符串数组样式,以空格分隔
箱子 N
数量满足 1<=N<=10000
,代表每一个箱子的字符串 s
的长度满足 0 <= s.length <= 50
,密码为仅包含小写字母的升序字符串,且不存在重复字母,密码 K
长度满足1 <= K.length <= 26
输出描述
返回对应箱子编号,如不存在符合要求的密码箱,则返回-1
补充说明
箱子中字符拼出的字符串与密码的匹配忽略大小写,且要求与密码完全匹配,如密码 abc
匹配 aBc
,但是密码 abc
不匹配 abcd
示例 1
输入
abc
s,sdf134 A2c4b
输出
2
说明
第 2 个箱子中的 Abc
,符合密码 abc
示例 2
输入
abc
s,sdf134 A2c4bd 523[]
输出
-1
说明
第 2
个箱子中的 Abcd
,与密码不完全匹配,不符合要求。
解题思路
本题思路非常直接。由于密码K
不包含重复字符,每一个箱子字符串s
也要做去重处理,因此我们可以直接分别用哈希集合K_set
和s_set
来表示密码和箱子字符串。
遍历boxes
中的每一个字符串s
,并且挑选出其中的所有字母ch
,并做ch.lower()
即转为小写的处理,再所有转为小写的字母构建为s_set
,再比较K_set
和s_set
是否完全相等即可。若相等,则该箱子字符串s
所对应的编号i+1
(之所以+1
是因为箱子的编号是从1
而不是从0
开始的)即为答案。
思考:如果稍微修改本题的条件,即箱子字符串不做去重处理,即s = "aa"
与 K = "a"
不能匹配,那么应该如何修改代码?
代码
Python
# 题目:2023Q1A-寻找关键钥匙
# 分值:100
# 作者:闭着眼睛学数理化
# 算法:哈希集合
# 代码有看不懂的地方请直接在群上提问
K = input() # 输入密码字符串K
boxes = input().split() # 输入箱子字符串数组boxes
ans = -1 # 初始化答案为-1
K_set = set(K) # 得到密码字符串所对应的集合
# 遍历boxes字符串中的所有索引i和字符串s
for i, s in enumerate(boxes):
# 得到字符串s中所有字母的集合,其中大写字母均转化为小写字母
s_set = {ch.lower() for ch in s if ch.isalpha()}
if K_set == s_set: # 如果该集合与密码集合相等,则得到了符合要求的箱子编号
ans = i+1 # 注意箱子编号是从1开始的
break # 因为只有一个箱子满足要求,所以此时直接退出循环即可
print(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);
String K = scanner.nextLine(); // 输入密码字符串K
String[] boxes = scanner.nextLine().split(" "); // 输入箱子字符串数组boxes
int ans = -1; // 初始化答案为-1
HashSet<Character> K_set = new HashSet<>(); // 得到密码字符串所对应的集合
for (char ch : K.toCharArray()) {
K_set.add(ch);
}
// 遍历boxes字符串中的所有索引i和字符串s
for (int i = 0; i < boxes.length; i++) {
String s = boxes[i];
HashSet<Character> s_set = new HashSet<>(); // 得到字符串s中所有字母的集合,其中大写字母均转化为小写字母
for (char ch : s.toCharArray()) {
if (Character.isLetter(ch)) {
s_set.add(Character.toLowerCase(ch));
}
}
if (K_set.equals(s_set)) { // 如果该集合与密码集合相等,则得到了符合要求的箱子编号
ans = i + 1; // 注意箱子编号是从1开始的
break; // 因为只有一个箱子满足要求,所以此时直接退出循环即可
}
}
System.out.println(ans);
scanner.close();
}
}
C++
“`C++
#include <iostream>
#include <sstream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string K;
getline(cin, K); // 输入密码字符串K
<pre><code>string line;
getline(cin, line);
stringstream ss(line);
vector<string> boxes;
string box;
while (ss >> box) {
boxes.push_back(box);
} // 输入箱子字符串数组boxes
int ans = -1; // 初始化答案为-1
// 得到密码字符串所对应的集合
unordered_set<char> K_set(K.begin(), K.end());
// 遍历boxes字符串中的所有索引i和字符串s
for (int i = 0; i < boxes.size(); i++) {
string s = boxes[i];
unordered_set<char> s_set;
// 得到字符串s中所有字母的集合,其中大写字母均转化为小写字母
for (char ch : s) {
if (isalpha(ch)) {
s_set.insert(tolower(ch));
}
}
if (K_set == s_set) { // 如果该集合与密码集合相等,则得到了符合要求的箱子编号
ans = i + 1; // 注意箱子编号是从1开始的
break; // 因为只有一个箱子满足要求,所以此时直接退出循环即可
}
}
cout << ans << endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度:O(k+NM)
。
空间复杂度:O(k+M)
。
其中N
为boxes的长度,M
为s
的平均长度,k
为K
的长度。
说明
华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。
机试分数越⾼评级越⾼,⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知
关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)