真心求教iterator of iterator

stellari 发表于 2016-4-2 23:38
我其实指的是iterator of iterators的代码……不过两道题意思其实差不多。

面试的话，还是上来就给ite ...

嗯嗯有道理，多谢提醒啊！

谁能贴个Java的解法？多谢啊

stellari 发表于 2016-4-2 23:38
我其实指的是iterator of iterators的代码……不过两道题意思其实差不多。

面试的话，还是上来就给ite ...

我写了个zigzag用iterator的解法，感觉除了需要一个STL存iterator，还是需要把input的container都存一下的，
比如我用的是

1. queue<vector<int>::iterator> zigIt

复制代码

和

1. queue<vector<int>> numbers

复制代码

，
剩下的思路跟我之前说的那个queue的差不多，
判定hasNext需要把queue里等于当前container end()的都pop掉，return是否不为空，
next函数就取zigIt里front指向的数据，然后在numbers里把这个数删掉，再把这个vector移到numbers的队尾，最后再处理下zigIt。这个的话我感觉跟LRU cache思路有点接近

1. 
   
2.         queue<vector<int>::iterator> zit;
   
3.         queue<vector<int>> number;
   
4.         zigzagIter(vector<vector<int>>& nums) {
   
5.                
   
6.                 for (vector<int> n : nums){
   
7.                         number.push(n);
   
8.                         zit.push(number.back().begin());
   
9.                 }
   
10.         }
    
11.         bool hasNext(){
    
12.                 if (zit.empty())return false;
    
13.                 while (!zit.empty() && zit.front() == number.front().end()){
    
14.                         zit.pop();
    
15.                         number.pop();
    
16.                 }
    
17.                 if (zit.empty())return false;
    
18.                 else return true;
    
19.         }
    
20.         int next(){
    
21.                 int res = *zit.front();
    
22.                 number.front().erase(zit.front());
    
23.                 zit.pop();
    
24.                 number.push(number.front());
    
25.                 number.pop();
    
26.                 zit.push(number.back().begin());
    
27.                
    
28.                 return res;
    
29.         }

复制代码

所以我感觉复制vector也是难以避免吧（当然C++里一般是用vector，所以类型确实是绑定的，JAVA会有更general点的container可以包含各种object）
因为一方面iterator需要指向实际存在的成员，不然都会变成null吧
然后每个iterator要判定他是不是到当前container的end()的指针时候要是不知道container的ref貌似没办法判定。不过这里应该还是会有更好的办法，我这块知识有限，要是有知道的大神也麻烦给点思路。

mymax2009 发表于 2016-4-4 13:33
我写了个zigzag用iterator的解法，感觉除了需要一个STL存iterator，还是需要把input的container都存一下 ...

嗯，这个用到了iterator，算法是正确的，但是还是不能完全满足我当初面试G时现场被问到的要求：

1. 输入是Iterator<Iterator<Type>>，这点面试官在现场特别强调过，也就是要求底层容器可以是任意类型。不过可以假设我们手头已经有可用的Iterator<Type>的具体类，不需自行实现。

2. ZigzagIterator内部不能使用超过O(K)的内存，其中K是外层容器的尺寸。也就是说内部存放二维容器的数据是不允许的。

3. ZigzagIterator必须实现Iterator<Type>接口。


换言之，ZigzagIterator必须是这个样子的：

template<typename Type>
class ZigzagIterator : public Iterator<Type> {
   ...
public:
    ZigzagIterator(Iterator<Iterator<Type>>& );
    Type next() {...}
    bool hasNext() {...}
};

这种限制条件下，你怎么做呢？

我被这道题坑过  主要是没太用过java里面的iterator   然后我用C++ 当时一脸懵逼不知道要干啥
四轮面试里面唯一一轮低分

bingo1995 发表于 2016-4-4 17:19
我被这道题坑过  主要是没太用过java里面的iterator   然后我用C++ 当时一脸懵逼不知道要干啥
四轮面试里 ...

我也是同样遭遇，面试官自己明显是Java背景。Java下的迭代器通常都是实现自通用的Iterator<E>接口，常见容器中都实现了Iterable<E>接口（该接口其中提供了一个Iterator<E>）。但问题是C++的 STL容器都是各自为战，压根就没有这么个“通用迭代器”接口，而algorithm中接受iterator的算法都是通过template来实现的。在现有C++框架下想实现个通用的iterator接口并不trivial，而且关键是各路大牛们都认为这么做是个很糟糕的主意。

所以对用C++的同学来说，遇到这题只能是假设已经有个实现好的Iterator<E>。

另外问一下，你怎么知道你每一轮的成绩的？

stellari 发表于 2016-4-4 19:01
我也是同样遭遇，面试官自己明显是Java背景。Java下的迭代器通常都是实现自通用的Iterator接口，常见容器 ...

感觉啊。最后HR说有一个面试官说我coding不行  但我最后还是拿到offer了 说明其他三轮是不错的。
虽然最后没接 233

bingo1995 发表于 2016-4-4 19:02
感觉啊。最后HR说有一个面试官说我coding不行  但我最后还是拿到offer了 说明其他三轮是不错的。
虽然最 ...

厉害啊！

stellari 发表于 2016-4-4 17:12
嗯，这个用到了iterator，算法是正确的，但是还是不能完全满足我当初面试G时现场被问到的要求：

1. 输 ...

如果Iterator<Type>已经有了的话那其实也还好，就跟JAVA和C#类似的不过需要多做一个box和unbox类似的操作吧。
但是只能用O(N)内存的话，
还是那两点疑问啊，一个是得有一个方法能判断当前iterator是否到达它自己的end()才行的吧。不过这个应该还是能有办法。
另一点如果类的内部不存储整个数据那指针操作不就没意义了吗？

mymax2009 发表于 2016-4-5 01:37
如果Iterator已经有了的话那其实也还好，就跟JAVA和C#类似的不过需要多做一个box和unbox类似的操作吧。
...

你说的这两个问题，恰好是Iterator<Type>接口要解决的问题：

1. 判断被包装的Iterator是否已经到达容器尾，直接调用它提供的hasNext()接口函数即可。
2. 你获得下一个元素的唯一途径，就是通过被包装的Iterator的next()函数。你自己写的代码中不应该出现任何指向容器内元素的指针。

这是纯粹的Java思路，所以我才建议你做这题时最好转用Java来做。用C++强行实现这种思路太痛苦了。