[LeetCode] 251. Flatten 2D Vector

251. Flatten 2D Vector

Medium

602338Add to ListShare

Design an iterator to flatten a 2D vector. It should support the next and hasNext operations.

Implement the Vector2D class:

• Vector2D(int[][] vec) initializes the object with the 2D vector vec.
• next() returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls to next are valid.
• hasNext() returns true if there are still some elements in the vector, and false otherwise.

 

Example 1:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

 

Constraints:

• 0 <= vec.length <= 200
• 0 <= vec[i].length <= 500
• -500 <= vec[i][j] <= 500
• At most 105 calls will be made to next and hasNext.

 

Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.

 

---

문제 풀이

문제 접근

1. 문제 제한이 타이트하지 않다, 구현 문제 인듯하다.
2. 파이썬의 Flatten 함수를 구현해야한다.
3. Follow up 에 이터레이터를 사용하라고 되어있는데 파이썬이라 패스.

풀이

1. 클래스 초기화 부분에서 1차원 리스트 생성한다.
2. 문제 제한에서 2차원 리스트 안에 1차원 리스트 크기가 0일 수도 있기 때문에 예외 처리한다.
3. 2중 for 문으로 하나씩 넣어준다. [고차원 배열의 경우 재귀사용 필수]
4. next 함수는 hasNext 함수를 사용하여 존재할 경우 답을 임시 저장 후, 인덱스 증가, 그리고 답을 반환한다.
5. hasNext 함수는 초기화에서 만들었던 인덱스(이터레이터 대체)가 리스트 길이를 넘으면 False 리턴, 나머지는 True 반환한다.

---

소스코드

class Vector2D:

    def __init__(self, vec: List[List[int]]):
        self.flatten2D = []
        self.index = 0
        for l in vec:
            if len(l) == 0: continue
            for num in l:
                self.flatten2D.append(num)

    def next(self) -> int:
        if self.hasNext:
            ans = self.flatten2D[self.index]
            self.index += 1
            return ans

    def hasNext(self) -> bool:
        if self.index < len(self.flatten2D):
            return True
        return False


# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(vec)
# param_1 = obj.next()
# param_2 = obj.hasNext()