LeetCode 641: Круглый дизайн Deque

Question

Я публикую решение для LeetCode "Design Circular Deque". Если вы хотите просмотреть, сделайте это. Спасибо!

Проблема

Разработайте свою реализацию круговой двусторонней очереди (deque).

Ваша реализация должна поддерживать следующие операции:

• MyCircularDeque(k): Конструктор, установите размер двухсторонней очереди равным k.
• insertFront(): Добавляет элемент в начало Deque. Верните true, если операция прошла успешно.
• insertLast(): Добавляет элемент в конец Deque. Верните true, если операция прошла успешно.
• deleteFront(): Удаляет элемент из передней части Deque. Верните true, если операция прошла успешно.
• deleteLast(): Удаляет элемент из задней части Deque. Верните true, если операция прошла успешно.
• getFront(): Получает передний элемент из Deque. Если двухсторонняя очередь пуста, верните -1.
• getRear(): Получает последний элемент из Deque. Если двухсторонняя очередь пуста, верните -1.
• isEmpty(): Проверяет, пуста ли Deque.
• isFull(): Проверяет, заполнен Deque или нет.

Пример:

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);            // return true
circularDeque.insertLast(2);            // return true
circularDeque.insertFront(3);           // return true
circularDeque.insertFront(4);           // return false, the queue is full
circularDeque.getRear();            // return 2
circularDeque.isFull();             // return true
circularDeque.deleteLast();         // return true
circularDeque.insertFront(4);           // return true
circularDeque.getFront();           // return 4

Заметка:

• Все значения будут в диапазоне [0, 1000].
• Количество операций будет в диапазоне [1, 1000].
• Пожалуйста, не используйте встроенную библиотеку Deque.

Код:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

struct MyCircularDeque {
        MyCircularDeque(int k): stream(k, 0), counts(0), k(k), head(k - 1), tail(0) {}

        const bool insertFront(
            const int value
        ) {
            if (isFull()) {
                return false;
            }

            stream[head] = value;
            --head;
            head += k;
            head %= k;
            ++counts;

            return true;
        }

        const bool insertLast(const int value) {
            if (isFull()) {
                return false;
            }

            stream[tail] = value;
            ++tail;
            tail %= k;
            ++counts;

            return true;
        }

        const bool deleteFront() {
            if (isEmpty()) {
                return false;
            }

            ++head;
            head %= k;
            --counts;

            return true;
        }

        const bool deleteLast() {
            if (isEmpty()) {
                return false;
            }

            --tail;
            tail += k;
            tail %= k;
            --counts;

            return true;
        }

        const int getFront() {
            return isEmpty() ? -1 : stream[(head + 1) % k];
        }

        const int getRear() {
            return isEmpty() ? -1 : stream[(tail - 1 + k) % k];
        }

        const bool isEmpty() {
            return !counts;
        }

        const bool isFull() {
            return counts == k;
        }

    private:
        using ValueType = std::uint_fast16_t;
        std::vector<ValueType> stream;
        ValueType counts;
        ValueType k;
        ValueType head;
        ValueType tail;
}; 

Answer 1

• Использование одного и того же типа для содержимого двухсторонней очереди и размеров / индексов ( k, count, head, tail) кажется неправильным. По крайней мере, так kи countдолжно быть std::vector::size_type.

• Так как вы резервное копирование Deque с std::vector, что делает headи tailчто std::vector::iteratorвыглядит более идиоматических.

• kне самое описательное имя. Посмотрим capacity.

• Я не уверен, что std::vectorэто лучший контейнер для резервного копирования двухсторонней очереди фиксированного размера. В конце концов, смысл в std::vectorтом, чтобы иметь динамический размер. std::array, или даже простой старый массив в стиле C, выглядит более естественно.

Answer 2

Вы можете вызвать stream.reserve(k)конструктор, чтобы повысить эффективность вектора, потому что вы знаете, что у вас будут только kэлементы, поэтому .reserve()память будет предварительно выделена.

Предпочитает использование std::size_tболееint
int k быstd::size_t k

Вы не объявлен конструктор копирования , ни оператор присваивания копии . Это может вызвать проблемы, если вы хотите назначить одно Dequeдругому.

Встраивание некоторых функций - членов вашей structLike isEmpty(), getRear(), getFront() может улучшить производительность вашего контейнера, но это будет торговлей в космос.

Если вы делаете это с единственной целью - выполнить задание, вы можете проигнорировать следующую часть.

Шаблоны

Прямо сейчас ваш dequeобязательно использовать std::uint_fast16_t. Но что, если я захочу составить список dequeимен? Или с dequeразными десятичными значениями? Я не могу просто создать по 15 классов для каждого типа данных.

Следовательно, я буду использовать шаблоны на C ++, чтобы создать общий deque .

Синтаксис прост

template < typename T >
struct deque
{
    public:
        // public member functions
    private:
        std::vector< T > stream;
};

Теперь, когда вы хотите создать новую двухстороннюю очередь, вы можете это сделать deque<any_data_type> my_deque.

Где бы вы ни использовали ValueType, вы заменяете его на T.

Что делает C ++, так это то, что он принимает any_data_typeи заменяет Tэтот тип данных во время компиляции . Реализация этого в вашей программе научит вас многому о том, как работают шаблоны в C ++, что будет полезно в ваших будущих проектах.

Шаблоны на C ++

Answer 3

Я думаю, что это тема для вашего кода: там const, где вы ее разместили, пользы нет; и он отсутствует в других местах, где он должен быть. Каждая входящая функция MyCircularDequeдолжна выпадать constвперед, потому что эти возвращаемые значения являются скалярными, поэтому их маркировка constпрактически не имеет никакого эффекта. insertLast(const int value)имеет немного больший эффект, но на самом деле не важен.

Самое важное место , чтобы положить constэто изменить константную-ность thisдля getи isметодов. Их нужно constдобавить после скобок. Это регистрирует обещание, что методы не изменяют никаких членов.