Leetcode819 最常見的單詞

1.題目

給定一個段落 (paragraph) 和一個禁用單詞列表 (banned)。返回出現(xiàn)次數(shù)最多，同時不在禁用列表中的單詞。

題目保證至少有一個詞不在禁用列表中，而且答案唯一。

禁用列表中的單詞用小寫字母表示，不含標(biāo)點(diǎn)符號。段落中的單詞不區(qū)分大小寫。答案都是小寫字母。

2.解題思路

首先分析題目，得出輸入和輸出：輸入一個字符串段落和一個字符串?dāng)?shù)組。輸出字符串段落中出現(xiàn)次數(shù)最多， 并且不在字符串?dāng)?shù)組里的單詞字符串。從題目可知這是一道分析詞頻的題目。

因為要輸出字符串段落中的單詞字符串，所以需要字符串拆分（strtok）

因為要采集字符串次數(shù)，因此需要使用到字典（dict）和排序（qsort）

因為要確認(rèn)每個拆分出來的字符串不屬于banned列表中，因此每次要進(jìn)行比較（strcmp）

綜上分析，核心解法可以分成：

step1. 拆分字符串（strtok）

step2. 遍歷比較當(dāng)前拆下來的字符串是否在banned中 （strcmp）

step3.1 若在banned中，跳過處理。 step3.2 若不在banned中，則遍歷判斷是否已經(jīng)記錄在字典中（dict = {word : count}）

step4.2.1 若不在字典中，則字典中新增一個（{word, count=1}）

step4.2.2 若在字典中， 則對應(yīng)word的count + 1

step5. 按照上述循環(huán)完成整個字符串段落的搜索

step6. 對字典的詞頻進(jìn)行從大到小排序，并取出詞頻最大值 count_max所對應(yīng)的單詞。（也可以再遍歷一遍字典，篩選出最大值）

再考慮預(yù)處理，

pre1. 由于字符串分割時，只能對特定某一種符號進(jìn)行分割，因此需要將標(biāo)點(diǎn)符號全轉(zhuǎn)化為空格符號。

pre2. 題目提到banned都是小寫字符，因此需要遍歷一次數(shù)組，將所有大寫字母化為小寫。

pre3. 題目已經(jīng)定死段落長度為1000單詞以內(nèi)，單詞長度小于10，對于C語言解題時，可以直接寫死數(shù)組長度。

3.數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)：字典

算法：字符串拆分算法、排序算法

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; // 是否已經(jīng)存在dict里// 預(yù)處理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++;}// 創(chuàng)建詞頻字典 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標(biāo)記清零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不執(zhí)行，直接分割下個字符串// 若不在banned中，判斷是否在字典中。if (!is_in_banned) {j = 0;is_in_word = 0;// 判斷是否在字典中->遍歷有序字典到當(dāng)前字典末端，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; }

總結(jié)

以上是生活随笔為你收集整理的【Leetcode819】最常见的单词的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。