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