app开发做网站,wordpress增加模板,安居客网站应该如何做,360建筑网怎么重新注册文章目录1. 题目2. 解题2.1 回溯2.2 位运算1. 题目
请你设计一个迭代器类#xff0c;包括以下内容#xff1a;
一个构造函数#xff0c;输入参数包括#xff1a;一个 有序且字符唯一 的字符串 characters#xff08;该字符串只包含小写英文字母#xff09;和一个数字 c…
文章目录1. 题目2. 解题2.1 回溯2.2 位运算1. 题目
请你设计一个迭代器类包括以下内容
一个构造函数输入参数包括一个 有序且字符唯一 的字符串 characters该字符串只包含小写英文字母和一个数字 combinationLength 。函数 next() 按 字典序 返回长度为 combinationLength 的下一个字母组合。函数 hasNext() 只有存在长度为 combinationLength 的下一个字母组合时才返回 True否则返回 False。
示例
CombinationIterator iterator new CombinationIterator(abc, 2);
// 创建迭代器 iteratoriterator.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 时都存在下一个字母组合。来源力扣LeetCode 链接https://leetcode-cn.com/problems/iterator-for-combination 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 回溯
回溯法先全部求出来存起来备用
class CombinationIterator {vectorstring ans;string path;int id 0;
public:CombinationIterator(string characters, int combinationLength){dfs(characters, combinationLength, 0);}void dfs(string s, int n, int idx){if(path.size() n){ans.push_back(path);return;}for(int i idx; i s.size(); i){path.push_back(s[i]);dfs(s, n, i1);//下一个字符只能更大1开始找path.pop_back();}}string next() {return ans[id];}bool hasNext() {return id ans.size();}
};32 ms 12.8 MB
2.2 位运算 class CombinationIterator {int bits;string s;int len;
public:CombinationIterator(string characters, int combinationLength) {s characters;bits (1s.size())-1;len combinationLength;}int countOne(int n){int count 0;while(n){count;n n (n-1);}return count;}string next() {while(bits 0 countOne(bits) ! len)bits--;string t;for(int i s.size()-1; i 0; --i){if((bitsi)1)t s[s.size()-i-1];//字符串是从左往右的序号0开始}bits--;//下一个数下次搜索的起点return t;}bool hasNext() {while(bits 0 countOne(bits) ! len)bits--;return bits 0;}
};20 ms 12 MB
