最近leetcode的c++版本好像有点。。问题？就是，求解之后，特别吃内存。哪怕是他给的程序，复制粘贴提交，还是会非常吃内存。
用c++写几道题就发现，
go语言写：哇塞，程序挺不错的嘛！
c++写：哇靠，垃圾程序的典范！
e.g.: problem 17 phone number，典型的DFS题目。
一开始很快就能想到简单的递归方法：
string mapping[8]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
class Solution {
public:
Solution() {}
~Solution() {}
vector<string> letterCombinations(string digits) {
if (digits.length()<=0) return vector<string>{};
vector<string> m;
for (char& i : digits) {
m.push_back(getString(i - '0'));
}
solve(m, "", 0, digits.length());
return this->s;
}
void solve(vector<string> &m, string candidate, int ptr, int len) {
if (ptr == len - 1) {
for (char& i : m[ptr]) {
s.push_back(candidate + i);
}
} else {
for (char& i : m[ptr]) {
solve(m, candidate+i, ptr+1, len);
}
}
}
private:
vector<string> s;
inline string getString(const int a) { return mapping[a - 2]; };
};
结果，4ms，4.7MB 内存。哇靠，垃圾程序的典范！
然后，改成了迭代：
class Solution {
public:
Solution() {}
~Solution() {}
vector<string> letterCombinations(string digits) {
unordered_map<char, string> mapping{
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
if (digits.empty()) return {};
vector<int> steps{1};
int sum = 1;
for (auto& i : digits) {
sum *= mapping[i].length();
steps.push_back(sum);
}
vector<string> m(sum);
for (size_t i = 0; i < digits.length(); i++) {
string& s = mapping[digits[i]];
int j = 0;
while (j < sum) {
for (int k = j; k < j + sum / steps[i + 1]; k++) {
m[k] += s[(k / (sum / steps[i + 1])) % s.length()];
}
j += sum / steps[i + 1];
}
}
return m;
}
};
时间内存还是没变化。没道理吧。。。
然后我把给的0ms的example复制粘贴提交，发现，不可能达到0ms～2ms之间。不管怎么优化，内存都是4MB以上。
于是乎得出了个结论：leetcode上的c++提交时间判断可能是对的，但内存肯定是错的hhh
折腾了一晚上，无果。