엔지니어 게시판
LeetCode 솔루션 분류

[5/8] 341. Flatten Nested List Iterator

컨텐츠 정보

본문

[LeetCode 시즌 3] 2022년 5월 8일 문제입니다.

https://leetcode.com/problems/flatten-nested-list-iterator/


341. Flatten Nested List Iterator
Medium
31121092Add to ListShare

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

  • NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
  • int next() Returns the next integer in the nested list.
  • boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

 

Example 1:

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

 

Constraints:

  • 1 <= nestedList.length <= 500
  • The values of the integers in the nested list is in the range [-106, 106].

관련자료

댓글 3

austin님의 댓글

  • 익명
  • 작성일
class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        auto build = [&](auto &self, vector<NestedInteger> &l) -> void{
          for(auto &n : l) {
              if (n.isInteger()) v.emplace_back(n.getInteger());
              else self(self, n.getList());
          }
        };
        build(build, nestedList);
        cur = v.begin();
    }
    
    int next() {
        return *cur++;
    }
    
    bool hasNext() {
        return !(cur == v.end());
        
    }
    vector<int> v;
    vector<int>::iterator cur;
};

mingki님의 댓글

  • 익명
  • 작성일
C++
Runtime: 20 ms, faster than 51.39% of C++ online submissions for Flatten Nested List Iterator.
Memory Usage: 12.8 MB, less than 93.05% of C++ online submissions for Flatten Nested List Iterator.
class NestedIterator {
private:
    vector<int> arr;
    int idx;
    
    void unwrap(NestedInteger &ni) {
        if (ni.isInteger()) {
            arr.push_back(ni.getInteger());
        }
        else {
            for (auto &elem : ni.getList()) {
                unwrap(elem);
            }
        }
    }
    
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        idx = 0;
        for (auto &elem : nestedList) {
            unwrap(elem);
        }
    }
    
    int next() {
        return arr[idx++];
    }
    
    bool hasNext() {
        return idx < arr.size();
    }
};

나무토끼님의 댓글

  • 익명
  • 작성일
Runtime: 97 ms
Memory Usage: 17.9 MB
class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.iterator = 0
        self.tempList = []
        self.nestedList = nestedList
        self.dfs_making_list(0, self.nestedList)
        
    def dfs_making_list(self, idx, lst):
        if idx < len(lst) and lst[idx]._integer != None:
            self.tempList.append(lst[idx]._integer)
            self.dfs_making_list(idx + 1, lst)
        elif idx >= len(lst):
            return
        else:
            self.dfs_making_list(0, lst[idx]._list)
            self.dfs_making_list(idx + 1, lst)
            
            
    
    def next(self) -> int:
        t = self.tempList[self.iterator]
        self.iterator += 1
        return t
    
    def hasNext(self) -> bool:
        if self.iterator < len(self.tempList):
            return True
        else:
            return False
전체 396 / 8 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 176 명
  • 오늘 방문자 3,033 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,047 명
알림 0