1286. 字母组合迭代器
请你设计一个迭代器类 CombinationIterator ，包括以下内容：
CombinationIterator(string characters, int combinationLength) 一个构造函数，输入参数包括：用一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 true
示例 1：
输入:
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
输出：
[null, "ab", true, "ac", true, "bc", 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 <= 15characters 中每个字符都 不同next 和 hasNext 调用 104次next 时都存在下一个字母组合。原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 6.8 MB, 提交时间: 2022-11-27 12:58:06
type CombinationIterator struct {
index int
characters []string
combinationLength int
}
func Constructor(characters string, combinationLength int) CombinationIterator {
length := len(characters)
ch := make([]string, length)
for i := range ch {
ch[i] = string(characters[i])
}
sort.Strings(ch)
fmt.Println(ch)
index := int(math.Pow(float64(2), float64(length)))
return CombinationIterator{index,ch,combinationLength}
}
func (this *CombinationIterator) Next() string {
this.index = nextIndex(this.index,this.combinationLength)
return getString(this.index, this.characters)
}
func getString(index int, characters []string) string {
res := ""
position := len(characters)-1
for index>0{
if index % 2 != 0 && position>=0{
res = characters[position] + res
}
position--
index /= 2
}
return res
}
func (this *CombinationIterator) HasNext() bool {
if nextIndex(this.index, this.combinationLength)>0{
return true
}
return false
}
func nextIndex(index int, length int) int {
index--
for index > 0 && countOne(index) != length {
index--
}
return index
}
func countOne(index int) int {
count := 0
for index>0{
count++
index &= index-1
}
return count
}
/**
* Your CombinationIterator object will be instantiated and called as such:
* obj := Constructor(characters, combinationLength);
* param_1 := obj.Next();
* param_2 := obj.HasNext();
*/
cpp 解法, 执行用时: 12 ms, 内存消耗: 11.9 MB, 提交时间: 2022-11-27 12:57:21
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();
*/
/**
* 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();
*/
python3 解法, 执行用时: 60 ms, 内存消耗: 17.5 MB, 提交时间: 2022-11-27 12:56:24
class CombinationIterator:
def __init__(self, characters: str, combinationLength: int):
self.s = characters
self.pos = [x for x in range(combinationLength)]
self.finished = False
def next(self) -> str:
ans = "".join([self.s[p] for p in self.pos])
i = -1
for k in range(len(self.pos) - 1, -1, -1):
if self.pos[k] != len(self.s) - len(self.pos) + k:
i = k
break
if i == -1:
self.finished = True
else:
self.pos[i] += 1
for j in range(i + 1, len(self.pos)):
self.pos[j] = self.pos[j - 1] + 1
return ans
def hasNext(self) -> bool:
return not self.finished
# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()