341. 扁平化嵌套列表迭代器

难度：中等

题目

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

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 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]。

Reference

题解

C语言可以将嵌套列表转换为链表，然后对链表进行迭代：

/**
 * *********************************************************************
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * *********************************************************************
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * bool NestedIntegerIsInteger(struct NestedInteger *);
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * int NestedIntegerGetInteger(struct NestedInteger *);
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The result is undefined if this NestedInteger holds a single integer
 * struct NestedInteger **NestedIntegerGetList(struct NestedInteger *);
 *
 * // Return the nested list's size that this NestedInteger holds, if it holds a nested list
 * // The result is undefined if this NestedInteger holds a single integer
 * int NestedIntegerGetListSize(struct NestedInteger *);
 * };
 */
struct NestedIterator {
    struct ListNode *list;
    struct ListNode *current;
};

struct ListNode *getNode(int val, struct ListNode *next)
{
    struct ListNode *ret = (struct ListNode *)malloc(sizeof(struct ListNode));
    ret->val = val;
    ret->next = next;
    return ret;
}

struct ListNode *toList(struct NestedInteger *src, struct ListNode **tail)
{
    if (NestedIntegerIsInteger(src))
    {
        struct ListNode *ret = getNode(NestedIntegerGetInteger(src), NULL);
        if (tail)
            *tail = ret;
        return ret;
    }
    else
    {
        struct NestedInteger **content = NestedIntegerGetList(src);
        struct ListNode *ret = NULL, *temp = NULL;
        int i = 0, size = NestedIntegerGetListSize(src);
        for (i = 0; i < size; i++)
        {
            if (!ret)
                ret = toList(content[i], &temp);
            else
                (*tail)->next = toList(content[i], &temp);
            if (temp)
                *tail = temp;
        }
        return ret;
    }
}

struct NestedIterator *nestedIterCreate(struct NestedInteger** nestedList, int nestedListSize) {
    struct NestedIterator *ret = (struct NestedIterator *)malloc(sizeof(struct NestedIterator));
    ret->list = NULL;
    ret->current = NULL;
    struct ListNode *temp = NULL;
    for (int i = 0; i < nestedListSize; i++)
    {
        if (!ret->list)
            ret->list = toList(nestedList[i], &temp);
        else
            ret->current->next = toList(nestedList[i], &temp);
        ret->current = temp;
    }
    ret->current = ret->list;
    return ret;
}

bool nestedIterHasNext(struct NestedIterator *iter) {
    return iter->current;
}

int nestedIterNext(struct NestedIterator *iter) {
    int ret = iter->current->val;
    iter->current = iter->current->next;
    return ret;
}

/** Deallocates memory previously allocated for the iterator */
void nestedIterFree(struct NestedIterator *iter) {
    while (iter->list)
    {
        iter->current = iter->list->next;
        free(iter->list);
        iter->list = iter->current;
    }
    free(iter);
}

/**
 * Your NestedIterator will be called like this:
 * struct NestedIterator *i = nestedIterCreate(nestedList, nestedListSize);
 * while (nestedIterHasNext(i)) printf("%d\n", nestedIterNext(i));
 * nestedIterFree(i);
 */

Python语言支持yield语句与yield from语句，因此直接迭代生成器即可

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

def listIter(nestNode):
    for node in nestNode:
        if node.isInteger():
            yield node.getInteger()
        else:
            yield from listIter(node.getList())

class NestedIterator:
    def __init__(self, nestedList):
        self.nextvalue = 0
        self.iterator = listIter(nestedList)

    def next(self):
        return self.nextvalue

    def hasNext(self):
        try:
            self.nextvalue = next(self.iterator)
        except StopIteration:
            return False
        return True

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

评论