又要写 leetcode 解题思路了，实在不想写一大堆的 leetcode 放在日记里，这篇先存成草稿，考虑是不是要给 leetcode 单独一个版面，免得让我感觉每天只是刷题。
combination，看到这个词，就觉得这道题是位操作的题，想到位操作，就头疼，不擅长啊。
看了以前的提交记录，上次是先生成所有的组合，然后直接返回结果的解法，很好，空间换时间，简单直接。唯一的问题就是如果字符很长就要占用相当大的内存空间。目前这个解法还能过，不知道以后随着测试样例的增加，会不会内存不够用（MLE）。发现自己习惯用 deque，两头可进可出，想怎么进出就怎么进出，真方便啊。根据cplusplus.com的介绍，c++ 上的 stack 和 queue 都是 deque 再次封装阉割实现的，用 deque 效率也更高。
上代码，这种解法没什么可说的。
class CombinationIterator {
public:
CombinationIterator(string characters, int combinationLength) {
const int n = characters.size();
function<void(int, string)> helper = [&] (const int idx, string cur) {
if (cur.size() == combinationLength) {
dq_.push_back(cur);
return;
}
for (int i = idx; i < n; ++i)
helper(i + 1, cur + characters[i]);
};
helper(0, "");
}
// It's guaranteed that all calls of the function next are valid.
string next() {
string res = dq_.front();
dq_.pop_front();
return res;
}
bool hasNext() {
return !dq_.empty();
}
deque<string> dq_;
};
真正有趣的是位操作的解法。网上有很多介绍通过位操作来快速计算的奇技淫巧，很有趣。下面这种解法来自花花
class CombinationIterator {
public:
CombinationIterator(string characters, int combinationLength):
chars_ (characters.rbegin(), characters.rend()) {
n_ = combinationLength;
mask_ = (1 << characters.size()) - 1;
}
string next() {
hasNext();
string res;
for (int i = chars_.size() - 1; i >= 0; --i)
if ((mask_ >> i) & 1)
res.push_back(chars_[i]);
--mask_;
return res;
}
bool hasNext() {
while (mask_ >= 0 && __builtin_popcount(mask_) != n_) --mask_;
return mask_ > 0;
}
private:
int mask_, n_;
string chars_;
};
两种解法的比较：第一种解法先生成了全部的组合，每次调用 next() 的时候直接给出答案，反应迅速但是内存消耗大。第二种方法需要在调用 next() 时计算，虽然位操作很快可是遇到 string 也会被拖累。如果系统要优秀的反应的时间，内存消耗不严格，就选用第一种，理解简单，维护方便，常数时间给出结果。如果对内存要求苛刻或者组合太大没办法全部生成，再采用第二种。