LeetCode 341. Flatten Nested List Iterator

简介: 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。列表中的项或者为一个整数,或者是另一个列表。

v2-f94bbfe06f5dd613ce9a1731b64e8cce_1440w.jpg

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

源代码文件在 这里


目录
相关文章
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
44 1
|
C++
Leetcode Copy List with Random Pointer(面试题推荐)
给大家推荐一道leetcode上的面试题,这道题的具体讲解在《剑指offer》的P149页有思路讲解,如果你手头有这本书,建议翻阅。
50 0
Leetcode 19.Remove Nth Node From End of List
删除单链表中的倒数第n个节点,链表中删除节点很简单,但这道题你得先知道要删除哪个节点。在我的解法中,我先采用计数的方式来确定删除第几个节点。另外我在头节点之前额外加了一个节点,这样是为了把删除头节点的特殊情况转换为一般情况,代码如下。
37 0
|
6月前
list转迭代器Iterator
list转迭代器Iterator
|
6月前
|
大数据 Java 程序员
「LeetCode合集」链表(List)及经典问题
「LeetCode合集」链表(List)及经典问题
51 0
LeetCode 141. 环形链表 Linked List Cycle
LeetCode 141. 环形链表 Linked List Cycle
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree
LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 206. 反转链表 Reverse Linked List
LeetCode 206. 反转链表 Reverse Linked List