可跳过的Iterator

一道狗家面经题，附上自己之前写的test case

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

没有足够的米

发个java的implementation

1. 
   
2. 
   
3. import java.util.Arrays;
   
4. import java.util.HashMap;
   
5. import java.util.Iterator;
   
6. import java.util.Map;
   
7. 
   
8. 
   
9. public class SkipIterator {
   
10. 
    
11.     Iterator<Integer> iterator;
    
12.     Map<Integer, Integer> counter = new HashMap();
    
13.     Integer cache;
    
14. 
    
15.     public SkipIterator (Iterator<Integer> iterator) {
    
16.         this.iterator = iterator;
    
17.     }
    
18. 
    
19.     boolean hasNext() {
    
20.         while(iterator.hasNext()) {
    
21.             cache = iterator.next();
    
22.             if (counter.containsKey(cache)) {
    
23.                 counter.put(cache, counter.get(cache) - 1);
    
24.                 if (counter.get(cache) == 0) {
    
25.                     counter.remove(cache);
    
26.                 }
    
27.             } else {
    
28.                 break;
    
29.             }
    
30.         }
    
31.         return cache != null;
    
32.     }
    
33. 
    
34.     int next() {
    
35.         int ans = cache;
    
36.         cache = null;
    
37.         return ans;
    
38.     }
    
39. 
    
40.     void skip(int num) {
    
41.         counter.put(num, counter.getOrDefault(num, 0) + 1);
    
42.     }
    
43. 
    
44. 
    
45.     public static void main(String[] args) {
    
46.         int[] arr = new int[]{1, 2, 3, 4, 5, 6, 5, 6, 2, 3};
    
47.         SkipIterator skipIterator = new SkipIterator(Arrays.stream(arr).iterator());
    
48.         skipIterator.skip(5);
    
49.         skipIterator.skip(5);
    
50. 
    
51.         // expect: 1, 2, 3, 4, 6, 6, 2, 3
    
52.         while(skipIterator.hasNext()) {
    
53.             System.out.println(skipIterator.next());
    
54.         }
    
55.         System.out.println(skipIterator.hasNext());
    
56.     }
    
57. }
    

复制代码

补充内容 (2019-5-18 10:43):
代码里面 hasNext 有问题，如果skip的是最后一个数字3, cache 不会变成null，会把3 打印出来的。
简单的fix方式就在hasNext() if(counter.containsKey(cache))里把cache置为null

tank_z 发表于 2019-5-1 10:47
发个java的implementation
[mw_shl_code=java,true]

Hmmm. 代码好像不太对，如果直接call next（）的话会return null的，得先执行一下hasNext（）

sherry001 发表于 2019-5-13 08:07
Hmmm. 代码好像不太对，如果直接call next（）的话会return null的，得先执行一下hasNext（）

Iterator 在call next() 之前不就是得先call hasNext()吗， 不过也可以把hasNext()里的Logic移到next()里可能那样更make sense一点

tank_z 发表于 2019-5-13 08:44
Iterator 在call next() 之前不就是得先call hasNext()吗， 不过也可以把hasNext()里的Logic移到next()里 ...

啊，刚看到你在main里面写了，不过我觉得这些logic在SkipInterator class里面更好一些

想问一下这个不能用linked list实现么？

什么是神秘doc o.o

tank_z 发表于 2019-5-1 10:47
发个java的implementation
[mw_shl_code=java,true]

代码里面 hasNext 有问题，如果skip的是最后一个数字3, cache 不会变成null，会把3 打印出来的。
可以把skip(5), skip(5) 换成skip(3), skip(3)，结果是不对的