🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈
 
🍂个人博客首页： KJ.JK
 
💖系列专栏：华为OD机试真题(C++)

一、题目

🔸题目描述

小强在参加《密室逃生》游戏，当前关卡要求找到符合给定密码K (升序的不重复小写字母组成)的箱子, 并给出箱子编号，箱子编号
为1~N。
每个箱子中都有一个 字符串s，字符串由大写字母、小写字母、数字、标点符号、空格组成，需要在这些字符串中找到所有的字母，忽
大小写后排列出对应的密码串，并返回匹配密码的箱子序号。
 
提示：满足条件的箱子不超过1个。

🔸输入输出

输入
第一行为key的字符串，
第二行为箱子boxes，为数组样式，以空格分隔
 
● 箱子N数量满足1≤N≤10000
 
● s长度满足0≤s.length≤50
 
密码为仅包含小写字母的升序字符串，不存在重复字母
 
输出
返回对应箱子编号
如不存在符合要求的密码箱，则返回-1。

🔸样例1

输入
abc
s,sdf134 A2c4b输出
2说明
第2个箱子中的Abc，符合密码abc。

二、题目解析

最简单的就是双重for循环，统计字符数量，在和key的数量对比。大于等于，则说明当前box就是可以匹配密码的箱子，返回
当前箱子的序号。如果一直找不到， 则返回-1。
 
另一种就是：
先将key转成数组，进行字典序排序
 
外层循环依旧遍历每个box，
 
如果box.length < key.length,则肯定不行，直接下次循环
 
如果box.length >= key.length，则先将box转为小写模式，然后将box转为数组字典序排序，接下来利用两个指针k，j，分别从key的0索引
位置，和box的0索引位开始扫描，如果扫描到的key[k] == box[j]，则k++, j++，不然则只有++。
 
当k===key.length时，则说明当前box中就是匹配密码的箱子。
这种算法，最坏的情况是0(n*slen)，但是其他情况都有优化可能。

三、代码参考

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {string passTword , boxes_str;getline(cin, passTword ); // 读取第一行输入，即密码getline(cin, boxes_str); // 读取第二行输入，即所有盒子的字符串vector<string> boxes; // 创建一个字符串向量，用于存储所有盒子的字符串string box = "";for (char c : boxes_str) {if (c == ' ') { // 如果遇到空格，则将当前盒子字符串加入向量中boxes.push_back(box);box = "";} else {box += c;}}boxes.push_back(box); // 将最后一个盒子字符串加入向量中int result = -1; // 初始化结果为-1，表示未找到// 遍历所有盒子for (int i = 0; i < boxes.size(); i++) {string lowerCase = boxes[i];transform(lowerCase.begin(), lowerCase.end(), lowerCase.begin(), ::tolower); // 将盒子字符串转为小写字母vector<char> letters; // 创建一个字符向量，用于存储盒子中的字母// 遍历盒子中的每个字符for (char c : lowerCase) {if (c >= 'a' && c <= 'z') { // 如果是小写字母letters.push_back(c); // 将其加入字符向量}}sort(letters.begin(), letters.end()); // 将字符向量按字典序排序string sortedLetters = ""; // 创建一个字符串，用于拼接排好序的字母// 遍历排好序的字母向量for (char c : letters) {sortedLetters += c; // 将每个字母加入字符串中}if (sortedLetters == passTword ) { // 如果拼接后的字符串与密码相等result = i + 1; // 将结果设为当前盒子的编号break; // 跳出循环}}cout << result << endl; // 输出结果return 0;
}

作者：KJ.JK

文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习