airbnb 一道电面题

农友们已经提到过的， iterator of a 2D array wi

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

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

目没有算法可言，但是很容易爬满虫子。。。

我写了一个，不知道对不对。

1. import java.io.*;
   
2. import java.util.*;
   
3. 
   
4. public class Solution {
   
5.   private List<List<Integer>> array;
   
6.   private int rowId;
   
7.   private int colId;
   
8.   private int numRows;
   
9.    
   
10.   public Solution(List<List<Integer>> array) {
    
11.     this.array = array;
    
12.     rowId = 0;
    
13.     colId = 0;
    
14.     numRows = array.size();
    
15.   }
    
16.    
    
17.   public boolean hasNext() {
    
18.     if (array == null || array.isEmpty()) {
    
19.       return false;
    
20.     }
    
21.      
    
22.     while (rowId < numRows && (array.get(rowId) == null ||
    
23.       array.get(rowId).isEmpty())) {
    
24.       rowId++;
    
25.     }
    
26.      
    
27.     return rowId < numRows;
    
28.   }
    
29.    
    
30.   public int next() {
    
31.     int ret = array.get(rowId).get(colId);
    
32.     colId++;
    
33.     if (colId == array.get(rowId).size()) {
    
34.       rowId++;
    
35.       colId = 0;
    
36.     }
    
37.      
    
38.     return ret;
    
39.   }
    
40.    
    
41.   public void remove() {
    
42.     List<Integer> listToRemove;
    
43.     int rowToRemove;
    
44.     int colToRemove;
    
45.      
    
46.     // Case 1: if the element to remove is the last element of the row
    
47.     if (colId == 0) {
    
48.       rowToRemove = rowId - 1;
    
49.       listToRemove = array.get(rowToRemove);
    
50.       colToRemove = listToRemove.size() - 1;
    
51.       
    
52.       listToRemove.remove(colToRemove);
    
53.     } else { // Case 2: the element to remove is not the last element
    
54.       rowToRemove = rowId;
    
55.       listToRemove = array.get(rowToRemove);
    
56.       colToRemove = colId - 1;
    
57.       listToRemove.remove(colToRemove);
    
58.     }
    
59.      
    
60.     // If the list to remove has only one element
    
61.     if (listToRemove.isEmpty()) {
    
62.       array.remove(listToRemove);
    
63.       rowId--;
    
64.     }
    
65.      
    
66.     // Update the colId
    
67.     if (colId != 0) {
    
68.       colId--;
    
69.     }
    
70.   }
    
71.    
    
72.   public static void main(String[] args) {
    
73.     List<List<Integer>> array = new ArrayList<>();
    
74.     List<Integer> row1 = new ArrayList<>();
    
75.     row1.add(1);
    
76.     row1.add(2);
    
77.     row1.add(3);
    
78.      
    
79.     array.add(row1);
    
80.      
    
81.     List<Integer> row3 = new ArrayList<>();
    
82.     array.add(row3);
    
83.      
    
84.     List<Integer> row2 = new ArrayList<>();
    
85.     row2.add(4);
    
86.     row2.add(5);
    
87.     array.add(row2);
    
88.      
    
89.     Solution sol = new Solution(array);
    
90.     while (sol.hasNext()) {
    
91.       int result = sol.next();
    
92.       System.out.println(result);
    
93.       
    
94.       if (result == 3) {
    
95.         sol.remove();
    
96.       }
    
97.     }
    
98.      
    
99.     System.out.println();
    
100.      
     
101.     for (List<Integer> row : array) {
     
102.       for (Integer elem : row) {
     
103.         System.out.println(elem);
     
104.       }
     
105.     }
     
106.   }
     
107.    
     
108. }

复制代码

Laurinda93 发表于 2016-7-22 07:09
我和层主有着同样的困惑；不知道你的思路有写过代码吗？

我觉得他的意思是  因为remove只能在next之后调用，而且iterator的更新是在每次调用next的时候更新的， 也就是说调用一次next后，iterator要么指向这一行中间的某个元素，要么指向这一行的end，这时调用remove的话，只要删掉当前iterator的前一个iterator就可以了，当然如果是C++的话，删除的结果应该再赋值给遍历用的iterator

爬满虫子这个term 我还用了几秒反应是什么意思。。。

remove 直接 调用next(),可以么？

butterwang 发表于 2015-12-2 07:48
我写了一个，不知道对不对。

如果是List<List<Integer>>这样的数据结构，可以用List的iterator，wrap一下就成了iterator of iterator。代码不超过30行

yjfox 发表于 2015-12-2 13:11
如果是List这样的数据结构，可以用List的iterator，wrap一下就成了iterator of iterator。代码不超过30行 ...

这样子就不太好删除元素了

joseph5wu 发表于 2016-2-12 11:28
这样子就不太好删除元素了

iterator的remove（） 一并wrap

降维或者wrap

yjfox 发表于 2016-2-12 12:51
iterator的remove（） 一并wrap

iterator的话如果上一次next的时候正好换成了下一个原来iterator的开始，这样remove是不是就无法处理了

joseph5wu 发表于 2016-2-12 14:31
iterator的话如果上一次next的时候正好换成了下一个原来iterator的开始，这样remove是不是就无法处理了

如果你说的是remove一个list中的第一个，那并不影响，删了还是可以next到下一个
如果你说的是remove一个list中的最后一个，那更不影响next到下一个list

不知道是否理解了你说的