leetcode472 C++代码蜜汁内存超限......

看了半天没找到问题。怀疑是别的case爆了然后在这才出现问题，而且试了提交一下，发现结果是44/44 case pass,然后再给你一个result MLE。我用golang写的过程和你差不多，占用的内存可能还比你的大。因为你的这个case，看了下只有一个status的size和trie_node的深度只有1。不过频繁的push pop，感觉更应该是TLE. 在其他case中，倒是有可能因为status太大导致问题。 话说楼主你的new/delete版本是什么样的，我在想会不会是gc不及时导致的问题。 想了半天，用个黑魔法可以解决问题。就是直接把内存分配在静态存储区上。 下面这个版本可以过所有case。 ``` struct trie_node { trie_node* children[26]; bool isword = false; }; int cnt = 0; static trie_node tmp[100000]; int idx = 0; void trie_extend(trie_node* root, string &s) { for (auto c : s) { int childindex = c - 'a'; if (!root->children[childindex]){ root->children[childindex] = &tmp[idx]; idx++; } root = root->children[childindex]; } root->isword = true; } bool search(trie_node* root, string &s) { stack<pair<trie_node*, int> > status; status.push({ root, 0 }); bool res = false; while (!status.empty()) { auto p = status.top(); status.pop(); int index = p.second; trie_node* now = p.first; if (index == s.size()) { if (now->isword) res = true; continue; } int childindex = s[index] - 'a'; if (now->isword) status.push({ root, index }); if (now->children[childindex]) status.push({ now->children[childindex], index + 1 }); } return res; } class Solution { public: vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { sort(words.begin(), words.end(), [](const string &a, const string &b) { return a.size() < b.size(); }); idx = 0; memset(&tmp, 0, sizeof(tmp)); trie_node* root = &tmp[idx]; idx++; vector<string> res; for (auto &word : words) { if (word.empty()) continue; if (search(root, word)) res.push_back(word); else trie_extend(root, word); } return res; } }; ```

【 在 NachtZ 的大作中提到: 】 : [md] : 看了半天没找到问题。怀疑是别的case爆了然后在这才出现问题，而且试了提交一下，发现结果是44/44 case pass,然后再给你一个result MLE。我用golang写的过程和你差不多，占用的内存可能还比你的大。因为你的这个case，看了下只有一个status的size和trie_node的深度只有1。不过频繁的push pop，感觉更应该是TLE. 在其他case中，倒是有可能因为status太大导致问题。 : 话说楼主你的new/delete版本是什么样的，我在想会不会是gc不及时导致的问题。 : ................... 首先谢谢你耐心的帮我想了这个问题！ gc的话，最初我也是用一般指针做的，然后只new而没有delete(怕麻烦．．．．．．) 然后考虑到是不是这个原因引起的，所以改用了c++11 的shared_ptr, 它是基于引用计数的，计数为0就自动回收内存了。但是还是MLE了 然后关于栈的push, pop的话，原本的版本search用的是递归，最后一个例子字符串最长为1000,担心栈溢出，所以用栈实现的非递归。然而没什么卵用。 感觉leetcode的判题机制对c++不太友好．．． 顺带吐槽一下，这个是什么鬼．．．．．．

我是觉得leetcode是有可能出错的。因为leetcode对golang也很不友好，特别是内存占用和递归方面。 你的答案，用递归。在有些case中，很有可能会暴栈。不过这个case应该不会。这一题的case貌似没那么恶心，要不然dfs很容易就TLE了。 然后你的res为true之后应该尽快返回，而不应该continue。 至于shared_ptr,我不是在说你没有回收的事情，我怀疑的是shared_ptr不一定是及时回收，而不是说不回收。比如golang中，gc是隔一段时间触发一次的，递归着色的检索分配的内存。如果c++中，也是隔一段时间触发一次。而不是说在计数器为0的时候直接触发，是有可能报个MLE的。当然，如果因为这个原因的话，其实golang也很有可能暴的。 不过我试了下，手动new和手动delete，还是MLE.我现在觉得是leetcode的问题。 【 在 intmain 的大作中提到: 】 : 首先谢谢你耐心的帮我想了这个问题！ : gc的话，最初我也是用一般指针做的，然后只new而没有delete(怕麻烦．．．．．．) : 然后考虑到是不是这个原因引起的，所以改用了c++11 的shared_ptr, 它是基于引用计数的，计数为0就自动回收内存了。但是还是MLE了 : ...................

【 在 NachtZ 的大作中提到: 】 : 我是觉得leetcode是有可能出错的。因为leetcode对golang也很不友好，特别是内存占用和递归方面。 : 你的答案，用递归。在有些case中，很有可能会暴栈。不过这个case应该不会。这一题的case貌似没那么恶心，要不然dfs很容易就TLE了。 : 然后你的res为true之后应该尽快返回，而不应该continue。 : ................... （⊙ｖ⊙）嗯，那个continue．．． 本来while判断条件里面是有!res的，修修改改的不知道什么时候把他去掉了，╮（╯▽╰）╭ 手动回收都MLE,（⊙ｏ⊙）…感觉leetcode的内存使用判断有问题啊

你发邮件问leetcode管理员吧。这应该是个bug。 然后我在代码中判断输入跳过最后一个case。还是MLE。╮（╯▽╰）╭问题果然不在这。 【 在 intmain 的大作中提到: 】 : : （⊙ｖ⊙）嗯，那个continue．．． : 本来while判断条件里面是有!res的，修修改改的不知道什么时候把他去掉了，╮（╯▽╰）╭ : ...................

加set记录状态，防止重复入栈。 另外要定义在全局上。 ```c++ struct trie_node { shared_ptr<trie_node> children[26] = { nullptr }; bool isword = false; }; void trie_extend(shared_ptr<trie_node> root, string &s) { for (auto c : s) { int childindex = c - 'a'; if (!root->children[childindex]) root->children[childindex] = make_shared<trie_node>(); root = root->children[childindex]; } root->isword = true; } stack<pair<shared_ptr<trie_node>, int>> status; set<pair<shared_ptr<trie_node>, int> > hh; bool search(shared_ptr<trie_node> root, string &s) { while(status.size()) status.pop(); hh.clear(); status.push({ root, 0 }); bool res = false; while (!status.empty()) { auto p = status.top(); status.pop(); hh.insert(p); int index = p.second; shared_ptr<trie_node> now = p.first; if (index == s.size()) { if ( now->isword) res = true; continue; } int childindex = s[index] - 'a'; if (now->isword&&!hh.count({ root, index })) status.push({ root, index }); if (now->children[childindex]&&!hh.count({ now->children[childindex], index+1 })) status.push({ now->children[childindex], index+1 }); } return res; } class Solution { public: vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { sort(words.begin(), words.end(), [](const string &a, const string &b) { return a.size() < b.size(); }); shared_ptr<trie_node> root = make_shared<trie_node>(); vector<string> res; for (auto &word : words) { if (word.empty()) continue; if (search(root, word)) res.push_back(word); else trie_extend(root, word); } return res; } };

我记得我之前做的的时候用的是vector<trie_node*>chi(26,null)能过。。。