华为OD机试 - 匿名信（Python/JS/C/C++ 2024 E卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

电视剧《分界线Q》里面有一个片段，男主为了向警察透露案件细节，且不暴露自己，于是将报刊上的字减下来，剪拼成匿名信。
现在一名举报人，希望借鉴这部片段，使用英文报刊为范本来剪拼举报信。
但为了增加文章的混淆程度，尽量避免每个单词中字母数量一致即可，不关注每个字母的顺序。
解释：单词n允许抄袭过n的字母组合。

报纸代表newspaper，匿名信代表anonymousLetter，求报纸内容是否可以拼成匿名信。

二、输入描述

第一行newspaper内容，包括1N个字符，并且空格分开

第二行anonymousLetter内容，包括1N个字符，并且空格分开。

newspaper和anonymousLetter的字符串中均为英文字母组成，且每个字母只能使用一次；

newspaper内容中的每个字符中字母顺序可以任意调整，但必须保证字符串的完整性（每个字符串不能有多余字母）

1 < N < 100，

1 <= newspaper.length，anonymousLetter.length <= 10⁴

三、输出描述

如果报纸可以拼成匿名信返回true，否则返回false

四、测试用例

测试用例1：

1、输入

ab cd
ab

2、输出

true

3、说明

测试用例2：

1、输入

ab ef
aef

2、输出

false

3、说明

五、解题思路

读取输入，包括报纸内容和匿名信内容。
将报纸和匿名信中的每个单词进行字母排序，得到其“规范形式”。
- 例如，单词“ab”排序后仍为“ab”，单词“aef”排序后为“aef”。
统计报纸中每种规范形式的单词出现次数，存入一个哈希映射 newspaperMap 中。
统计匿名信中每种规范形式的单词出现次数，存入另一个哈希映射 letterMap 中。
遍历匿名信中的每种规范形式，检查报纸中是否有足够数量的对应单词。
- 如果报纸中某种规范形式的单词数量少于匿名信中需要的数量，则返回 false。
如果所有匿名信中的单词都在报纸中有足够的对应单词，则返回 true。

六、Python算法源码

# 导入所需模块
import sysdef calculate_total_cost(newspaper_words, letter_words):"""计算报纸内容是否可以拼成匿名信:param newspaper_words: 报纸中的单词列表:param letter_words: 匿名信中的单词列表:return: 如果可以拼成匿名信返回True，否则返回False"""# 使用字典统计报纸中每种规范形式的单词出现次数newspaper_map = {}for word in newspaper_words:sorted_word = ''.join(sorted(word))  # 将单词字母排序if sorted_word in newspaper_map:newspaper_map[sorted_word] += 1else:newspaper_map[sorted_word] = 1# 使用字典统计匿名信中每种规范形式的单词出现次数letter_map = {}for word in letter_words:sorted_word = ''.join(sorted(word))  # 将单词字母排序if sorted_word in letter_map:letter_map[sorted_word] += 1else:letter_map[sorted_word] = 1# 检查报纸中是否有足够的单词来组成匿名信for sorted_word, required_count in letter_map.items():available_count = newspaper_map.get(sorted_word, 0)if available_count < required_count:return False  # 如果报纸中对应单词数量不足，返回Falsereturn True  # 所有单词数量足够，返回Truedef main():# 读取标准输入的所有行，并去除多余空格lines = sys.stdin.read().splitlines()lines = [line.strip() for line in lines if line.strip()]# 检查输入是否至少包含两行if len(lines) < 2:print("false")return# 读取报纸内容，并分割成单词列表newspaper_words = lines[0].split()# 读取匿名信内容，并分割成单词列表letter_words = lines[1].split()# 调用函数计算结果can_form = calculate_total_cost(newspaper_words, letter_words)# 输出结果print("true" if can_form else "false")if __name__ == "__main__":main()

七、JavaScript算法源码

// 导入所需模块
const readline = require('readline');// 创建接口以读取标准输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let inputLines = [];// 读取每一行输入
rl.on('line', (line) => {inputLines.push(line.trim());// 当读取了至少两行输入时，开始处理if (inputLines.length === 2) {rl.close();}
});// 输入读取完成后处理
rl.on('close', () => {// 读取报纸内容并分割成单词数组const newspaperWords = inputLines[0].split(/\s+/);// 读取匿名信内容并分割成单词数组const letterWords = inputLines[1].split(/\s+/);// 计算报纸是否可以拼成匿名信const canForm = calculateTotalCost(newspaperWords, letterWords);// 输出结果console.log(canForm ? "true" : "false");
});/*** 计算报纸内容是否可以拼成匿名信* @param {string[]} newspaperWords 报纸中的单词数组* @param {string[]} letterWords 匿名信中的单词数组* @returns {boolean} 如果可以拼成匿名信返回true，否则返回false*/
function calculateTotalCost(newspaperWords, letterWords) {// 使用对象统计报纸中每种规范形式的单词出现次数const newspaperMap = {};for (let word of newspaperWords) {const sortedWord = sortLetters(word); // 将单词字母排序if (newspaperMap.hasOwnProperty(sortedWord)) {newspaperMap[sortedWord] += 1;} else {newspaperMap[sortedWord] = 1;}}// 使用对象统计匿名信中每种规范形式的单词出现次数const letterMap = {};for (let word of letterWords) {const sortedWord = sortLetters(word); // 将单词字母排序if (letterMap.hasOwnProperty(sortedWord)) {letterMap[sortedWord] += 1;} else {letterMap[sortedWord] = 1;}}// 检查报纸中是否有足够的单词来组成匿名信for (let sortedWord in letterMap) {const requiredCount = letterMap[sortedWord];const availableCount = newspaperMap[sortedWord] || 0;if (availableCount < requiredCount) {return false; // 如果报纸中对应单词数量不足，返回false}}return true; // 所有单词数量足够，返回true
}/*** 将单词中的字母按字母序排序，并返回排序后的字符串* @param {string} word 原始单词* @returns {string} 排序后的单词*/
function sortLetters(word) {return word.split('').sort().join('');
}

八、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>// 定义最大单词数和最大单词长度
#define MAX_WORDS 10000
#define MAX_WORD_LENGTH 100// 比较函数，用于qsort
int cmp_char(const void *a, const void *b) {return (*(char*)a - *(char*)b);
}int main() {char newspaper_line[1000001]; // 假设每行最多100万字符char letter_line[1000001];// 读取报纸内容if (fgets(newspaper_line, sizeof(newspaper_line), stdin) == NULL) {printf("false\n");return 0;}// 读取匿名信内容if (fgets(letter_line, sizeof(letter_line), stdin) == NULL) {printf("false\n");return 0;}// 分割报纸内容成单词char *newspaper_words[MAX_WORDS];int newspaper_count = 0;char *token = strtok(newspaper_line, " \n");while (token != NULL && newspaper_count < MAX_WORDS) {newspaper_words[newspaper_count++] = token;token = strtok(NULL, " \n");}// 分割匿名信内容成单词char *letter_words[MAX_WORDS];int letter_count = 0;token = strtok(letter_line, " \n");while (token != NULL && letter_count < MAX_WORDS) {letter_words[letter_count++] = token;token = strtok(NULL, " \n");}// 使用哈希表模拟报纸中的单词频率// 由于C没有内置哈希表，这里使用排序和二分查找的方法// 首先，创建一个数组存储报纸中排序后的单词char **sorted_newspaper = (char**)malloc(newspaper_count * sizeof(char*));for (int i = 0; i < newspaper_count; i++) {int len = strlen(newspaper_words[i]);sorted_newspaper[i] = (char*)malloc((len + 1) * sizeof(char));strcpy(sorted_newspaper[i], newspaper_words[i]);qsort(sorted_newspaper[i], len, sizeof(char), cmp_char); // 排序字母}// 排序整个报纸单词数组// 使用指针数组排序for (int i = 0; i < newspaper_count - 1; i++) {for (int j = i + 1; j < newspaper_count; j++) {if (strcmp(sorted_newspaper[i], sorted_newspaper[j]) > 0) {char *temp = sorted_newspaper[i];sorted_newspaper[i] = sorted_newspaper[j];sorted_newspaper[j] = temp;}}}// 创建一个数组存储匿名信中排序后的单词char **sorted_letter = (char**)malloc(letter_count * sizeof(char*));for (int i = 0; i < letter_count; i++) {int len = strlen(letter_words[i]);sorted_letter[i] = (char*)malloc((len + 1) * sizeof(char));strcpy(sorted_letter[i], letter_words[i]);qsort(sorted_letter[i], len, sizeof(char), cmp_char); // 排序字母}// 排序匿名信中的单词for (int i = 0; i < letter_count - 1; i++) {for (int j = i + 1; j < letter_count; j++) {if (strcmp(sorted_letter[i], sorted_letter[j]) > 0) {char *temp = sorted_letter[i];sorted_letter[i] = sorted_letter[j];sorted_letter[j] = temp;}}}// 统计报纸中每种单词的频率// 使用两个数组存储唯一单词和对应频率char **unique_newspaper = (char**)malloc(newspaper_count * sizeof(char*));int *freq_newspaper = (int*)malloc(newspaper_count * sizeof(int));int unique_count = 0;for (int i = 0; i < newspaper_count; i++) {if (i == 0 || strcmp(sorted_newspaper[i], sorted_newspaper[i - 1]) != 0) {unique_newspaper[unique_count] = sorted_newspaper[i];freq_newspaper[unique_count] = 1;unique_count++;} else {freq_newspaper[unique_count - 1]++;}}// 统计匿名信中每种单词的频率char **unique_letter = (char**)malloc(letter_count * sizeof(char*));int *freq_letter = (int*)malloc(letter_count * sizeof(int));int unique_letter_count = 0;for (int i = 0; i < letter_count; i++) {if (i == 0 || strcmp(sorted_letter[i], sorted_letter[i - 1]) != 0) {unique_letter[unique_letter_count] = sorted_letter[i];freq_letter[unique_letter_count] = 1;unique_letter_count++;} else {freq_letter[unique_letter_count - 1]++;}}// 检查每个匿名信中的单词是否在报纸中有足够的数量int can_form = 1; // 默认可以for (int i = 0; i < unique_letter_count; i++) {// 使用二分查找在报纸中查找单词int left = 0;int right = unique_count - 1;int found = 0;while (left <= right) {int mid = left + (right - left) / 2;int cmp = strcmp(unique_letter[i], unique_newspaper[mid]);if (cmp == 0) {if (freq_newspaper[mid] < freq_letter[i]) {can_form = 0; // 不足}found = 1;break;} else if (cmp < 0) {right = mid - 1;} else {left = mid + 1;}}if (!found) {can_form = 0; // 未找到break;}if (can_form == 0) {break;}}// 输出结果if (can_form) {printf("true\n");} else {printf("false\n");}// 释放动态分配的内存for (int i = 0; i < newspaper_count; i++) {free(sorted_newspaper[i]);}free(sorted_newspaper);free(sorted_letter);free(unique_newspaper);free(freq_newspaper);free(unique_letter);free(freq_letter);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;/*** 将字符串中的字母按字母序排序，并返回排序后的字符串* @param word 原始字符串* @return 排序后的字符串*/
string sortLetters(const string &word) {string sorted = word;sort(sorted.begin(), sorted.end());return sorted;
}int main(){ios::sync_with_stdio(false);cin.tie(0);string newspaper_line;string letter_line;// 读取报纸内容if (!getline(cin, newspaper_line)) {cout << "false\n";return 0;}// 读取匿名信内容if (!getline(cin, letter_line)) {cout << "false\n";return 0;}// 分割报纸内容成单词vector<string> newspaper_words;string word;stringstream ss_newspaper(newspaper_line);while (ss_newspaper >> word) {newspaper_words.push_back(word);}// 分割匿名信内容成单词vector<string> letter_words;stringstream ss_letter(letter_line);while (ss_letter >> word) {letter_words.push_back(word);}// 使用unordered_map统计报纸中每种规范形式的单词出现次数unordered_map<string, int> newspaper_map;for (const auto &w : newspaper_words) {string sorted_word = sortLetters(w); // 将单词字母排序newspaper_map[sorted_word]++;}// 使用unordered_map统计匿名信中每种规范形式的单词出现次数unordered_map<string, int> letter_map;for (const auto &w : letter_words) {string sorted_word = sortLetters(w); // 将单词字母排序letter_map[sorted_word]++;}// 检查报纸中是否有足够的单词来组成匿名信bool can_form = true;for (const auto &entry : letter_map) {const string &sorted_word = entry.first;int required_count = entry.second;int available_count = newspaper_map[sorted_word];if (available_count < required_count) {can_form = false;break;}}// 输出结果cout << (can_form ? "true" : "false") << "\n";return 0;
}