Re: [閒聊] 每日LeetCode已回收
49. Group Anagrams
要把同樣字母組成的字串分在同一組
所以重點在要能知道兩個字串是否由相同字母組成
最簡單的方法是把兩個字串 sort 之後進行比較
所以可以寫一個 hash map 是 string ---> vector<string>
key 就是 sort 過的字串
這樣複雜度會是 O(n klogk), k 是字串長度
雖然 k 上限只有 100 而已，但有個 log 卡在那邊就有點不爽
所以後來改成用 char arr[26] 來存各字母出現的次數
(因為 k <= 100 < 128 所以 char 放的下)
這樣複雜度可以到 O(nk)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> M;
for (string & s: strs) {
char arr[26] = {};
for (char c: s)
arr[c - 'a'] += 1;
M[string(arr, arr + 26)].push_back(s);
}
vector<vector<string>> ans;
for (auto & [_, v]: M)
ans.push_back(move(v));
return ans;
}
};
Runtime : 19 ms (99.99%)
Memory : 19.5 MB (87.72%)
https://leetcode.com/submissions/detail/831781703/
是說，LeetCode 的執行時間好像不是很穩定
我改個變數名稱，理論上要是一模一樣的程式再丟一次
時間就暴增到 54 ms，所以感覺那個百分比也看看就好
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.130 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1666926548.A.2AE.html
→
10/28 11:12,
3年前
, 1F
10/28 11:12, 1F
→
10/28 11:12,
3年前
, 2F
10/28 11:12, 2F
→
10/28 11:17,
3年前
, 3F
10/28 11:17, 3F
推
10/28 14:40,
3年前
, 4F
10/28 14:40, 4F
→
10/28 15:15,
3年前
, 5F
10/28 15:15, 5F
→
10/28 15:32,
3年前
, 6F
10/28 15:32, 6F
→
10/28 15:32,
3年前
, 7F
10/28 15:32, 7F
→
10/28 15:33,
3年前
, 8F
10/28 15:33, 8F
→
10/28 15:55,
3年前
, 9F
10/28 15:55, 9F
→
10/28 15:56,
3年前
, 10F
10/28 15:56, 10F
推
10/28 15:56,
3年前
, 11F
10/28 15:56, 11F
討論串 (同標題文章)
完整討論串 (本文為第 68 之 719 篇)：