341. Flatten Nested List Iterator

LeetCode medium оригинал: C# #csharp #design #leetcode #medium #queue #stack

LeetCode Static

Вам дан вложенный список целых чисел nestedList. Каждый элемент либо является целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Реализуйте итератор для его развёртки.

Реализуйте класс NestedIterator:

NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList.

int next() Возвращает следующий целый элемент вложенного списка.

boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае.

Пример

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].

C# решение

сопоставлено/оригинал

public class NestedIterator {
    private Stack<NestedInteger> stack;
    
    public NestedIterator(IList<NestedInteger> nestedList) {
        stack = new Stack<NestedInteger>();
        Flatten(nestedList);
    }
    
    private void Flatten(IList<NestedInteger> nestedList) {
        for (int i = nestedList.Count - 1; i >= 0; i--) {
            stack.Push(nestedList[i]);
        }
    }
    
    public int Next() {
        return stack.Pop().GetInteger();
    }
    
    public bool HasNext() {
        while (stack.Count > 0 && !stack.Peek().IsInteger()) {
            Flatten(stack.Pop().GetList());
        }
        return stack.Count > 0;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class NestedIterator {
    private stack<NestedInteger> stack;
    
    public NestedIterator(IList<NestedInteger> nestedList) {
        stack = new stack<NestedInteger>();
        Flatten(nestedList);
    }
    
    private void Flatten(IList<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList[i]);
        }
    }
    
    public int Next() {
        return stack.pop().GetInteger();
    }
    
    public bool HasNext() {
        while (stack.size() > 0 && !stack.Peek().IsInteger()) {
            Flatten(stack.pop().GetList());
        }
        return stack.size() > 0;
    }
}

Java решение

сопоставлено/оригинал

public class NestedIterator implements Iterator<Integer> {
    private Stack<NestedInteger> stack;
    
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        flatten(nestedList);
    }
    
    private void flatten(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }
    
    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }
    
    @Override
    public boolean hasNext() {
        while (!stack.isEmpty() && !stack.peek().isInteger()) {
            flatten(stack.pop().getList());
        }
        return !stack.isEmpty();
    }
}

JavaScript решение

сопоставлено/оригинал

var NestedIterator = function(nestedList) {
    this.stack = [];
    this.flatten(nestedList);
};

NestedIterator.prototype.flatten = function(nestedList) {
    for (let i = nestedList.length - 1; i >= 0; i--) {
        this.stack.push(nestedList[i]);
    }
};

NestedIterator.prototype.next = function() {
    return this.stack.pop().getInteger();
};

NestedIterator.prototype.hasNext = function() {
    while (this.stack.length > 0 && !this.stack[this.stack.length - 1].isInteger()) {
        this.flatten(this.stack.pop().getList());
    }
    return this.stack.length > 0;
};

Python решение

сопоставлено/оригинал

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        self._flatten(nestedList)
    
    def _flatten(self, nestedList):
        for ni in reversed(nestedList):
            self.stack.append(ni)
    
    def next(self) -> int:
        return self.stack.pop().getInteger()
    
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            self._flatten(self.stack.pop().getList())
        return bool(self.stack)

Go решение

сопоставлено/оригинал

type NestedIterator struct {
    stack []*NestedInteger
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
    it := &NestedIterator{}
    it.flatten(nestedList)
    return it
}

func (this *NestedIterator) flatten(nestedList []*NestedInteger) {
    for i := len(nestedList) - 1; i >= 0; i-- {
        this.stack = append(this.stack, nestedList[i])
    }
}

func (this *NestedIterator) Next() int {
    return this.stack[len(this.stack)-1].GetInteger()
}

Algorithm

Инициализация

Сохраняйте исходный вложенный список в стеке или очереди. Используйте стек для сохранения состояния итерации по вложенным спискам.

Метод next()

Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек.

Метод hasNext()

Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.