[Swift]LeetCode341.压平嵌套链表迭代器|FlattenNestedListIterator

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10738395.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

给定一个嵌套的整数列表，实现一个迭代器来展平它。

每个元素要么是一个整数，要么是一个列表——其元素也可以是整数或其他列表。

例1：

给出列表[[1,1]，2，[1,1]]，

通过反复调用next，直到hasNext返回false，next返回的元素顺序应该是：[1,1,2,1,1]。

例2：

给出清单[1，[4，[6]]]，

通过重复调用next直到hasNext返回false，next返回的元素顺序应该是：[1,4,6]。

52ms

 1 /**
 2  * // This is the interface that allows for creating nested lists.
 3  * // You should not implement it, or speculate about its implementation
 4  * class NestedInteger {
 5  *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 6  *     public func isInteger() -> Bool
 7  *
 8  *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 9  *     // The result is undefined if this NestedInteger holds a nested list
10  *     public func getInteger() -> Int
11  *
12  *     // Set this NestedInteger to hold a single integer.
13  *     public func setInteger(value: Int)
14  *
15  *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
16  *     public func add(elem: NestedInteger)
17  *
18  *     // Return the nested list that this NestedInteger holds, if it holds a nested list
19  *     // The result is undefined if this NestedInteger holds a single integer
20  *     public func getList() -> [NestedInteger]
21  * }
22  */
23 
24 class NestedIterator {
25 
26       var array = [Int]()
27       var currentIterator = 0
28 
29       init(_ nestedList: [NestedInteger]) {
30         flattenList(nestedList)
31       }
32 
33       func flattenList(_ nestedList: [NestedInteger]) {
34         for element in nestedList {
35           if element.isInteger() {
36             array.append(element.getInteger())
37           } else {
38             flattenList(element.getList())
39           }
40         }
41       }
42 
43       func next() -> Int {
44         let val = array[currentIterator]
45         currentIterator += 1
46         return val
47       }
48 
49       func hasNext() -> Bool {
50         return currentIterator < array.count
51       }
52 }
53 
54 /**
55  * Your NestedIterator object will be instantiated and called as such:
56  * let obj = NestedIterator(nestedList)
57  * let ret_1: Int = obj.next()
58  * let ret_2: Bool = obj.hasNext()
59  */

56ms

 1 class NestedIterator {
 2     private var stack = [NestedInteger]()
 3     private var curr = 0
 4     private var arr = [NestedInteger]()
 5     init(_ nestedList: [NestedInteger]) {
 6         arr = nestedList
 7     }
 8     
 9     
10     private func flatternCurrentStack(){
11         while !stack.isEmpty && !stack.last!.isInteger(){
12             let list = stack.removeLast().getList()
13             for i in stride(from: list.count - 1, through: 0 , by: -1){
14                 stack.append(list[i])
15             }
16         }
17     }
18     
19     
20     func next() -> Int {
21         return stack.removeLast().getInteger()
22     }
23     
24     func hasNext() -> Bool {
25         flatternCurrentStack()
26         while stack.isEmpty && curr < arr.count {
27             stack.append(arr[curr])
28             flatternCurrentStack()
29             curr += 1
30         }
31         return !stack.isEmpty
32     }
33 }

60ms

 1 struct Stack<T>
 2 {
 3     var elements:[T] = []
 4     mutating func push(_ item:T)
 5     {
 6         elements.append(item)
 7     }
 8     mutating func pop() -> T
 9     {
10        return elements.removeLast() 
11     }
12     func isEmpty() -> Bool
13     {
14         return elements.isEmpty
15     }
16     func peek() -> T
17     {
18        return elements.last!
19     }
20 }
21 class NestedIterator {
22 
23    var stk = Stack<NestedInteger>()
24     init(_ nestedList: [NestedInteger]) {
25       for ni in stride(from:nestedList.count - 1, through:0, by: -1)
26         {
27             stk.push(nestedList[ni])
28         }
29     }
30     
31     func next() -> Int {
32         return stk.pop().getInteger()
33     }
34     
35     func hasNext() -> Bool {
36         
37         if stk.isEmpty()
38         {
39             return false
40         }
41         
42        while !stk.isEmpty(){ 
43         
44         var top = stk.peek()
45         if top.isInteger()
46         {
47             return true
48         }
49         else
50         {
51             stk.pop()
52             
53             var list = top.getList()
54             
55             for ni in stride(from:list.count - 1, through:0, by: -1)
56             {
57                 stk.push(list[ni])
58             }
59 
60         }
61        }
62         return false        
63     }
64 }

64ms

 1 class NestedIterator {
 2 
 3     var queue = [Int]()
 4     
 5     init(_ nestedList: [NestedInteger]) {
 6         makeQueue(nestedList)
 7     }
 8     
 9     func next() -> Int {
10         return queue.removeFirst()
11     }
12     
13     func hasNext() -> Bool {
14         return !queue.isEmpty
15     }
16     
17     func makeQueue(_ nestedList: [NestedInteger]) {
18         for n in nestedList {
19             if n.isInteger() { queue.append(n.getInteger()) }
20             else { makeQueue(n.getList()) }
21         }
22     }
23 }

68ms

 1 class NestedIterator {
 2  
 3     var stack : [NestedInteger]
 4     init(_ nestedList: [NestedInteger]) {
 5         stack = []
 6         append(nestedList)
 7     }
 8     
 9     func next() -> Int {
10         var last = stack.first!
11         stack.removeFirst()
12         return last.getInteger()
13         
14     }
15     
16     func append(_ nestedList: [NestedInteger]){
17         for ni in  nestedList{
18             if ni.isInteger(){
19                 stack.append(ni)
20             } else{
21                 append(ni.getList())
22             }
23         }
24     }
25     func hasNext() -> Bool {
26         guard stack.count > 0 else{
27             return false
28         }
29         return true
30     }
31 }

72ms

 1 class NestedIterator {
 2 
 3     init(_ nestedList: [NestedInteger]) {
 4         q =  [NestedInteger]()
 5         for a in nestedList {
 6             q.append(a)
 7         }
 8     }
 9     
10     func next() -> Int {
11         return q.removeFirst().getInteger()
12     }
13     
14     func hasNext() -> Bool {
15         while !q.isEmpty {
16             let t = q.first!
17             if t.isInteger() { return true }
18             q.removeFirst()
19             for a in t.getList().reversed() {
20                 q.insert(a, at: 0)
21             }
22         }
23         return false
24     }
25     private var q: [NestedInteger]
26 }

76ms

 1 class NestedIterator {
 2 
 3     var flattendList: [Int]!
 4     
 5     init(_ nestedList: [NestedInteger]) {
 6         flattendList = flatten(nestedList)
 7     }
 8     
 9     func flatten(_ list: [NestedInteger]) -> [Int] {
10         var flatList: [Int] = []
11         
12         for content in list {
13             if content.isInteger() { flatList.append(content.getInteger()) }
14             // else { flatList += NestedIterator(content.getList()).flattendList }
15             else { flatList += flatten(content.getList()) }
16         }
17         
18         return flatList
19     }
20     
21     func next() -> Int {
22         return flattendList.removeFirst()
23     }
24     
25     func hasNext() -> Bool {
26         return !flattendList.isEmpty
27     }
28 }

80ms

 1 class NestedIterator {
 2     
 3     var data = [Int]()
 4 
 5     init(_ nestedList: [NestedInteger]) {
 6         self.flattenList(nestedList)
 7     }
 8     
 9     func next() -> Int {
10         return self.data.removeFirst()
11     }
12     
13     func hasNext() -> Bool {
14         return self.data.count > 0
15     }
16     
17     private func flattenList(_ nestedList:[NestedInteger]){
18         for n in nestedList{
19             if n.isInteger(){
20                 self.data.append(n.getInteger())
21             }else{
22                 self.flattenList(n.getList())
23             }
24         }
25     }
26 }