原文链接: https://leetcode-cn.com/problems/iterator-for-combination

英文原文

Design the CombinationIterator class:

• CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• next() Returns the next combination of length combinationLength in lexicographical order.
• hasNext() Returns true if and only if there exists a next combination.

 

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

 

Constraints:

• 1 <= combinationLength <= characters.length <= 15
• All the characters of characters are unique.
• At most 104 calls will be made to next and hasNext.
• It is guaranteed that all calls of the function next are valid.

中文题目

请你设计一个迭代器类，包括以下内容：

• 一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。
• 函数 next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。
• 函数 hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 True；否则，返回 False。

 

示例：

CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator

iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false

 

提示：

• 1 <= combinationLength <= characters.length <= 15
• 每组测试数据最多包含 10^4 次函数调用。
• 题目保证每次调用函数 next 时都存在下一个字母组合。

通过代码

高赞题解

1. 我们可以看到按照字典序排序编码如下，长度为2，比如：
   abcd
   则字典序排序应该是:

   ab
   ac
   ad
   bc
   bd

   刚好可以对应二进制数，从大到小:

   1100
   1010
   1001
   0110
   0101
   0011

   观察到以上规律，我们就可以避免求出所有的全排列组合，依次按照二进制编码从大到小的顺序，将所有的字符串依次求出即可。
2. 所谓的长度，只需要满足二进制编码中1的个数满足要求即可，通过n&(n-1)这种快速的解法很容易求出1的个数.

代码如下：

class CombinationIterator {
public:
    CombinationIterator(string characters, int combinationLength) {
        reverse(characters.begin(),characters.end());
        this->key = characters;
        this->curr = (1<<key.size())-1;
        this->sz = combinationLength;
    }
    
    int countOne(int n){
        int count = 0;
        while (n != 0){
            count++;
            n = (n-1) & n;
        }
        return count;
    }
    
    string next() {    
        while(curr >= 0 && countOne(curr) != sz){
            curr--;
        }
        
        string res;
        for(int i = 0; i < key.size(); ++i){
            if((curr&(1<<i))>>i){ 
                res = key[i] + res;
            }
        }
        curr--;
        
        return res;
    }

    bool hasNext() {  
        while(curr >= 0 && countOne(curr) != sz){curr--;}
        if(curr < 0){
            return false;
        }
        return true;
    }
private:
    int curr;
    int sz;
    int maxCnt;
    string key;
};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

统计信息

通过次数	提交次数	AC比率
5039	7734	65.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言