C++實(shí)現(xiàn)LeetCode(49.群組錯(cuò)位詞)
[LeetCode] 49. Group Anagrams 群組錯(cuò)位詞
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
這道題讓我們?nèi)航M給定字符串集中所有的錯(cuò)位詞,所謂的錯(cuò)位詞就是兩個(gè)字符串中字母出現(xiàn)的次數(shù)都一樣,只是位置不同,比如 abc,bac, cba 等它們就互為錯(cuò)位詞,那么如何判斷兩者是否是錯(cuò)位詞呢,可以發(fā)現(xiàn)如果把錯(cuò)位詞的字符順序重新排列,那么會(huì)得到相同的結(jié)果,所以重新排序是判斷是否互為錯(cuò)位詞的方法,由于錯(cuò)位詞重新排序后都會(huì)得到相同的字符串,以此作為 key,將所有錯(cuò)位詞都保存到字符串?dāng)?shù)組中,建立 key 和當(dāng)前的不同的錯(cuò)位詞集合個(gè)數(shù)之間的映射,這里之所以沒有建立 key 和其隸屬的錯(cuò)位詞集合之間的映射,是用了一個(gè)小 trick,從而避免了最后再將 HashMap 中的集合拷貝到結(jié)果 res 中。當(dāng)檢測到當(dāng)前的單詞不在 HashMap 中,此時(shí)知道這個(gè)單詞將屬于一個(gè)新的錯(cuò)位詞集合,所以將其映射為當(dāng)前的錯(cuò)位詞集合的個(gè)數(shù),然后在 res 中新增一個(gè)空集合,這樣就可以通過其映射值,直接找到新的錯(cuò)位詞集合的位置,從而將新的單詞存入結(jié)果 res 中,參見代碼如下:
解法一:
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string, int> m; for (string str : strs) { string t = str; sort(t.begin(), t.end()); if (!m.count(t)) { m[t] = res.size(); res.push_back({}); } res[m[t]].push_back(str); } return res; } };
下面這種解法沒有用到排序,用一個(gè)大小為 26 的 int 數(shù)組來統(tǒng)計(jì)每個(gè)單詞中字符出現(xiàn)的次數(shù),然后將 int 數(shù)組轉(zhuǎn)為一個(gè)唯一的字符串,跟字符串?dāng)?shù)組進(jìn)行映射,這樣就不用給字符串排序了,參見代碼如下:
解法二:
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string, vector<string>> m; for (string str : strs) { vector<int> cnt(26); string t; for (char c : str) ++cnt[c - 'a']; for (int i = 0; i < 26; ++i) { if (cnt[i] == 0) continue; t += string(1, i + 'a') + to_string(cnt[i]); } m[t].push_back(str); } for (auto a : m) { res.push_back(a.second); } return res; } };
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(49.群組錯(cuò)位詞)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)群組錯(cuò)位詞內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(58.求末尾單詞的長度)
- C++實(shí)現(xiàn)LeetCode(57.插入?yún)^(qū)間)
- C++實(shí)現(xiàn)LeetCode(56.合并區(qū)間)
- C++實(shí)現(xiàn)LeetCode(53.最大子數(shù)組)
- C++實(shí)現(xiàn)LeetCode(52.N皇后問題之二)
- C++實(shí)現(xiàn)LeetCode(50.求x的n次方)
- C++實(shí)現(xiàn)LeetCode(48.旋轉(zhuǎn)圖像)
- C++實(shí)現(xiàn)LeetCode(62.不同的路徑)
相關(guān)文章
C++對Json數(shù)據(jù)的友好處理實(shí)現(xiàn)過程
在Ajax的應(yīng)用中,前臺(tái)基本上會(huì)用到JSON作為數(shù)據(jù)交換格式,所以下面這篇文章主要給大家介紹了關(guān)于C++對Json數(shù)據(jù)的友好處理,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-02-02使用VSCode和VS2017編譯調(diào)試STM32程序的實(shí)現(xiàn)
這篇文章主要介紹了使用VSCode和VS2017編譯調(diào)試STM32程序的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05C++ EasyX學(xué)習(xí)之鼠標(biāo)操作詳解
EasyX是針對C/C++的圖形庫,可以幫助使用C/C++語言的程序員快速上手圖形和游戲編程。本文將為大家詳細(xì)講講EasyX的鼠標(biāo)操作,需要的可以參考一下2022-07-07C++入門概覽和嘗試創(chuàng)建第一個(gè)C++程序
這篇文章主要介紹了C++入門概覽和嘗試創(chuàng)建第一個(gè)C++程序,同時(shí)也包括編寫類的示例展示C++面向?qū)ο蟮奶匦?需要的朋友可以參考下2015-09-09Mac下使用Eclipse編譯C/C++文件出現(xiàn) launch failed, binary not found 解決方
這篇文章主要介紹了Mac下使用Eclipse編譯C/C++文件出現(xiàn) launch failed, binary not found 解決方案,需要的朋友可以參考下2014-10-10