首页 > 其他 > 详细

LeetCode "Flatten Nested List Iterator"

时间:2016-04-06 07:03:18      阅读:239      评论:0      收藏:0      [点我收藏+]

Besides the common stack-based solutions, here is another recursive NestedIterator solution :)

class NestedIterator 
{
    int currInx;
    const vector<NestedInteger> &rData;    
    NestedIterator *sub;

    void move()
    {
        if (currInx < 0 || rData[currInx].isInteger() || !sub->hasNext())
        {
            if ((++currInx) < rData.size())
            {    
                releaseSub();
                if (!rData[currInx].isInteger())
                {
                    // get next non-empty list
                    while (currInx < rData.size() &&
                            ( sub = new NestedIterator(const_cast<vector<NestedInteger>&>(rData[currInx].getList())),
                              (!rData[currInx].isInteger() && sub && !sub->hasNext())) )
                    {
                        currInx++;
                        releaseSub();
                    }
                }
            }
        }
        else
        {
            sub->move();
        }
    }
    //
    NestedIterator() 
        :rData(vector<NestedInteger>()), currInx(-1), sub(nullptr)
    { }

    void releaseSub()
    {
        delete sub;    sub = nullptr;
    }
    
public:
    ~NestedIterator()
    {
        releaseSub();
    }
    
    NestedIterator(vector<NestedInteger> &nestedList) 
        :rData(nestedList), currInx(-1), sub(nullptr)
    {
        move();
    }

    int next() 
    {
        int val = 0;
        if (rData[currInx].isInteger())
        {
            val = rData[currInx].getInteger();
            move();
        }
        else
        {
            val = sub->next();
            if (!sub->hasNext()) move();
        }        
        return val;
    }

    bool hasNext() 
    {
        return currInx < rData.size() && (rData[currInx].isInteger() || sub->hasNext());
    }
};

 

LeetCode "Flatten Nested List Iterator"

原文:http://www.cnblogs.com/tonix/p/5357664.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!