36ms accepted c++ solution


  • 0
    W
    class NestedIterator {
    private:
    	vector<NestedInteger>& v;
    	vector<int> nextIdx; // an index contains many sub-indices for every level 
    
    	NestedInteger* getNi() {
    		if (nextIdx.empty()) return NULL;
    		NestedInteger* ni = &v[nextIdx[0]];
    		for (int i = 1; i < nextIdx.size(); ++i)
    		{
    			ni = (NestedInteger*)&(ni->getList()[nextIdx[i]]);
    		}
    		return ni;
    	}
    
    	void updateNextIdx() {
    		if (nextIdx.empty()) return; // failure
    
    		while (1) {
    			int i = nextIdx.back();
    			nextIdx.pop_back();
    
    			NestedInteger* pni = getNi();
    			NestedInteger* ni = NULL;
    
    			i += 1;
    			if (pni == NULL) {
    				if (i >= v.size()) return; // end
    				nextIdx.push_back(i);
    				ni = &v[i];
    			}
    			else {
    				if (i >= pni->getList().size()) continue; // this level is done
    				nextIdx.push_back(i);
    				ni = (NestedInteger*)&(pni->getList()[i]);
    			}
    
    			if (ni->isInteger()) break; // success
    
    			while (!ni->isInteger())
    			{
    				if (ni->getList().empty()) break; // this level is done
    
    				nextIdx.push_back(0);
    				ni = (NestedInteger*)&(ni->getList()[0]);
    				if (ni->isInteger()) return; // success
    			}
    		}
    	}
    
    public:
    	NestedIterator(vector<NestedInteger>& nestedList) :v(nestedList) {
    		if (!nestedList.empty()) {
    			nextIdx.push_back(-1);
    			updateNextIdx();
    		}
    	}
    
    	int next() {
    		assert(!nextIdx.empty());
    		int ret;
    		NestedInteger* ni = getNi();
    		assert(ni->isInteger());
    		ret = ni->getInteger();
    		updateNextIdx();
    		return ret;
    	}
    
    	bool hasNext() {
    		return !nextIdx.empty();
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.