1233.
看起来就trie
多开一格放slash 才不会跟stop撞
不然a会卡ax...什么什么的
class Trie {
public:
vector<Trie*> ch;
bool stop;
Trie(): ch(27, nullptr), stop(false){};
// ch[26] = '/';
};
class Solution {
public:
Trie* root;
vector<string> removeSubfolders(vector<string>& folder) {
root = new Trie();
for(auto& s: folder){
Trie* t = root;
for(int i = 0; i < s.length(); i++){
if(s[i] == '/'){
if(t->stop) break;
if(t->ch[26] == nullptr){
t->ch[26] = new Trie();
}
t = t->ch[26];
continue;
}
if(t->ch[s[i]-'a'] == nullptr){
t->ch[s[i]-'a'] = new Trie();
}
t = t->ch[s[i]-'a'];
}
t->stop = true;
}
vector<string> res;
search_folder(root, "", res);
return res;
}
void search_folder(Trie* t, string folder, vector<string>& res){
if(t == nullptr) return ;
for(int i = 0; i < 26; i++){
search_folder(t->ch[i], folder + (char)('a' + i), res);
}
if(t->stop){
res.push_back(folder);
return;
}
else search_folder(t->ch[26], folder + '/', res);
}
};
跑好慢
看solution说有nlogn
才想到可以直接sort找
就看现在这个是不是上一个的subfolder
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
ranges::sort(folder);
unordered_set<string> fs;
vector<string> res;
int len = folder[0].length();
for(auto& s: folder){
if(s.length() < len or s[len] != '/' or !fs.count(s.substr(0, len)) ){
fs.insert(s);
res.push_back(s);
len = s.length();
}
}
return res;
}
};
刷题这么好玩
我都把daily当wordle在解
别人打LOL我写扣
这种需要一点点思考的游戏
本质差不多吧
打LOL比较难一点
※ 引述《Sougou (搜狗)》之铭言：
: 别再卷LeetCode了拉，
: 卷了对于求职也不见得有帮助，
: 对啊，
: 根据我之前硕毕拿offer经验，
: 星国外商银行IT一年有百万，
: 面试还不是不看LeetCode，
: 考的是Java阿，
: 唉，
: 卷LeetCode不如去准备作品集==