Chapter 33 Iterator
Iterator顾名思义用iterative的方法解.递归的数据结构用迭代的方法解?这时候经常就需要stack的帮助.
C++ stack: http://en.cppreference.com/w/cpp/container/stack
33.1 173. Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average \(O(1)\) time and uses \(O(h)\) memory, where h is the height of the tree.
https://leetcode.com/problems/binary-search-tree-iterator/
如果不是题目对space complexity的要求,这题解法根据S分为:
S: O(1) - morris traversal
S: O(H) - stack
S: O(N) - do work at constructor
S:O(H)的解法如下:
维护一个栈,从根节点开始,每次迭代地将根节点的左孩子压入栈,直到左孩子为空为止. 调用next()方法时,弹出栈顶,如果被弹出的元素拥有右孩子,则以右孩子为根,将其左孩子迭代压栈.
class BSTIterator {
stack<TreeNode *> stk;
BSTIterator(TreeNode *root) { //
TreeNode *c = root;
while(c){
stk.push(c);
c = c->left;
}
}
bool hasNext() { return !stk.empty(); }
int next() {
auto t=stk.top(); stk.pop();
if (t->right){
auto c = t->right;
while(c) stk.push(c), c= c->left;
}
return t->val;
}
};S:O(N)的解法是: 采用根的中序遍历法将树节点保存在list中也可以实现树的迭代.但是空间复杂度\(O(N)\),N为树的大小,不满足题目要求
S:O(1)的解法(Morris)如下:
class BSTIterator {
TreeNode *c;
public:
BSTIterator(TreeNode *root) { c = root; }
bool hasNext() { return c!=NULL; }
int next() {// morris traversal
TreeNode* p, *t;
while(c){
if(c->left){
t = p = c->left;
while(p->right) p = p->right;
c->left=0, p->right=c, c = t;
}else{
break; //c = c->right;
}
}
int r = c->val;
c = c->right;
return r;
}
};33.2 284. Peeking Iterator
https://leetcode.com/problems/peeking-iterator/
If we know the underlying data structure, this question will be very easy. The trikcy part here is you can not access underlying data structure directly, instead you have to use the interface provided by the base class
C++:
class PeekingIterator : public Iterator {
int n;
public:
PeekingIterator(const vector<int>& nums) : Iterator(nums) {
if(Iterator::hasNext()) n = Iterator::next();
}
int peek() { return n; }
int next() {
int t=n;
n = Iterator::hasNext()?Iterator::next():INT_MAX;
return t;
}
bool hasNext() const {
return n!=INT_MAX;
}
};这里有个C++的语法问题,如何从child class里面调用parent class. 注意这里没有用override,因为没有virtual function. Overload和override的区别?
JAVA:
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
private Iterator<Integer> iter;
private Integer next;
public PeekingIterator(Iterator<Integer> iterator) {
// initialize any member here.
iter = iterator;
if (iter.hasNext()) {
next = iter.next();
}
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
return next;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
Integer res = next;
next = iter.hasNext() ? iter.next() : null;
return res;
}
@Override
public boolean hasNext() {
return next != null;
}
}33.3 341. Flatten Nested List Iterator
https://leetcode.com/problems/flatten-nested-list-iterator/
这道题让我们建立压平嵌套链表的迭代器,关于嵌套链表的数据结构最早出现在Nested List Weight Sum中,而那道题是用的递归的方法来解的,而迭代器一般都是用迭代的方法来解的,而递归一般都需用栈来辅助遍历,由于栈的后进先出的特性,我们在对向量遍历的时候,从后往前把对象压入栈中,那么第一个对象最后压入栈就会第一个取出来处理,我们的hasNext()函数需要遍历栈,并进行处理,如果栈顶元素是整数,直接返回true,如果不是,那么移除栈顶元素,并开始遍历这个取出的list,还是从后往前压入栈,循环停止条件是栈为空,返回false.
可不可以把push stack的任务放在next()函数中做呢?答案是不可以,因为有edge case: [[]], [[[[]]],[]],如果不对其解封,根本不知道是否有next.
注意就是stack是LIFO的,所以push的时候是从后往前loop.
class NestedIterator {
NestedIterator(vector<NestedInteger> &nestedList) {
for (int i = nestedList.size() - 1; i >= 0; --i)
s.push(nestedList[i]);
}
int next() { //O(1)
NestedInteger t = s.top(); s.pop();
return t.getInteger();
}
bool hasNext() {
while (!s.empty()) {
NestedInteger t = s.top();
if (t.isInteger()) return true;
s.pop();
for (int i = t.getList().size() - 1; i >= 0; --i)
s.push(t.getList()[i]);
}
return false;
}
private:
stack<NestedInteger> s;
};如果要强行用递归,在构造函数的时候就利用递归的方法把这个嵌套链表全部压平展开.其实程序一般初始化的时间长点无所谓,只要运行起来快就行.所以可以这样:
class NestedIterator {
NestedIterator(vector<NestedInteger> &nestedList) {
make_queue(nestedList);
}
int next() { //O(1)
int t = q.front(); q.pop();
return t;
}
bool hasNext() { //O(1)
return !q.empty();
}
private:
queue<int> q;
void make_queue(vector<NestedInteger> &nestedList) {
for (auto a : nestedList) {
if (a.isInteger()) q.push(a.getInteger());
else make_queue(a.getList());
}
}
};如果数据是静态的,其实第二个方法要好.如果这个数据是动态的,可以把第一个方法的stack改成deque或者list,可以在hasNext被调用之前往里面加入新的数据,虽然这不是典型迭代器的用法.
第二个方法并没有使用
getList().size(),如果没有size().第二种方法显得更加方便.
另一种写法:
class NestedIterator { // edge case: [[]], [[[[]]],[]]
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for(auto &n: nestedList) makeQ(n);
}
int next() { int r = Q.front(); Q.pop(); return r; }
bool hasNext() {return !Q.empty(); }
private:
queue<int> Q;
void makeQ(NestedInteger& n){
if(n.isInteger()) Q.push(n.getInteger());
else for(auto &e: n.getList()) makeQ(e);
}
};33.4 281. Zigzag Iterator
Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2]
v2 = [3, 4, 5, 6]By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].
Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?
Clarification for the follow up question - Update (2015-09-18): The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:
[1,2,3]
[4,5,6,7]
[8,9]It should return [1,4,8,2,5,9,3,6,7].
https://leetcode.com/problems/zigzag-iterator/
33.4.1 Algo 1: Matrix
关键是什么时候hasNext返回false.
class ZigzagIterator {
int i=0, j=0, ROW=2;
vector<vector<int>> v;
public:
ZigzagIterator(vector<int>& v1_, vector<int>& v2_){
v.push_back(v1_);
v.push_back(v2_);
}
int next() { return v[i++][j]; }
bool hasNext() {
if(i==ROW) i=0, j++;
int count=0;
while(i<ROW){
if(j>=v[i].size()){
i++, count++;
if(count==ROW) return 0;
if(i==ROW) i=0, j++, count=0;// else return 1;
}else return 1;
}
return 0;
}
};上面这个方法可以轻易推广到many vectors.
33.4.2 Algo 2: Queue
https://discuss.leetcode.com/topic/24548/c-with-queue-compatible-with-k-vectors
这个类似BFS.
33.5 251. Flatten 2D Vector
Implement an iterator to flatten a 2d vector.
For example, Given 2d vector =
[
[1,2],
[3],
[4,5,6]
]By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].
https://leetcode.com/problems/flatten-2d-vector/
- CPP
class Vector2D {
vector<vector<int>>::iterator i, iEnd;
int j = 0;
public:
Vector2D(vector<vector<int>>& vec2d) {
i = vec2d.begin();
iEnd = vec2d.end();
}
int next() {
hasNext();
return (*i)[j++];
}
bool hasNext() {
while (i != iEnd && j == (*i).size())
i++, j = 0;
return i != iEnd;
}
};- Java
public class Vector2D {
int indexList, indexEle;
List<List<Integer>> vec;
public Vector2D(List<List<Integer>> vec2d) {
indexList = 0;
indexEle = 0;
vec = vec2d;
}
public int next() {
return vec.get(indexList).get(indexEle++);
}
public boolean hasNext() {
while(indexList < vec.size()){
if(indexEle < vec.get(indexList).size())
return true;
else{
indexList++;
indexEle = 0;
}
}
return false;
}
}public class Vector2D {
private Iterator<List<Integer>> i;
private Iterator<Integer> j;
public Vector2D(List<List<Integer>> vec2d) {
i = vec2d.iterator();
}
public int next() {
hasNext();
return j.next();
}
public boolean hasNext() {
while ((j == null || !j.hasNext()) && i.hasNext())
j = i.next().iterator();
return j != null && j.hasNext();
}
}- Python
33.6 604. Design Compressed String Iterator
Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext.
The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.
next() - if the original string still has uncompressed characters, return the next letter; Otherwise return a white space.
hasNext() - Judge whether there is any letter needs to be uncompressed.
Note: Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details.
Example:
StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");
iterator.next(); // return 'L'
iterator.next(); // return 'e'
iterator.next(); // return 'e'
iterator.next(); // return 't'
iterator.next(); // return 'C'
iterator.next(); // return 'o'
iterator.next(); // return 'd'
iterator.hasNext(); // return true
iterator.next(); // return 'e'
iterator.hasNext(); // return false
iterator.next(); // return ' 'https://leetcode.com/problems/design-compressed-string-iterator
class StringIterator {
string s;
vector<int> f;//freq
int k=0;
public:
StringIterator(string compressedString) {
int i=-1;
for(char c: compressedString)
if(isdigit(c)){
i=i*10+c-'0';
}else{
if(i!=-1) f.push_back(i);
i=0, s+=c;
}
f.push_back(i);
}
char next() {
if(k==s.size()) return ' ';
char c=s[k];
if(--f[k]==0) k++;
return c;
}
bool hasNext() { return k<s.size();}
};