LeetCode 1286. 字母组合迭代器(回溯/位运算)
发布日期:2021-07-01 03:25:14
浏览次数:3
分类:技术文章
本文共 1892 字,大约阅读时间需要 6 分钟。
文章目录
1. 题目
请你设计一个迭代器类,包括以下内容:
- 一个构造函数,输入参数包括:一个 有序且字符唯一 的字符串 characters(该字符串只包含小写英文字母)和一个数字 combinationLength 。
- 函数 next() ,按 字典序 返回长度为 combinationLength 的下一个字母组合。
- 函数 hasNext() ,只有存在长度为 combinationLength 的下一个字母组合时,才返回 True;否则,返回 False。
示例:CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iteratoriterator.next(); // 返回 "ab"iterator.hasNext(); // 返回 trueiterator.next(); // 返回 "ac"iterator.hasNext(); // 返回 trueiterator.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 { vectorans; 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, i+1);//下一个字符只能更大+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 = (1<0 && countOne(bits) != len) bits--; string t; for(int i = s.size()-1; i >= 0; --i) { if((bits>>i)&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
转载地址:https://michael.blog.csdn.net/article/details/105975552 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年05月05日 17时15分36秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!