-
Notifications
You must be signed in to change notification settings - Fork 43
/
flatten-nested-list-iterator.py
444 lines (366 loc) · 13.3 KB
/
flatten-nested-list-iterator.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
"""
341. Flatten Nested List Iterator
Medium
You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.
Implement the NestedIterator class:
NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
int next() Returns the next integer in the nested list.
boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.
Your code will be tested with the following pseudocode:
initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res
If res matches the expected flattened list, then your code will be judged as correct.
Example 1:
Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
Constraints:
1 <= nestedList.length <= 500
The values of the integers in the nested list is in the range [-106, 106].
"""
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
# V0
class NestedIterator(object):
def __init__(self, nestedList):
self.queue = []
def getAll(nests):
for nest in nests:
if nest.isInteger():
self.queue.append(nest.getInteger())
else:
getAll(nest.getList())
getAll(nestedList)
def next(self):
return self.queue.pop(0)
def hasNext(self):
return len(self.queue)
# V0'
import collections
class NestedIterator(object):
def __init__(self, nestedList):
self.queue = collections.deque()
def getAll(nests):
for nest in nests:
if nest.isInteger():
self.queue.append(nest.getInteger())
else:
getAll(nest.getList())
getAll(nestedList)
def next(self):
return self.queue.popleft()
def hasNext(self):
return len(self.queue)
# V0''
#### key : define a r = [] outside of the func
# r = []
# def flatten_array(_array):
# for i in _array:
# if type(i) == int:
# print (i)
# r.append(i)
# else:
# flatten_array(i)
#
# _input = [1,0, [1,2,[4,[5,[6,[7]]]]]]
#
# flatten_array(_input)
# print ("r = " + str(r))
# V1
# https://blog.csdn.net/fuxuemingzhu/article/details/79529982
import collections
class NestedIterator(object):
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
self.queue = collections.deque()
def getAll(nests):
for nest in nests:
if nest.isInteger():
self.queue.append(nest.getInteger())
else:
getAll(nest.getList())
getAll(nestedList)
def next(self):
"""
:rtype: int
"""
return self.queue.popleft()
def hasNext(self):
"""
:rtype: bool
"""
return len(self.queue)
# V1'
# https://www.jiuzhang.com/solution/flatten-nested-list-iterator/#tag-highlight-lang-python
class NestedIterator(object):
def __init__(self, nestedList):
self.next_elem = None
self.stack = []
for elem in reversed(nestedList):
self.stack.append(elem)
# @return {int} the next element in the iteration
def next(self):
if self.next_elem is None:
self.hasNext()
temp, self.next_elem = self.next_elem, None
return temp
# @return {boolean} true if the iteration has more element or false
def hasNext(self):
if self.next_elem:
return True
while self.stack:
top = self.stack.pop()
if top.isInteger():
self.next_elem = top.getInteger()
return True
for elem in reversed(top.getList()):
self.stack.append(elem)
return False
# V1
# IDEA : Make a Flat List with Recursion
# https://leetcode.com/problems/flatten-nested-list-iterator/solution/
class NestedIterator:
def __init__(self, nestedList):
def flatten_list(nested_list):
for nested_integer in nested_list:
if nested_integer.isInteger():
self._integers.append(nested_integer.getInteger())
else:
flatten_list(nested_integer.getList())
self._integers = []
self._position = -1 # Pointer to previous returned.
flatten_list(nestedList)
def next(self):
self._position += 1
return self._integers[self._position]
def hasNext(self):
return self._position + 1 < len(self._integers)
# V1
# IDEA : Stack
# https://leetcode.com/problems/flatten-nested-list-iterator/solution/
class NestedIterator:
def __init__(self, nestedList):
self.stack = list(reversed(nestedList))
def next(self):
self.make_stack_top_an_integer()
return self.stack.pop().getInteger()
def hasNext(self):
self.make_stack_top_an_integer()
return len(self.stack) > 0
def make_stack_top_an_integer(self):
# While the stack contains a nested list at the top...
while self.stack and not self.stack[-1].isInteger():
# Unpack the list at the top by putting its items onto
# the stack in reverse order.
self.stack.extend(reversed(self.stack.pop().getList()))
# V1
# IDEA : Two Stacks
# https://leetcode.com/problems/flatten-nested-list-iterator/solution/
class NestedIterator:
def __init__(self, nestedList):
self.stack = [[nestedList, 0]]
def make_stack_top_an_integer(self):
while self.stack:
# Essential for readability :)
current_list = self.stack[-1][0]
current_index = self.stack[-1][1]
# If the top list is used up, pop it and its index.
if len(current_list) == current_index:
self.stack.pop()
continue
# Otherwise, if it's already an integer, we don't need
# to do anything.
if current_list[current_index].isInteger():
break
# Otherwise, it must be a list. We need to increment the index
# on the previous list, and add the new list.
new_list = current_list[current_index].getList()
self.stack[-1][1] += 1 # Increment old.
self.stack.append([new_list, 0])
def next(self):
self.make_stack_top_an_integer()
current_list = self.stack[-1][0]
current_index = self.stack[-1][1]
self.stack[-1][1] += 1
return current_list[current_index].getInteger()
def hasNext(self):
self.make_stack_top_an_integer()
return len(self.stack) > 0
# V1
# IDEA : Stack of Iterators
# https://leetcode.com/problems/flatten-nested-list-iterator/solution/
# JAVA
# import java.util.NoSuchElementException;
#
# public class NestedIterator implements Iterator<Integer> {
#
# // This time, our stack will hold list iterators instead of just lists.
# private Deque<ListIterator<NestedInteger>> stackOfIterators = new ArrayDeque();
# private Integer peeked = null;
#
# public NestedIterator(List<NestedInteger> nestedList) {
# // Make an iterator with the input and put it on the stack.
# // Note that creating a list iterator is an O(1) operation.
# stackOfIterators.addFirst(nestedList.listIterator());
# }
#
# private void setPeeked() {
#
# // If peeked is already set, there's nothing to do.
# if (peeked != null) return;
#
# while (!stackOfIterators.isEmpty()) {
#
# // If the iterator at the top of the stack doesn't have a next,
# // remove that iterator and continue on.
# if (!stackOfIterators.peekFirst().hasNext()) {
# stackOfIterators.removeFirst();
# continue;
# }
#
# // Otherwise, we need to check whether that next is a list or
# // an integer.
# NestedInteger next = stackOfIterators.peekFirst().next();
#
# // If it's an integer, set peeked to it and return as we're done.
# if (next.isInteger()) {
# peeked = next.getInteger();
# return;
# }
#
# // Otherwise, it's a list. Create a new iterator with it, and put
# // the new iterator on the top of the stack.
# stackOfIterators.addFirst(next.getList().listIterator());
# }
# }
#
#
# @Override
# public Integer next() {
#
# // As per Java specs, throw an exception if there are no further elements.
# if (!hasNext()) throw new NoSuchElementException();
#
# // hasNext() called setPeeked(), which ensures peeked has the next integer
# // in it. We need to clear the peeked field so that the element is returned
# // again.
# Integer result = peeked;
# peeked = null;
# return result;
# }
#
# @Override
# public boolean hasNext() {
#
# // Try to set the peeked field. If any integers are remaining, it will
# // contain the next one to be returned after this call.
# setPeeked();
#
# // There are elements remaining iff peeked contains a value.
# return peeked != null;
# }
# }
# V1
# IDEA : Using a Generator
# https://leetcode.com/problems/flatten-nested-list-iterator/solution/
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
# Get a generator object from the generator function, passing in
# nestedList as the parameter.
self._generator = self._int_generator(nestedList)
# All values are placed here before being returned.
self._peeked = None
# This is the generator function. It can be used to create generator
# objects.
def _int_generator(self, nested_list):
# This code is the same as Approach 1. It's a recursive DFS.
for nested in nested_list:
if nested.isInteger():
"""
NOTE : we use yield here
"""
yield nested.getInteger()
else:
"""
NOTE : we use yield here
"""
# We always use "yield from" on recursive generator calls.
yield from self._int_generator(nested.getList())
# Will automatically raise a StopIteration.
def next(self):
# Check there are integers left, and if so, then this will
# also put one into self._peeked.
if not self.hasNext(): return None
# Return the value of self._peeked, also clearing it.
next_integer, self._peeked = self._peeked, None
return next_integer
def hasNext(self):
if self._peeked is not None: return True
try: # Get another integer out of the generator.
self._peeked = next(self._generator)
return True
except: # The generator is finished so raised StopIteration.
return False
# V2
# Time: O(n), n is the number of the integers.
# Space: O(h), h is the depth of the nested lists.
class NestedIterator(object):
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
self.__depth = [[nestedList, 0]]
def next(self):
"""
:rtype: int
"""
nestedList, i = self.__depth[-1]
self.__depth[-1][1] += 1
return nestedList[i].getInteger()
def hasNext(self):
"""
:rtype: bool
"""
while self.__depth:
nestedList, i = self.__depth[-1]
if i == len(nestedList):
self.__depth.pop()
elif nestedList[i].isInteger():
return True
else:
self.__depth[-1][1] += 1
self.__depth.append([nestedList[i].getList(), 0])
return False