lc上的NestedInteger这个class到底如何定义呀

之前去onsite，因为是java选手，所以要写一个nestedinteger的class，（python应该是可以直接用了）。当时在面试官的指点下写出来了，现在想想又不会了。求指点！感谢！

可以看lc 341: https://leetcode.com/problems/fl ... erator/description/

可以对NestedInteger接口实现两个子类，一个处理单个整数的情况，另一个处理List的情况：

1. import java.util.ArrayList;
   
2. import java.util.Iterator;
   
3. import java.util.List;
   
4. import java.util.Stack;
   
5. 
   
6. public class Main {
   
7.   public static void main(String[] args) {
   
8.     // 测试数据
   
9.     // [1, [2, 3], [[4, [], [5], 6, 7], 8], 9]
   
10.     NestedInteger nestedList = new NestedList(
    
11.         new SingletonInteger(1),
    
12.         new NestedList(
    
13.             new SingletonInteger(2),
    
14.             new SingletonInteger(3)
    
15.         ),
    
16.         new NestedList(
    
17.             new NestedList(
    
18.                 new SingletonInteger(4),
    
19.                 new NestedList(),
    
20.                 new NestedList(
    
21.                     new SingletonInteger(5)
    
22.                 ),
    
23.                 new SingletonInteger(6),
    
24.                 new SingletonInteger(7)
    
25.             ),
    
26.             new SingletonInteger(8)
    
27.         ),
    
28.         new SingletonInteger(9)
    
29.     );
    
30. 
    
31.     NestedIterator it = new NestedIterator(nestedList.getList());
    
32.     while (it.hasNext()) {
    
33.       System.out.println(it.next());
    
34.     }
    
35.   }
    
36. }
    
37. 
    
38. 
    
39. interface NestedInteger {
    
40.   public boolean isInteger();
    
41.   public Integer getInteger();
    
42.   public List<NestedInteger> getList();
    
43. }
    
44. 
    
45. // 处理单个整数
    
46. class SingletonInteger implements NestedInteger {
    
47.   private int value;
    
48. 
    
49.   public SingletonInteger(int value) {
    
50.     this.value = value;
    
51.   }
    
52. 
    
53.   @Override
    
54.   public boolean isInteger() {
    
55.     return true;
    
56.   }
    
57. 
    
58.   @Override
    
59.   public Integer getInteger() {
    
60.     return value;
    
61.   }
    
62. 
    
63.   @Override
    
64.   public List<NestedInteger> getList() {
    
65.     return null;
    
66.   }
    
67. }
    
68. 
    
69. // 处理List
    
70. class NestedList implements NestedInteger {
    
71.   private List<NestedInteger> list = new ArrayList<NestedInteger>();
    
72. 
    
73.   public NestedList(NestedInteger ...values) {
    
74.     for (NestedInteger value : values) {
    
75.       list.add(value);
    
76.     }
    
77.   }
    
78. 
    
79.   @Override
    
80.   public boolean isInteger() {
    
81.     return false;
    
82.   }
    
83. 
    
84.   @Override
    
85.   public Integer getInteger() {
    
86.     return null;
    
87.   }
    
88. 
    
89.   @Override
    
90.   public List<NestedInteger> getList() {
    
91.     return list;
    
92.   }
    
93. }
    
94. 
    
95. 
    
96. // LC 341
    
97. class NestedIterator implements Iterator<Integer> {
    
98.   private Stack<Iterator<NestedInteger>> state;
    
99.   private boolean hasNextValue;
    
100.   private Integer nextValue;
     
101. 
     
102.   public NestedIterator(List<NestedInteger> nestedList) {
     
103.     state = new Stack<Iterator<NestedInteger>>();
     
104.     state.push(nestedList.iterator());
     
105.     fetchNext();
     
106.   }
     
107. 
     
108.   @Override
     
109.   public Integer next() {
     
110.     Integer retValue = nextValue;
     
111.     fetchNext();
     
112.     return retValue;
     
113.   }
     
114. 
     
115.   @Override
     
116.   public boolean hasNext() {
     
117.     return hasNextValue;
     
118.   }
     
119. 
     
120.   private void fetchNext() {
     
121.     while (!state.isEmpty()) {
     
122.       Iterator<NestedInteger> it = state.pop();
     
123.       if (it.hasNext()) {
     
124.         NestedInteger ni = it.next();
     
125.         state.push(it);
     
126.         if (ni.isInteger()) {
     
127.           hasNextValue = true;
     
128.           nextValue = ni.getInteger();
     
129.           return;
     
130.         }
     
131.         state.push(ni.getList().iterator());
     
132.       }
     
133.     }
     
134.     hasNextValue = false;
     
135.   }
     
136. }
     

复制代码

magicsets 发表于 2018-1-23 04:06
可以对NestedInteger接口实现两个子类，一个处理单个整数的情况，另一个处理List的情况：

sorry，不明白为什么会miss到这个消息，现在才看到，先给层主热心答题点赞！非常感谢！