重庆建设银行官方网站首页,自己的店铺如何弄小程序,企业网站建设及维护,我也要投放广告Leetcode819 最常见的单词
1.题目
给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多#xff0c;同时不在禁用列表中的单词。
题目保证至少有一个词不在禁用列表中#xff0c;而且答案唯一。
禁用列表中的单词用小写字母表示#xff0c;不含标点…Leetcode819 最常见的单词
1.题目
给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多同时不在禁用列表中的单词。
题目保证至少有一个词不在禁用列表中而且答案唯一。
禁用列表中的单词用小写字母表示不含标点符号。段落中的单词不区分大小写。答案都是小写字母。
2.解题思路
首先分析题目得出输入和输出输入一个字符串段落和一个字符串数组。输出字符串段落中出现次数最多 并且不在字符串数组里的单词字符串。从题目可知这是一道分析词频的题目。
因为要输出字符串段落中的单词字符串所以需要字符串拆分strtok
因为要采集字符串次数因此需要使用到字典dict和排序qsort
因为要确认每个拆分出来的字符串不属于banned列表中因此每次要进行比较strcmp
综上分析核心解法可以分成
step1. 拆分字符串strtok
step2. 遍历比较当前拆下来的字符串是否在banned中 strcmp
step3.1 若在banned中跳过处理。 step3.2 若不在banned中则遍历判断是否已经记录在字典中dict {word : count}
step4.2.1 若不在字典中则字典中新增一个{word, count1}
step4.2.2 若在字典中 则对应word的count 1
step5. 按照上述循环完成整个字符串段落的搜索
step6. 对字典的词频进行从大到小排序并取出词频最大值 count_max所对应的单词。也可以再遍历一遍字典筛选出最大值
再考虑预处理
pre1. 由于字符串分割时只能对特定某一种符号进行分割因此需要将标点符号全转化为空格符号。
pre2. 题目提到banned都是小写字符因此需要遍历一次数组将所有大写字母化为小写。
pre3. 题目已经定死段落长度为1000单词以内单词长度小于10对于C语言解题时可以直接写死数组长度。
3.数据结构与算法
数据结构字典
算法字符串拆分算法、排序算法
4.字符串拆分 定长字典排序
typedef struct {char val[11];int time;
} WordDict;int Cmp (const void* a, const void* b)
{return ((WordDict*)b)-time - ((WordDict*)a)-time;
}char * mostCommonWord(char * paragraph, char ** banned, int bannedSize) {int i;int j;int is_in_banned 0; // 是否在banned名单里int is_in_dict 0; // 是否已经存在dict里// 预处理while (paragraph[i] ! 0) {if (paragraph[i] A paragraph[i] Z) {// paragraph[i] (a - A);paragraph[i] tolower(paragraph[i]);}if ((paragraph[i] A || paragraph[i] Z) ((paragraph[i] a || paragraph[i] z))) {paragraph[i] ;}i;}// 创建词频字典 word,count// 因为不知道多少单词所以定位为段落的最大值。WordDict para_word_dict[1000];memset(para_word_dict, 0, sizeof(WordDict) * 1000);// 主功能提取字符串char* temp strtok(paragraph, );// 每次获得新单词时候int is_in_banned, is_in_dict标记清零while (temp ! NULL) {is_in_banned 0;is_in_word 0;// 判断是否在banned中for (i 0; i bannedSize; i) {if (strcmp(banned[i], temp) 0) {is_in_banned 1;break;}}// 若在banned中下面if不执行直接分割下个字符串// 若不在banned中判断是否在字典中。if (!is_in_banned) {j 0;is_in_word 0;// 判断是否在字典中-遍历有序字典到当前字典末端time 0 等价于 !valwhile (para_word_dict[j].time ! 0 j 1000) {if (strcmp(para_word_dict[j].val, temp) 0) {para_word_dict[j].time;is_in_word 1;break;}j;}// 不在则新增一个val,timeif (!is_in_word) {strcpy(para_word_dict[j].val, temp);para_word_dict[j].time;}}// 获取新字符串temp strtok(NULL, );}qsort(para_word_dict, 1000, sizeof(para_word_dict[0]), Cmp);// 输出char* res (char*)malloc(11);memset(res, 0, 11);strcpy(res, para_word_dict[0].val);return res;
}
