文檔教程知識(shí)庫(kù)【免費(fèi)下載鏈接】InterviewGuide「InterviewGuide」是阿秀從校園-職場(chǎng)多年計(jì)算機(jī)自學(xué)過(guò)程的記錄以及學(xué)弟學(xué)妹們計(jì)算機(jī)校招秋招經(jīng)驗(yàn)總結(jié)文章的匯總包括但不限于C/C 、Golang、JavaScript、Vue、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)、MySQL、Redis等學(xué)習(xí)總結(jié)堅(jiān)持學(xué)習(xí)持續(xù)成長(zhǎng)項(xiàng)目地址https://gitcode.com/forthespada/InterviewGuide點(diǎn)擊查看免費(fèi)下載本篇是 InterviewGuide 倉(cāng)庫(kù)「精選力扣 300 題目之哈希表」Easy 分類(lèi)下第 884 題的完整題解。圍繞「不常見(jiàn)單詞」的定義本文會(huì)講清楚如何把計(jì)數(shù)問(wèn)題翻譯成哈希表統(tǒng)計(jì)詞頻給出倉(cāng)庫(kù)中原始記錄的手寫(xiě) C 解法并逐行剖析其切詞與邊界處理細(xì)節(jié)最后補(bǔ)充更簡(jiǎn)潔的istringstream寫(xiě)法并串聯(lián)哈希表分類(lèi)下的同類(lèi)題目供刷題時(shí)對(duì)照復(fù)習(xí)。讀完本文你將掌握「用unordered_map統(tǒng)計(jì)詞頻、再按頻次篩選」這一類(lèi)題目的標(biāo)準(zhǔn)套路以及面試手撕時(shí)需要注意的邊界條件。題目回顧什么是不常見(jiàn)單詞給定兩個(gè)句子 A 和 B句子是一串由空格分隔的單詞每個(gè)單詞僅由小寫(xiě)字母組成如果一個(gè)單詞在其中一個(gè)句子中只出現(xiàn)一次在另一個(gè)句子中卻沒(méi)有出現(xiàn)那么這個(gè)單詞就是不常見(jiàn)的要求返回所有不常見(jiàn)單詞的列表順序不限。原始題解記錄見(jiàn) 884.兩句話中的不常見(jiàn)單詞.md本文以此文檔為主體展開(kāi)。示例與約束示例 1輸入A this apple is sweetB this apple is sour輸出[sweet,sour]。其中this、apple、is都在兩句中重復(fù)出現(xiàn)而sweet只在 A 中、sour只在 B 中。示例 2輸入A apple appleB banana輸出[banana]。apple雖然在 A 中出現(xiàn)了兩次但既然它「出現(xiàn)不止一次」就不滿足「只出現(xiàn)一次」的條件因此不是不常見(jiàn)單詞。提示0 A.length 2000 B.length 200A 和 B 都只包含空格和小寫(xiě)字母。題目允許句子為空串長(zhǎng)度可為 0這是后面實(shí)現(xiàn)中必須處理好的邊界情況。解題思路把「不常見(jiàn)」翻譯成「全局詞頻 1」本題看似在說(shuō)「一個(gè)句子出現(xiàn)一次、另一個(gè)句子不出現(xiàn)」但如果把兩句話合并看待條件可以等價(jià)改寫(xiě)為一個(gè)單詞在 A、B 兩個(gè)句子合并后的總詞頻中恰好只出現(xiàn) 1 次。原因很簡(jiǎn)單若單詞只在一句話里出現(xiàn)一次另一句沒(méi)有 → 合并后總頻次為 1若單詞在兩句話里總共出現(xiàn) 2 次及以上無(wú)論是同一句內(nèi)重復(fù)還是跨句重復(fù)→ 不滿足「只出現(xiàn)一次」應(yīng)被排除示例 2 中apple apple里的apple總頻次為 2即使另一句沒(méi)有也不符合條件。因此解題分為兩步統(tǒng)計(jì)用一個(gè)哈希表C 的unordered_mapstring, int對(duì)兩個(gè)句子中的所有單詞分別計(jì)數(shù)篩選遍歷哈希表取出所有value 1的鍵即單詞本身放入結(jié)果數(shù)組返回。這一步的篩選是unordered_map最適合干的活——它以哈希方式組織鍵值插入和查詢(xún)都是平均 O(1) 的復(fù)雜度且遍歷時(shí)可以直接拿到「單詞 → 出現(xiàn)次數(shù)」的完整對(duì)應(yīng)關(guān)系。第一版實(shí)現(xiàn)倉(cāng)庫(kù)中記錄的手寫(xiě)切詞 unordered_map 統(tǒng)計(jì)原文檔給出的第一版解法完全沿用了上述思路且沒(méi)有借助split之類(lèi)的庫(kù)函數(shù)而是手動(dòng)按空格切詞代碼如下vectorstring uncommonFromSentences(string A, string B) { unordered_mapstring,int un_mp; string temp; for (unsigned i0;iA.size();i) { temp ; while (A[i] ! i A.size()) { temp A[i]; } if (temp.size() 0) un_mp[temp]; } for (unsigned i 0; i B.size(); i) { temp ; while (B[i] ! i B.size()) { temp B[i]; } if (temp.size() 0) un_mp[temp]; } vectorstring res; for (auto a : un_mp) { if (a.second 1) res.push_back(a.first); //cout a.first a.second endl; } return res; }原文檔記錄了該版本提交時(shí)的表現(xiàn)歷史提交數(shù)據(jù)來(lái)自 LeetCode 中文站執(zhí)行用時(shí)4 ms擊敗約 91.83% 的 cpp 提交內(nèi)存消耗8.7 MB擊敗約 100.00% 的提交。這段代碼雖然「土」但在面試手撕場(chǎng)景下非常直觀兩次遍歷分詞、一次遍歷篩詞全程只用到一個(gè)unordered_mapstring, int空間占用只有「不同單詞的個(gè)數(shù)」。逐行拆解手寫(xiě)切詞的細(xì)節(jié)核心的切詞循環(huán)是while (A[i] ! i A.size()) { temp A[i]; }這里有兩個(gè)容易被忽略的細(xì)節(jié)循環(huán)條件的先后順序先判斷A[i] ! 再判斷i A.size()。當(dāng)i已經(jīng)等于size()即掃描到字符串末尾之后時(shí)C 標(biāo)準(zhǔn)保證string::operator[]在i size()位置返回一個(gè)指向空字符\0的引用\0 ! 為真緊接著i A.size()為假循環(huán)安全退出不會(huì)越界訪問(wèn)。也就是說(shuō)這種寫(xiě)法依賴(lài)「\0不等于空格」這一事實(shí)來(lái)兜底收尾。跳過(guò)空串if (temp.size() 0) un_mp[temp];保證即使句子中出現(xiàn)連續(xù)空格雖然題目約束下不會(huì)出現(xiàn)也不會(huì)把空串計(jì)入統(tǒng)計(jì)。同時(shí)在循環(huán)外層for的末尾i已經(jīng)指向空格位置下一輪外層循環(huán)會(huì)i跳過(guò)該空格再進(jìn)入下一輪切詞。對(duì) B 的第二次遍歷與 A 完全對(duì)稱(chēng)。最終遍歷哈希表時(shí)a.first是單詞、a.second是出現(xiàn)次數(shù)只收集a.second 1的單詞即可。由于unordered_map本身無(wú)序返回結(jié)果天然滿足題目「可以按任何順序返回列表」的要求。復(fù)雜度分析時(shí)間復(fù)雜度O(n)其中 n 為兩個(gè)句子字符總長(zhǎng)度。兩輪分詞各自線性掃描一遍句子最后一輪遍歷哈希表也只需 O(k)k 為不同單詞數(shù)總體為線性時(shí)間?？臻g復(fù)雜度O(k)k 為 A 和 B 中出現(xiàn)的不同單詞總數(shù)哈希表只存儲(chǔ)不重復(fù)的鍵值對(duì)。進(jìn)階寫(xiě)法用 istringstream 簡(jiǎn)化分詞手寫(xiě)切詞能幫助我們理解指針/下標(biāo)推進(jìn)的細(xì)節(jié)但生產(chǎn)級(jí)代碼通常直接交給std::istringstream來(lái)做「按空格分詞」代碼更短、更不易出錯(cuò)#include sstream vectorstring uncommonFromSentences(string A, string B) { unordered_mapstring, int un_mp; istringstream iss(A B); // 合并兩句話統(tǒng)一分詞統(tǒng)計(jì) string word; while (iss word) { un_mp[word]; } vectorstring res; for (auto it : un_mp) { if (it.second 1) res.push_back(it.first); } return res; }這里的改進(jìn)點(diǎn)在于用A B把兩句話拼成一句中間補(bǔ)一個(gè)空格之后一次while (iss word)就能把兩個(gè)句子的所有單詞全部喂進(jìn)同一個(gè)哈希表免去了對(duì) A、B 各寫(xiě)一遍的重復(fù)代碼operator天然按空白符含空格切分且會(huì)自動(dòng)跳過(guò)空串與第一版里temp.size() 0的判斷效果一致統(tǒng)計(jì)與篩選兩個(gè)階段的結(jié)構(gòu)保持不變邏輯與第一版完全等價(jià)只是實(shí)現(xiàn)更簡(jiǎn)潔。面試延伸哈希表分類(lèi)下的同類(lèi)題目串聯(lián)「統(tǒng)計(jì)詞頻 → 按條件篩選」是哈希表分類(lèi)下的高頻套路本倉(cāng)庫(kù)哈希表模塊中還收錄了多道可對(duì)照練習(xí)的題目題目核心考點(diǎn)倉(cāng)庫(kù)路徑387. 字符串中的第一個(gè)唯一字符用哈希表統(tǒng)計(jì)字符頻次再按字符串順序找第一個(gè)頻次為 1 的字符easy/387.字符串中的第一個(gè)唯一字符.md1207. 獨(dú)一無(wú)二的出現(xiàn)次數(shù)哈希表統(tǒng)計(jì)頻次后再用unordered_set判斷頻次是否互不相同easy/1207.獨(dú)一無(wú)二的出現(xiàn)次數(shù).md290. 單詞規(guī)律用兩張哈希表建立字符?單詞的雙向映射easy/290.單詞規(guī)律.md205. 同構(gòu)字符串字符之間雙向映射判斷是否一一對(duì)應(yīng)easy/205.同構(gòu)字符串.md970. 強(qiáng)整數(shù)用unordered_set完成去重再轉(zhuǎn)成vector返回easy/970.強(qiáng)整數(shù).md尤其值得對(duì)比的是 1207 題與本題1207 統(tǒng)計(jì)的是數(shù)字的出現(xiàn)次數(shù)再用unordered_set判重返回un_st.size() un_mp.size()本題統(tǒng)計(jì)的是單詞的出現(xiàn)次數(shù)再按value 1篩選。兩者共用同一套「哈希表計(jì)數(shù)」骨架只是篩選條件不同。刷題時(shí)可以把它們放在一起對(duì)照強(qiáng)化「統(tǒng)計(jì) → 篩選」兩步走的心智模型。小結(jié)不常見(jiàn)單詞 合并后全局詞頻恰好為 1 的單詞這是把題意轉(zhuǎn)化為哈希表問(wèn)題的關(guān)鍵一步實(shí)現(xiàn)上「手寫(xiě)切詞 unordered_mapstring, int」與「istringstream分詞」兩種寫(xiě)法等價(jià)前者適合理解邊界細(xì)節(jié)后者適合快速寫(xiě)出干凈代碼注意兩個(gè)邊界句子可能為空串長(zhǎng)度 0以及切詞循環(huán)中\(zhòng)0 ! 對(duì)越界收尾的兜底本題位于哈希表分類(lèi)的 Easy 檔與之相鄰的 387、1207、290、205、970 等題目均可在 05-哈希表 目錄下找到完整題解是面試前復(fù)習(xí)哈希表套路的高性?xún)r(jià)比組合。贊分享文檔教程知識(shí)庫(kù)【免費(fèi)下載鏈接】InterviewGuide「InterviewGuide」是阿秀從校園-職場(chǎng)多年計(jì)算機(jī)自學(xué)過(guò)程的記錄以及學(xué)弟學(xué)妹們計(jì)算機(jī)校招秋招經(jīng)驗(yàn)總結(jié)文章的匯總包括但不限于C/C 、Golang、JavaScript、Vue、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)、MySQL、Redis等學(xué)習(xí)總結(jié)堅(jiān)持學(xué)習(xí)持續(xù)成長(zhǎng)項(xiàng)目地址https://gitcode.com/forthespada/InterviewGuide點(diǎn)擊查看免費(fèi)下載相關(guān)推薦LogicStack-LeetCode 題解884. 兩句話中的不常見(jiàn)單詞哈希表 模擬LogicStack LeetCode 題解884. 兩句話中的不常見(jiàn)單詞哈希表 模擬 本文以 LogicStack LeetCode 倉(cāng)庫(kù)中 884教程文檔兩句話中的不常見(jiàn)單詞NeetCode 哈希表計(jì)數(shù)解法全解析兩句話中的不常見(jiàn)單詞NeetCode 哈希表計(jì)數(shù)解法全解析 本篇技術(shù)指南聚焦 LeetCode 經(jīng)典題目「Uncommon Words from Two Se示例工程教程AlgoNote 題解0884. 兩句話中的不常見(jiàn)單詞——用哈希表統(tǒng)計(jì)詞頻的字符串計(jì)數(shù)實(shí)戰(zhàn)AlgoNote 題解0884. 兩句話中的不常見(jiàn)單詞——用哈希表統(tǒng)計(jì)詞頻的字符串計(jì)數(shù)實(shí)戰(zhàn) 本篇是「算法通關(guān)手冊(cè)」AlgoNote LeetCode 題解教程文檔知識(shí)庫(kù)上一篇如何在離線環(huán)境下使用Osintgram進(jìn)行Instagram數(shù)據(jù)分析完整指南下一篇stdexec性能優(yōu)化從入門(mén)到專(zhuān)家的完整調(diào)優(yōu)指南創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考