LeetCode 341. Flatten Nested List Iterator

mingzhong 发布于2019-07-31 10:16 / 2444人阅读

摘要：设计一个迭代器，使其能够遍历这个整型列表中的所有整数。列表中的项或者为一个整数，或者是另一个列表。示例输入输出解释通过重复调用直到返回，返回的元素的顺序应该是。

Description

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:

Input: [[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: [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].

描述

给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的项或者为一个整数，或者是另一个列表。

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:

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

思路

递归遍历，使用双端队列，取出每一个元素，放入到队列中

如果当前的元素是整型（使用自带的 isInteger 方法），将当前元素放入到队列中，如果是 List，递归调用当前函数。

next 方法从队列中不断取出元素

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-04-08 14:01:53
# @Last Modified by:   何睿
# @Last Modified time: 2019-04-08 14:45:23

from collections import deque


class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        self.queue = deque()
        # 遍历得到所有的元素
        self._get_elements(nestedList)
        # 统计元素的个数
        self.count = len(self.queue)

    def _get_elements(self, nestedList):
        for item in nestedList:
            # isInteger 方法是 NestedIterator 类提供的方法
            # 如果是整型，将该数组添加到双端队列中
            if item.isInteger():
                self.queue.append(item.getInteger())
                # 如果是一个 List ，递归调用 _get_elements
            else:
                self._get_elements(item.getList())
        return

    def next(self):
        """
        :rtype: int
        """
        hasnext = self.hasNext()
        if hasnext:
            self.count -= 1
            # 返回下一个元素
            return self.queue.popleft()
        return False

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.count > 0

源代码文件在这里。
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.

云服务器私有云 Flatten okhttp341 Nested Iterator

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43534.html

leetcode341. Flatten Nested List Iterator

摘要：题目要求假设有一个嵌套形式的数组，要求按照顺序遍历数组中的元素。思路和代码首先可以想到通过深度优先递归的方式将嵌套形式的数组展开为一个无嵌套的列表。题目要求 Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a lis...

MartinHan 2019-08-15 15:54 评论0 收藏0
leetcode 341 Flatten Nested List Iterator 以及其他Iter

摘要：返回的是表示是否走到了结尾。起到的就是缓存作用，因为调用之后马上就走到下一个了。如果调用，返回用得到和最初的输入相同的做相同的步骤存入不断拆开得到结果。思想就是来自括号，后面也会跟进的专题 Iterator其实就是一个单链表，无法回头看。java里很多数据结构都有这个接口，使用时需要initalize,得到一个iterator. 调用next()返回的是一个object, 指向的是下一...

chaosx110 2019-08-14 18:00 评论0 收藏0
[LintCode/LeetCode] Flatten Nested List Iterator

摘要：首先，根据迭代器需要不断返回下一个元素，确定用堆栈来做。堆栈初始化数据结构，要先从后向前向堆栈压入中的元素。在调用之前，先要用判断下一个是还是，并进行的操作对要展开并顺序压入对直接返回。 Problem Given a nested list of integers, implement an iterator to flatten it. Each element is either...

spacewander 2019-08-14 15:45 评论0 收藏0
[Leetcode] Flatten 2D Vector 整平二维向量

摘要：另一个则是的迭代器，它负责记录当前到哪一个的迭代器了。每次时，我们先调用一下，确保当前的迭代器有下一个值。代码当前列表的迭代器为空，或者当前迭代器中没有下一个值时，需要更新为下一个迭代器 Flatten 2D Vector Implement an iterator to flatten a 2d vector. For example, Given 2d vector = [ ...

MageekChiu 2019-08-14 12:36 评论0 收藏0
[LeetCode] 251. Flatten 2D Vector

Problem Implement an iterator to flatten a 2d vector. Example: Input: 2d vector = [ [1,2], [3], [4,5,6] ] Output: [1,2,3,4,5,6] Explanation: By calling next repeatedly until hasNext returns fals...

curried 2019-08-16 13:30 评论0 收藏0