给你一个嵌套的 NSArray 数据,实现一个迭代器类,该类提供一个 next() 方法,可以依次的取出这个 NSArray 中的数据。 比如 NSArray 如果是 `[1,[4,3],6,[5,[1,0]]]`, 则最终应该输出:`1, 4, 3, 6, 5, 1, 0` 。 另外,实现一个 `allObjects` 方法,可以一次性取出所有元素。
// | |
// AlgorithmSolutionCode | |
// | |
// Created by TangQiao on 12/13/16. | |
// Copyright © 2016 Tang Qiao. All rights reserved. | |
// | |
#import <Foundation/Foundation.h> | |
@interface NSArrayIterator : NSObject | |
- (id)initWithArray:(NSArray *)array; | |
- (id)next; | |
- (NSArray *)allObjects; | |
@end |
// | |
// AlgorithmSolutionCode | |
// | |
// Created by TangQiao on 12/13/16. | |
// Copyright © 2016 Tang Qiao. All rights reserved. | |
// | |
#import "NSArrayIterator.h" | |
@interface NSArrayIteratorCursor : NSObject | |
@property (nonatomic) NSArray *array; | |
@property (nonatomic) NSUInteger index; | |
@end | |
@implementation NSArrayIteratorCursor | |
- (id)initWithArray:(NSArray *)array { | |
self = [super init]; | |
if (self) { | |
_array = array; | |
_index = 0; | |
} | |
return self; | |
} | |
@end | |
@implementation NSArrayIterator { | |
NSMutableArray *_stack; | |
NSArray *_originArray; | |
} | |
- (id)initWithArray:(NSArray *)array { | |
self = [super init]; | |
if (self) { | |
_originArray = array; | |
_stack = [NSMutableArray array]; | |
[self setupStackWithArray:array]; | |
} | |
return self; | |
} | |
- (void)setupStackWithArray:(NSArray *)array { | |
NSArrayIteratorCursor *c = [[NSArrayIteratorCursor alloc] initWithArray:array]; | |
[_stack addObject:c]; | |
} | |
- (id)next { | |
// 1. 判断栈是否为空,如果为空则返回 nil。 | |
if (_stack.count == 0) { | |
return nil; | |
} | |
// 2. 从栈中取出元素,看是否遍历到了结尾,如果是的话,则出栈。 | |
NSArrayIteratorCursor *c; | |
c = [_stack lastObject]; | |
while (c.index == c.array.count && _stack.count > 0) { | |
[_stack removeLastObject]; | |
c = [_stack lastObject]; | |
} | |
// 3. 判断第2步是否使栈为空,如果为空,则返回 nil。 | |
if (_stack.count == 0) { | |
return nil; | |
} | |
// 4. 终于拿到元素了,这一步判断拿到的元素是否是数组。 | |
id item = c.array[c.index]; | |
if ([item isKindOfClass:[NSArray class]]) { | |
c.index++; | |
// 5. 如果是数组,则重新生成一个遍历的 | |
// NSArrayIteratorCursor 对象,放到栈中, 然后递归调用 next 方法 | |
[self setupStackWithArray:item]; | |
return [self next]; | |
} | |
// 6. 如果到了这一步,说明拿到了一个非数组的元素,这样就可以把元素返回, | |
// 同时更新索引到下一个位置。 | |
c.index++; | |
return item; | |
} | |
- (NSArray *)allObjects { | |
NSMutableArray *result = [NSMutableArray array]; | |
[self fillArray:_originArray into:result]; | |
return result; | |
} | |
- (void)fillArray:(NSArray *)array into:(NSMutableArray *)result { | |
for (id item in array) { | |
if ([item isKindOfClass:[NSArray class]]) { | |
[self fillArray:item into:result]; | |
} else { | |
[result addObject:item]; | |
} | |
} | |
} | |
@end |
// | |
// NSArrayIteratorTest.m | |
// AlgorithmSolutionCode | |
// | |
// Created by TangQiao on 12/13/16. | |
// Copyright © 2016 Tang Qiao. All rights reserved. | |
// | |
#import <XCTest/XCTest.h> | |
#import "NSArrayIterator.h" | |
@interface NSArrayIteratorTest : XCTestCase | |
@end | |
@implementation NSArrayIteratorTest | |
- (void)testNext { | |
NSArray *arr = @[@1, @2, @[ @[ @5], @3, @4], @[@6, @7, @[ @[ @[ @8 ]]]]]; | |
NSArrayIterator *c = [[NSArrayIterator alloc] initWithArray:arr]; | |
XCTAssertEqualObjects(@1, [c next]); | |
XCTAssertEqualObjects(@2, [c next]); | |
XCTAssertEqualObjects(@5, [c next]); | |
XCTAssertEqualObjects(@3, [c next]); | |
XCTAssertEqualObjects(@4, [c next]); | |
XCTAssertEqualObjects(@6, [c next]); | |
XCTAssertEqualObjects(@7, [c next]); | |
XCTAssertEqualObjects(@8, [c next]); | |
XCTAssertEqualObjects(nil, [c next]); | |
XCTAssertEqualObjects(nil, [c next]); | |
} | |
- (void)testEmptyNestedArray { | |
NSArray *arr = @[@1, @2, @[ @[ ], @3, @4, @[]], @[@6, @7, @[ @[ @[ @8 ]]]]]; | |
NSArrayIterator *c = [[NSArrayIterator alloc] initWithArray:arr]; | |
XCTAssertEqualObjects(@1, [c next]); | |
XCTAssertEqualObjects(@2, [c next]); | |
XCTAssertEqualObjects(@3, [c next]); | |
XCTAssertEqualObjects(@4, [c next]); | |
XCTAssertEqualObjects(@6, [c next]); | |
XCTAssertEqualObjects(@7, [c next]); | |
XCTAssertEqualObjects(@8, [c next]); | |
XCTAssertEqualObjects(nil, [c next]); | |
XCTAssertEqualObjects(nil, [c next]); | |
} | |
- (void)testEmptyArray { | |
NSArray *arr = @[ @[ @[ ]], @[@[ @[ @[ ]]]]]; | |
NSArrayIterator *c = [[NSArrayIterator alloc] initWithArray:arr]; | |
XCTAssertEqualObjects(nil, [c next]); | |
XCTAssertEqualObjects(nil, [c next]); | |
} | |
- (void)testAllObjects { | |
NSArray *arr = @[@1, @2, @[ @[ @5], @3, @4], @[@6, @7, @[ @[ @[ @8 ]]]]]; | |
NSArray *expect = @[@1, @2, @5, @3, @4, @6, @7, @8]; | |
NSArrayIterator *c = [[NSArrayIterator alloc] initWithArray:arr]; | |
XCTAssertEqualObjects(expect, [c allObjects]); | |
} | |
@end |
This comment has been minimized.
This comment has been minimized.
@haoero 我觉得是可以的。你的方法和我类似,不过你把数组内容多展开了一维(把数据元素放到stack中了),这样stack里面的东西会稍多一些。 |
This comment has been minimized.
This comment has been minimized.
我也自己实现了一个next,和你们的方法思路不太一样。我会维护一个游标curser和一个是否打印的标记变量flag。遍历过程中如果curser==current一样了,就是到了目标位置的上一个number,那么设置一下flag = YES,下次到了number 的时候就给拿出来。自己觉得这个思路挺简单的,不用维护一个栈,只是在递归调用的路上加了两个变量,找到next object。 |
This comment has been minimized.
This comment has been minimized.
我觉得在初始化时 就调用
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
唐大神,我刚看了你的博文,然后我之前刚好写过一个类似的,实现方法有点类似,但是跟你的有一点不同,我用了一个辅助的hasNext方法,麻烦帮忙看一下可行否?
https://github.com/haoero/NSNestedNumberEnumerator