1. 項(xiàng)目背景與核心價(jià)值為什么“熱門話題”值得深究最近在輔導(dǎo)一些同學(xué)準(zhǔn)備PATProgramming Ability Test或者類似的數(shù)據(jù)結(jié)構(gòu)算法考試時(shí)發(fā)現(xiàn)“新浪微博熱門話題”這道題的出現(xiàn)頻率相當(dāng)高而且大家的錯(cuò)誤率也不低。這道題乍一看就是一個(gè)字符串處理加統(tǒng)計(jì)排序的問(wèn)題似乎沒(méi)什么難度。但真正上手去寫才會(huì)發(fā)現(xiàn)里面布滿了“坑點(diǎn)”從輸入格式的詭異到字符串處理的繁瑣再到排序規(guī)則的細(xì)節(jié)每一步都可能讓你丟分。網(wǎng)上的很多題解要么過(guò)于簡(jiǎn)略只給個(gè)核心思路要么代碼冗長(zhǎng)關(guān)鍵邏輯淹沒(méi)在細(xì)節(jié)里讓人看了還是一頭霧水。所以我決定結(jié)合自己多次調(diào)試和教學(xué)的經(jīng)驗(yàn)寫一份超詳細(xì)的題解。這份題解的目的不僅僅是告訴你ACAccepted的代碼怎么寫更重要的是我會(huì)帶你完整地走一遍解題的思考過(guò)程題目到底在考什么常見(jiàn)的陷阱在哪里為什么你的代碼會(huì)在這里出錯(cuò)以及如何寫出既清晰又高效的代碼。此外我還會(huì)提供一些額外的測(cè)試樣例這些樣例很多是官方樣例沒(méi)有覆蓋到的邊界情況和易錯(cuò)點(diǎn)能幫你更全面地檢驗(yàn)自己的程序。無(wú)論你是正在備戰(zhàn)PAT、CCF-CSP考試還是單純想提升自己的字符串處理和模擬能力相信這篇從實(shí)戰(zhàn)中總結(jié)出來(lái)的經(jīng)驗(yàn)都能給你帶來(lái)實(shí)實(shí)在在的幫助。我們不止要“做對(duì)”更要“理解為什么這樣是對(duì)的”。2. 題目深度剖析隱藏在字里行間的“考點(diǎn)地圖”在動(dòng)手寫代碼之前我們必須像偵探一樣把題目的每一個(gè)要求都拆解清楚。很多同學(xué)失分不是因?yàn)樗惴ú粫?huì)而是因?yàn)闆](méi)完全讀懂題。2.1 核心任務(wù)拆解題目要求我們統(tǒng)計(jì)N條微博中所有被“#”包圍的話題即話題標(biāo)簽并找出出現(xiàn)次數(shù)最多的那個(gè)。如果出現(xiàn)并列則按字典序升序輸出最小的那個(gè)。聽起來(lái)很簡(jiǎn)單對(duì)吧但魔鬼藏在細(xì)節(jié)里。首先話題的提取與歸一化是第一個(gè)難點(diǎn)。題目明確要求話題標(biāo)簽以#開頭和結(jié)尾且#與話題內(nèi)容之間沒(méi)有空格。同一話題經(jīng)過(guò)“歸一化”后視為相同。歸一化規(guī)則是忽略所有的英文字母大小寫。例如#Hello和#HELLO是同一個(gè)話題。忽略話題開頭、結(jié)尾和中間多余的空白符包括空格、制表符等。但單詞間的單個(gè)空格需要保留。話題本身可能包含#、!、?等標(biāo)點(diǎn)這些標(biāo)點(diǎn)需要被保留。這是很多人的思維盲區(qū)。2.2 易錯(cuò)點(diǎn)預(yù)警踩坑重災(zāi)區(qū)這里我結(jié)合批改過(guò)的上百份代碼總結(jié)出幾個(gè)最高頻的失分點(diǎn)嵌套“#”的處理比如#Hello#World#這算一個(gè)話題Hello#World還是兩個(gè)話題Hello和World根據(jù)規(guī)則#必須成對(duì)出現(xiàn)作為邊界。所以#Hello#World#會(huì)被解析為#Hello#和#World#兩個(gè)獨(dú)立的話題。你的代碼必須能正確識(shí)別話題的邊界而不是簡(jiǎn)單地按字符分割。歸一化邏輯的完整性很多同學(xué)只做了轉(zhuǎn)小寫和去除首尾空格卻忽略了“將連續(xù)的空格包括制表符等替換為單個(gè)空格”這一步。例如# a b c #歸一化后應(yīng)該是a b c中間的多個(gè)空格要合并成一個(gè)。這需要你在去除首尾空白后再對(duì)中間部分進(jìn)行一次空白符的掃描與合并。標(biāo)點(diǎn)符號(hào)的保留這是最容易被忽略的題目說(shuō)“除了英文字母大小寫和多余空格外其他字符原樣保留”。這意味著#Hello! World?#歸一化后是Hello! World?其中的!和?必須保留。如果你在歸一化過(guò)程中不小心過(guò)濾掉了非字母數(shù)字字符那就錯(cuò)了。統(tǒng)計(jì)與排序的細(xì)節(jié)統(tǒng)計(jì)次數(shù)時(shí)鍵Key必須是歸一化后的話題字符串。排序時(shí)第一關(guān)鍵字是出現(xiàn)次數(shù)降序第二關(guān)鍵字是話題字符串本身字典序升序。注意字典序升序意味著abc排在abd前面。在C中string默認(rèn)的比較運(yùn)算符就是字典序升序。把這些考點(diǎn)和陷阱在心里畫成一張地圖我們寫代碼時(shí)才能有的放矢避免低級(jí)錯(cuò)誤。3. 核心算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)選型明確了要求接下來(lái)就要選擇用什么樣的“武器”來(lái)解決它。這道題的核心是“統(tǒng)計(jì)”和“排序”自然想到使用哈希表散列表來(lái)計(jì)數(shù)然后用一個(gè)有序結(jié)構(gòu)來(lái)輸出結(jié)果。3.1 數(shù)據(jù)結(jié)構(gòu)為什么用map或unordered_mapvector計(jì)數(shù)階段我們需要一個(gè)能從“歸一化后的話題字符串”快速映射到“出現(xiàn)次數(shù)”的結(jié)構(gòu)。C中的std::unordered_map平均O(1)的查找和插入效率是最優(yōu)選擇。std::map也可以但它是基于紅黑樹的有序映射O(log n)的效率在此題數(shù)據(jù)規(guī)模下也完全足夠且代碼更通用。我個(gè)人的習(xí)慣是除非性能瓶頸非常明確否則優(yōu)先用map因?yàn)樗鼙ＷC遍歷時(shí)按key有序雖然本題不依賴這個(gè)特性。排序輸出階段我們需要按次數(shù)降序 話題升序的規(guī)則輸出。哈希表本身是無(wú)序的所以我們需要把其中的鍵值對(duì)pair提取出來(lái)放到一個(gè)線性容器如vector中然后使用std::sort配合自定義比較函數(shù)進(jìn)行排序。3.2 算法流程的偽代碼描述讓我們把思路整理成清晰的步驟1. 初始化一個(gè)空的 mapstring, int topicCount用于統(tǒng)計(jì)話題出現(xiàn)次數(shù)。 2. 循環(huán)讀取 N 行微博內(nèi)容 a. 定義一個(gè)字符串變量 line讀取一整行。 b. 調(diào)用函數(shù) extractAndNormalizeTopics(line, topicCount)處理該行。 3. 定義 extractAndNormalizeTopics 函數(shù) a. 遍歷字符串 line 的每個(gè)字符尋找 #。 b. 找到起始 # 后記錄其位置 start。 c. 繼續(xù)向后尋找配對(duì)的結(jié)束 #記錄位置 end。如果找不到則當(dāng)前起始 # 無(wú)效繼續(xù)向后搜索。 d. 截取 start1 到 end-1 的子串這就是原始話題內(nèi)容 rawTopic。 e. 調(diào)用 normalizeTopic(rawTopic) 函數(shù)對(duì) rawTopic 進(jìn)行歸一化得到 stdTopic。 f. 如果 stdTopic 不為空注意歸一化后可能變成空字符串如 ##則 topicCount[stdTopic]。 g. 從 end 位置之后繼續(xù)搜索下一個(gè)話題。 4. 定義 normalizeTopic 函數(shù) a. 去除 rawTopic 首尾的空白字符包括空格、\t、\n等。 b. 創(chuàng)建一個(gè)結(jié)果字符串 result。 c. 遍歷去除首尾空白后的字符串 i. 將當(dāng)前字符轉(zhuǎn)換為小寫如果是字母。 ii. 如果當(dāng)前字符是空白類字符 * 如果 result 不為空且 result 的最后一個(gè)字符不是空格則向 result 追加一個(gè)空格實(shí)現(xiàn)連續(xù)空格合并。 * 否則跳過(guò)該空白字符。 iii. 否則當(dāng)前字符不是空白直接將該字符已轉(zhuǎn)小寫追加到 result。 d. 返回 result。 5. 統(tǒng)計(jì)完成后將 topicCount 中的所有鍵值對(duì)存入一個(gè) vectorpairstring, int 中。 6. 使用 sort 函數(shù)對(duì)該 vector 排序自定義比較規(guī)則先按 int次數(shù)降序次數(shù)相同則按 string話題升序。 7. 輸出結(jié)果 a. 輸出排序后第一個(gè)元素的話題內(nèi)容。 b. 輸出該話題出現(xiàn)的次數(shù)。 c. 如果該次數(shù)為1或者 topicCount 為空則需要在第二行輸出 “No one is trending!” 嗎**不仔細(xì)看題題目只要求輸出熱門話題和其次數(shù)并沒(méi)有這個(gè)要求。這是一個(gè)常見(jiàn)的理解偏差。** 我們只輸出統(tǒng)計(jì)出的結(jié)果即可。這個(gè)設(shè)計(jì)清晰地分離了輸入解析、話題提取、字符串歸一化、統(tǒng)計(jì)計(jì)數(shù)和結(jié)果排序這幾個(gè)模塊邏輯清晰便于調(diào)試和修改。4. 關(guān)鍵代碼實(shí)現(xiàn)與逐行解析理論說(shuō)得再多不如一行代碼來(lái)得實(shí)在。下面我將用C實(shí)現(xiàn)并加上詳細(xì)注釋解釋每一處關(guān)鍵代碼的意圖和注意事項(xiàng)。#include iostream #include string #include map #include vector #include algorithm #include cctype // 用于 isspace, tolower using namespace std; // 關(guān)鍵函數(shù)1字符串歸一化 string normalizeTopic(const string raw) { if (raw.empty()) return ; // 1. 去除首尾空白 size_t start 0, end raw.size() - 1; while (start end isspace(raw[start])) start; while (end start isspace(raw[end])) end--; // 如果全是空白則歸一化后為空串 if (start end) return ; string result; bool lastIsSpace false; // 標(biāo)記上一個(gè)字符是否是已處理的空格 // 2. 遍歷有效部分處理中間字符 for (size_t i start; i end; i) { char c raw[i]; if (isspace(c)) { // 當(dāng)前是空白符 if (!result.empty() !lastIsSpace) { result.push_back( ); // 遇到空白且上一個(gè)字符不是空格則添加一個(gè)空格 lastIsSpace true; } // 如果是連續(xù)空格或者結(jié)果串還是空的就跳過(guò)這個(gè)空白符 } else { // 當(dāng)前是非空白字符 if (isalpha(c)) { result.push_back(tolower(c)); // 字母轉(zhuǎn)小寫 } else { result.push_back(c); // 非字母字符標(biāo)點(diǎn)等原樣保留 } lastIsSpace false; } } // 3. 處理一種特殊情況如果結(jié)果以空格結(jié)尾理論上不會(huì)因?yàn)槟┪部瞻滓讶コ虚g處理邏輯可能遺留 // 我們的邏輯保證了不會(huì)因?yàn)橹挥杏龅椒强瞻鬃址艜?huì)關(guān)閉“空格添加”狀態(tài)。但為安全起見(jiàn)可以檢查。 // if (!result.empty() isspace(result.back())) result.pop_back(); // 實(shí)際上上面的邏輯已經(jīng)能保證這里為了清晰可以加上。 return result; } // 關(guān)鍵函數(shù)2從一行文本中提取并統(tǒng)計(jì)話題 void extractTopics(const string line, mapstring, int countMap) { size_t len line.size(); for (size_t i 0; i len; i) { if (line[i] #) { // 找到起始# size_t j i 1; // 尋找結(jié)束的#注意結(jié)束#必須與起始#成對(duì)且中間可以有任意字符 while (j len line[j] ! #) { j; } if (j len) { // 找到了結(jié)束的# // 提取#之間的內(nèi)容注意子串區(qū)間是[i1, j-1] string rawTopic line.substr(i 1, j - i - 1); string stdTopic normalizeTopic(rawTopic); if (!stdTopic.empty()) { // 歸一化后非空才計(jì)數(shù) countMap[stdTopic]; } i j; // 更新索引到結(jié)束#的位置循環(huán)的會(huì)使其指向下一個(gè)字符 } else { // 沒(méi)有找到結(jié)束#說(shuō)明這個(gè)起始#是無(wú)效的跳出內(nèi)層循環(huán)繼續(xù)外層循環(huán)掃描 // 實(shí)際上因?yàn)闆](méi)找到i不會(huì)更新外層循環(huán)的會(huì)使其繼續(xù)后移。這里直接break內(nèi)層查找循環(huán)即可。 // 更準(zhǔn)確地說(shuō)沒(méi)找到配對(duì)的#這個(gè)起始#無(wú)效我們什么也不做讓i繼續(xù)掃描下一個(gè)字符。 // 所以這里不需要特殊處理讓循環(huán)繼續(xù)即可。但為了邏輯清晰可以注釋說(shuō)明。 // 當(dāng)前實(shí)現(xiàn)中如果沒(méi)找到配對(duì)#j會(huì)等于len不會(huì)進(jìn)入if(jlen)分支也不會(huì)更新i循環(huán)正常繼續(xù)。 } } } } // 關(guān)鍵函數(shù)3自定義排序比較函數(shù) bool cmp(const pairstring, int a, const pairstring, int b) { if (a.second ! b.second) { return a.second b.second; // 次數(shù)降序 } else { return a.first b.first; // 話題字典序升序 } } int main() { int N; cin N; cin.ignore(); // 非常重要清除輸入N后緩沖區(qū)殘留的換行符否則后面的getline會(huì)直接讀到空行。 mapstring, int topicCount; for (int i 0; i N; i) { string line; getline(cin, line); // 讀取整行微博內(nèi)容 extractTopics(line, topicCount); } if (topicCount.empty()) { // 理論上如果一條有效話題都沒(méi)有map為空。但題目似乎保證至少有一個(gè)有效話題 // 為代碼健壯性考慮可以處理。 cout No one is trending! endl; // 注意原題輸出要求可能沒(méi)有這一句這里僅為演示健壯性處理。 return 0; } // 將map中的數(shù)據(jù)轉(zhuǎn)存到vector以便排序 vectorpairstring, int vec(topicCount.begin(), topicCount.end()); sort(vec.begin(), vec.end(), cmp); // 輸出結(jié)果 cout vec[0].first endl; cout vec[0].second endl; // 附加如果第一名有并列題目要求只輸出字典序最小的我們已經(jīng)通過(guò)排序保證了vec[0]就是。 // 如果想看看所有并列的調(diào)試用可以這樣 // cout All top topics: endl; // for (const auto p : vec) { // if (p.second vec[0].second) { // cout p.first : p.second endl; // } else { // break; // } // } return 0; }代碼要點(diǎn)解析cin.ignore()這是新手必踩的坑。在cin N之后輸入緩沖區(qū)里還留有一個(gè)換行符\n。如果不把它消耗掉接下來(lái)的getline(cin, line)會(huì)立刻讀到這個(gè)空行導(dǎo)致第一條微博內(nèi)容讀取錯(cuò)誤。加上cin.ignore()就能清空緩沖區(qū)直到下一個(gè)換行符。normalizeTopic中的lastIsSpace標(biāo)志這是實(shí)現(xiàn)“合并連續(xù)空格”的精髓。它記錄結(jié)果字符串result的上一個(gè)字符是否是空格。只有當(dāng)遇到空白符且上一個(gè)字符不是空格時(shí)我們才添加一個(gè)空格。這樣就完美避免了多個(gè)連續(xù)空格也防止了在開頭添加空格。extractTopics中的索引更新i j當(dāng)我們成功提取一個(gè)話題#...#后起始位置是i結(jié)束位置是j。下一次搜索應(yīng)該從j之后開始。i j將索引定位到結(jié)束的#for循環(huán)的i會(huì)使其指向下一個(gè)字符從而避免了重復(fù)處理或死循環(huán)。排序比較函數(shù)cmp注意a.second b.second是降序次數(shù)多的排前面。a.first b.first是升序字典序小的排前面。當(dāng)?shù)谝魂P(guān)鍵字相同時(shí)sort會(huì)使用第二關(guān)鍵字進(jìn)行比較。5. 額外測(cè)試樣例與針對(duì)性調(diào)試官方樣例往往只覆蓋常規(guī)情況。要想代碼真正健壯必須自己設(shè)計(jì)一些“刁鉆”的測(cè)試數(shù)據(jù)。下面我提供幾組并解釋它們主要測(cè)試什么。樣例1基礎(chǔ)與大小寫合并輸入 3 I love #Coding#! Do you like #CODING#? #CoDinG# is fun. 輸出 coding 3測(cè)試點(diǎn)驗(yàn)證大小寫歸一化是否有效。三個(gè)不同大小寫形式的#Coding#應(yīng)被合并。樣例2空格處理首尾、中間連續(xù)輸入 2 This is a # Hello World # topic. And this: # hello world # again. 輸出 hello world 2測(cè)試點(diǎn)驗(yàn)證首尾空格去除以及中間多個(gè)空格包括制表符這里用空格表示合并為一個(gè)空格的功能。樣例3包含標(biāo)點(diǎn)符號(hào)輸入 1 Whats this? #Hello! How are you?# #Good, thanks!# 輸出 hello! how are you? 1測(cè)試點(diǎn)驗(yàn)證非字母字符!,?,,是否被正確保留。注意這里有兩個(gè)話題但第一個(gè)和第二個(gè)不同所以各自計(jì)數(shù)為1。輸出第一個(gè)按字典序“hello! how are you?” 比 “good, thanks!” 小實(shí)際上比較的是整個(gè)字符串的ASCII碼g(103) 比h(104) 小所以good, thanks!字典序更小。但這里次數(shù)都是1所以按字典序輸出最小的應(yīng)該是good, thanks!。讓我們仔細(xì)分析兩個(gè)話題次數(shù)相同字典序比較good, thanks!和hello! how are you?。 第一個(gè)字符g(103) vsh(104)g更小所以good, thanks!是第一名。 因此這個(gè)樣例的正確輸出應(yīng)該是good, thanks! 1這個(gè)樣例非常好它同時(shí)測(cè)試了標(biāo)點(diǎn)保留和排序規(guī)則。樣例4嵌套與無(wú)效#號(hào)輸入 1 Test #Outer#Inner# and #NotClosed and ## and #Valid# 輸出 valid 1測(cè)試點(diǎn)#Outer#Inner#被解析為#Outer#和#Inner#兩個(gè)獨(dú)立話題。但outer和inner并未在別處出現(xiàn)所以各計(jì)1次。#NotClosed沒(méi)有結(jié)束的#無(wú)效忽略。##兩個(gè)#緊挨著中間內(nèi)容為空歸一化后為空字符串忽略。#Valid#有效話題valid。 最終outer,inner,valid各出現(xiàn)1次。按字典序升序inner(105) outer(111) valid(118)所以輸出inner和1。等等這里inner的字典序確實(shí)最小。所以這個(gè)樣例的正確輸出是inner 1這個(gè)樣例極其重要它綜合測(cè)試了話題邊界識(shí)別、空話題過(guò)濾和最終排序。樣例5極端情況——超長(zhǎng)輸入和純符號(hào)話題輸入 1 # # ##$% # #A # # a # # (這是一個(gè)很長(zhǎng)的話題包含各種字符) # #測(cè)試點(diǎn)測(cè)試程序的魯棒性。需要正確處理那些歸一化后可能變?yōu)榭沾脑掝}如# #以及包含各種標(biāo)點(diǎn)的話題。建議你在本地編寫代碼時(shí)把這些樣例都跑一遍并用調(diào)試器或打印中間變量的方式仔細(xì)觀察每個(gè)階段字符串的變化確保你的程序邏輯與預(yù)期完全一致。尤其是樣例3和樣例4它們的結(jié)果可能和第一直覺(jué)不同正是區(qū)分代碼正確與否的關(guān)鍵。