机考E卷100分题 - 猜字谜
题目描述
小王设计了一个简单的猜字谜游戏，游戏的谜面是一个错误的单词，比如nesw，玩家需要猜出谜底库中正确的单词。猜中的要求如下：
对于某个谜面和谜底单词，满足下面任一条件都表示猜中：
- 变换顺序以后一样的，比如通过变换w和e的顺序，“nwes”跟“news”是可以完全对应的；
- 字母去重以后是一样的，比如“woood”和“wood”是一样的，它们去重后都是“wod”
请你写一个程序帮忙在谜底库中找到正确的谜底。谜面是多个单词，都需要找到对应的谜底，如果找不到的话，返回”not found”
输入描述
- 谜面单词列表，以“,”分隔
- 谜底库单词列表，以","分隔
输出描述
- 匹配到的正确单词列表，以","分隔
- 如果找不到，返回"not found"
备注
- 单词的数量N的范围：0 < N < 1000
- 词汇表的数量M的范围：0 < M < 1000
- 单词的长度P的范围：0 < P < 20
- 输入的字符只有小写英文字母，没有其他字符
示例1
输入
conection
connection,today
12
输出
connection
1
示例2
输入
bdni,wooood
bind,wrong,wood
12
输出
bind,wood
1
解题思路
猜中的情况：
- 变换顺序以后一样的，比如通过变换w和e的顺序，“nwes”跟“news”是可以完全对应的；
- 字母去重以后是一样的，比如“woood”和“wood”是一样的，它们去重后都是“wod”
- 以上两个同时满足
直接对谜底和谜面单词进行去重+字典序排序，然后对比即可。
两个字符串变为数组后进行排序，如果排序后的数组一致，则表示变序后一致。
去重后是否一致:将两个字符串去重后加入列表中，如果两个列表一致，则表示去重后一致。
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取谜面单词列表，以逗号分隔
String[] puzzleWords = scanner.nextLine().split(",");
// 读取谜底库单词列表，以逗号分隔
String[] answerBank = scanner.nextLine().split(",");
// 创建一个列表，用于存储匹配到的正确单词
List<String> matchedAnswers = new ArrayList<>();
// 遍历谜面单词列表
for (String puzzleWord : puzzleWords) {
// 去除谜面单词中的重复字母，TreeSet自动升序排序
String puzzleWordNoDuplicate = String.join("", new TreeSet<>(Arrays.asList(puzzleWord.split(""))));
// 标记是否匹配到对应的谜底
boolean isFound = false;
// 遍历谜底库单词列表
for (String answer : answerBank) {
// 去除谜底单词中的重复字母，TreeSet自动升序排序
String answerNoDuplicate = String.join("", new TreeSet<>(Arrays.asList(answer.split(""))));
// 如果去重后的谜面单词与谜底单词相同，则将谜底单词添加到结果列表中，并将 isFound 标记为 true
if (puzzleWordNoDuplicate.equals(answerNoDuplicate)) {
matchedAnswers.add(answer);
isFound = true;
}
}
// 如果没有找到匹配的单词，则将 "not found" 添加到结果列表中
if (!isFound) {
matchedAnswers.add("not found");
}
}
// 输出匹配到的正确单词列表，以逗号分隔
System.out.println(String.join(",", matchedAnswers));
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344
Python
puzzle_words = input().split(",")
word_bank = input().split(",")
# 用于存储匹配到的正确单词列表
matched_words = []
# 遍历每个谜面
for puzzle_word in puzzle_words:
# 将谜面中的字符去重并排序
sorted_puzzle_word = "".join(sorted(set(puzzle_word)))
# 标记是否找到匹配的谜底
found = False
# 遍历每个谜底
for word in word_bank:
# 将谜底中的字符去重并排序
sorted_word = "".join(sorted(set(word)))
# 判断谜底是否与谜面匹配
if sorted_puzzle_word == sorted_word:
# 将匹配到的谜底添加到结果列表中
matched_words.append(word)
# 标记为已找到匹配的谜底
found = True
# 如果没有找到匹配的谜底，将"not found"添加到结果列表中
if not found:
matched_words.append("not found")
# 输出匹配到的正确单词列表，以","分隔
print(",".join(matched_words))
123456789101112131415161718192021222324252627282930313233
JavaScript
// 导入 readline 模块，用于从标准输入读取数据
const readline = require('readline');
// 创建 readline 接口实例，用于处理输入输出
const rl = readline.createInterface({
input: process.stdin, // 指定标准输入流
output: process.stdout // 指定标准输出流
});
// 监听第一个输入行，即谜面单词列表
rl.on('line', (puzzleInput) => {
// 监听第二个输入行，即谜底库单词列表
rl.on('line', (answerBankInput) => {
// 将谜面单词列表按照逗号分隔成数组
const puzzles = puzzleInput.split(',');
// 将谜底库单词列表按照逗号分隔成数组
const answerBank = answerBankInput.split(',');
// 用于存储匹配到的正确单词
const matchedAnswers = [];
// 遍历每一个谜面单词
for (let puzzleIndex = 0; puzzleIndex < puzzles.length; puzzleIndex++) {
// 对谜面单词进行排序并去重
const sortedPuzzle = puzzles[puzzleIndex].split('') // 将单词分割成字符数组
.sort() // 对字符数组进行排序
.filter((char, index, array) => {
// 通过过滤函数去重，保留第一次出现的字符
return index === 0 || char !== array[index - 1];
})
.join(''); // 将处理后的字符数组重新组合成字符串
let found = false; // 用于标记当前谜面是否找到匹配的正确单词
// 遍历谜底库中的每一个单词
for (let answerIndex = 0; answerIndex < answerBank.length; answerIndex++) {
// 对谜底单词进行排序并去重，方法同上
const sortedAnswer = answerBank[answerIndex].split('')
.sort()
.filter((char, index, array) => {
return index === 0 || char !== array[index - 1];
})
.join('');
// 如果处理后的谜面单词和谜底单词相同，则表示匹配成功
if (sortedPuzzle === sortedAnswer) {
// 将匹配到的谜底单词加入结果数组
matchedAnswers.push(answerBank[answerIndex]);
found = true; // 标记为已找到匹配
break; // 一旦找到匹配的正确单词，跳出当前循环
}
}
// 如果没有找到匹配的正确单词，加入"not found"标记
if (!found) {
matchedAnswers.push("not found");
}
}
// 将匹配到的正确单词以逗号分隔的形式输出
console.log(matchedAnswers.join(', '));
rl.close(); // 关闭 readline 接口
});
});
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
C++
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
string input_puzzles, input_solutions;
getline(cin, input_puzzles); // 读取第一行谜面单词列表
getline(cin, input_solutions); // 读取第二行谜底单词列表
vector<string> puzzles, solutions;
string temp = "";
// 将输入的谜面单词列表以“,”分隔并存储在puzzles向量中
for (char c : input_puzzles) {
if (c == ',') {
puzzles.push_back(temp); // 遇到逗号，将temp中的单词加入puzzles
temp = ""; // 重置temp
} else {
temp += c; // 将字符加入temp
}
}
puzzles.push_back(temp); // 将最后一个单词加入puzzles
temp = "";
// 将输入的谜底库单词列表以“,”分隔并存储在solutions向量中
for (char c : input_solutions) {
if (c == ',') {
solutions.push_back(temp); // 遇到逗号，将temp中的单词加入solutions
temp = ""; // 重置temp
} else {
temp += c; // 将字符加入temp
}
}
solutions.push_back(temp); // 将最后一个单词加入solutions
vector<string> matched_solutions; // 用于存储匹配到的谜底单词
// 遍历每个谜面单词
for (string puzzle : puzzles) {
string sorted_puzzle = puzzle;
sort(sorted_puzzle.begin(), sorted_puzzle.end()); // 对谜面单词排序
sorted_puzzle.erase(unique(sorted_puzzle.begin(), sorted_puzzle.end()), sorted_puzzle.end()); // 去重
bool found = false; // 标记是否找到匹配的谜底单词
// 遍历谜底库中的每个单词
for (string solution : solutions) {
string sorted_solution = solution;
sort(sorted_solution.begin(), sorted_solution.end()); // 对谜底单词排序
sorted_solution.erase(unique(sorted_solution.begin(), sorted_solution.end()), sorted_solution.end()); // 去重
if (sorted_puzzle == sorted_solution) { // 如果排序去重后的结果相同
matched_solutions.push_back(solution); // 将该谜底单词加入匹配结果中
found = true; // 标记为找到匹配
break; // 跳出当前循环
}
}
if (!found) { // 如果未找到匹配的谜底单词
matched_solutions.push_back("not found"); // 加入"not found"
}
}
// 输出第一个匹配结果
cout << matched_solutions[0];
// 输出剩余的匹配结果，中间以逗号分隔
for (int i = 1; i < matched_solutions.size(); i++) {
cout << "," << matched_solutions[i];
}
return 0; // 程序结束
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
C语言
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 自定义比较函数，用于qsort中的字符排序
int compare(const void *a, const void *b) {
return *(char *)a - *(char *)b;
}
// 去重函数，将字符串中的重复字符移除
void remove_duplicates(char *str) {
int length = strlen(str);
if (length < 2) return;
int j = 0;
for (int i = 1; i < length; i++) {
if (str[i] != str[j]) {
j++;
str[j] = str[i];
}
}
str[j + 1] = '\0';
}
int main() {
char input_puzzles[1000], input_solutions[1000];
// 从标准输入读取谜面和谜底列表
fgets(input_puzzles, sizeof(input_puzzles), stdin); // 读取第一行谜面单词列表
fgets(input_solutions, sizeof(input_solutions), stdin); // 读取第二行谜底单词列表
// 移除字符串末尾的换行符
input_puzzles[strcspn(input_puzzles, "\n")] = '\0';
input_solutions[strcspn(input_solutions, "\n")] = '\0';
char *puzzles[1000];
char *solutions[1000];
int puzzle_count = 0, solution_count = 0;
// 将谜面单词列表以“,”分隔并存储在puzzles数组中
char *token = strtok(input_puzzles, ",");
while (token != NULL) {
puzzles[puzzle_count++] = strdup(token); // 将分隔出的单词复制到puzzles中
token = strtok(NULL, ",");
}
// 将谜底库单词列表以“,”分隔并存储在solutions数组中
token = strtok(input_solutions, ",");
while (token != NULL) {
solutions[solution_count++] = strdup(token); // 将分隔出的单词复制到solutions中
token = strtok(NULL, ",");
}
char *matched_solutions[1000];
int match_count = 0;
// 遍历每个谜面单词
for (int i = 0; i < puzzle_count; i++) {
char sorted_puzzle[1000];
strcpy(sorted_puzzle, puzzles[i]);
qsort(sorted_puzzle, strlen(sorted_puzzle), sizeof(char), compare); // 对谜面单词排序
remove_duplicates(sorted_puzzle); // 去重
int found = 0; // 标记是否找到匹配的谜底单词
// 遍历谜底库中的每个单词
for (int j = 0; j < solution_count; j++) {
char sorted_solution[1000];
strcpy(sorted_solution, solutions[j]);
qsort(sorted_solution, strlen(sorted_solution), sizeof(char), compare); // 对谜底单词排序
remove_duplicates(sorted_solution); // 去重
if (strcmp(sorted_puzzle, sorted_solution) == 0) { // 如果排序去重后的结果相同
matched_solutions[match_count++] = solutions[j]; // 将该谜底单词加入匹配结果中
found = 1; // 标记为找到匹配
break; // 跳出当前循环
}
}
if (!found) { // 如果未找到匹配的谜底单词
matched_solutions[match_count++] = "not found"; // 加入"not found"
}
}
// 输出第一个匹配结果
printf("%s", matched_solutions[0]);
// 输出剩余的匹配结果，中间以逗号分隔
for (int i = 1; i < match_count; i++) {
printf(",%s", matched_solutions[i]);
}
// 释放动态分配的内存
for (int i = 0; i < puzzle_count; i++) {
free(puzzles[i]);
}
for (int i = 0; i < solution_count; i++) {
free(solutions[i]);
}
return 0;
}
大厂原题(全网最全，持续更新) 文章被收录于专栏
主要记录自己的刷题日常，学而时习之。
