建筑公司网站大全,wordpress 新年插件,网站设计报价是多少,东营科技官方网站华为OD机试 2024E卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试真题#xff08;Python/JS/C/C#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;私信哪吒#xff0c;备注华为OD#xff0c;加入华为OD刷题交流群#xff0c;… 华为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.lengthanonymousLetter.length 104
三、输出描述
如果报纸可以拼成匿名信返回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;}// 分割报纸内容成单词vectorstring newspaper_words;string word;stringstream ss_newspaper(newspaper_line);while (ss_newspaper word) {newspaper_words.push_back(word);}// 分割匿名信内容成单词vectorstring letter_words;stringstream ss_letter(letter_line);while (ss_letter word) {letter_words.push_back(word);}// 使用unordered_map统计报纸中每种规范形式的单词出现次数unordered_mapstring, int newspaper_map;for (const auto w : newspaper_words) {string sorted_word sortLetters(w); // 将单词字母排序newspaper_map[sorted_word];}// 使用unordered_map统计匿名信中每种规范形式的单词出现次数unordered_mapstring, 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;
} 下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 2024 E卷 200分
本文收录于华为OD机试真题Python/JS/C/C
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。
