LeetCode 641: Design Circular Deque

Question

Wysyłam rozwiązanie dla „Design Circular Deque” LeetCode. Jeśli chcesz przejrzeć, zrób to. Dziękuję Ci!

Problem

Zaprojektuj implementację okrągłej kolejki dwustronnej (deque).

Twoja implementacja powinna wspierać następujące operacje:

• MyCircularDeque(k): Constructor, ustaw rozmiar deque na k.
• insertFront(): Dodaje element z przodu Deque. Zwróć wartość true, jeśli operacja się powiedzie.
• insertLast(): Dodaje element z tyłu Deque. Zwróć wartość true, jeśli operacja się powiedzie.
• deleteFront(): Usuwa element z przodu Deque. Zwróć wartość true, jeśli operacja się powiedzie.
• deleteLast(): Usuwa element z tyłu Deque. Zwróć wartość true, jeśli operacja się powiedzie.
• getFront(): Pobiera element z przodu z Deque. Jeśli deque jest pusty, zwraca -1.
• getRear(): Pobiera ostatni element z Deque. Jeśli deque jest pusty, zwraca -1.
• isEmpty(): Sprawdza, czy Deque jest pusty, czy nie.
• isFull(): Sprawdza, czy Deque jest pełny, czy nie.

Przykład:

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

Uwaga:

• Wszystkie wartości będą w zakresie [0, 1000].
• Liczba operacji będzie się mieścić w przedziale [1, 1000].
• Nie używaj wbudowanej biblioteki Deque.

Kod:

// 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

• Używanie tego samego typu dla zawartości deque i rozmiarów / indeksów ( k, count, head, tail) wydaje się niewłaściwe. Przynajmniej ki countpowinno być std::vector::size_type.

• Ponieważ jesteś kopii zapasowej z deque std::vector, co czyni headi tailto std::vector::iteratorwygląda bardziej idiomatyczne.

• knie jest najbardziej opisową nazwą. Rozważ capacity.

• Nie jestem pewien, czy std::vectorjest to najlepszy kontener do tworzenia kopii zapasowych o stałym rozmiarze. W końcu chodzi o std::vectorto, aby mieć rozmiar dynamiczny. std::arraylub nawet zwykła stara tablica w stylu C wygląda bardziej naturalnie.

Answer 2

Możesz wywołać stream.reserve(k)konstruktor, aby poprawić wydajność wektora, ponieważ wiesz, że będziesz mieć tylko kelementy, więc .reserve()wstępnie przydzieli pamięć.

Wolisz używać std::size_tponadint
int k byłobystd::size_t k

Nie zadeklarowałeś konstruktora kopiującego ani operatora przypisania kopii . Może to powodować problemy, jeśli chcesz przypisać jeden Dequedo drugiego.

Inline niektórych funkcji członka Twojej structLike isEmpty(), getRear(), getFront() można poprawić wydajność swojego pojemnika, ale będzie to handel na przestrzeni.

Jeśli robisz to wyłącznie w celu ukończenia wyzwania, możesz zignorować następną część

Szablony

W tej chwili twój dequejest zobowiązany do użycia std::uint_fast16_t. Ale co jeśli chciałbym stworzyć dequenazwiska? A może dequeróżne wartości dziesiętne? Nie mogę po prostu utworzyć 15 klas dla każdego typu danych.

Dlatego będę używał szablonów w C ++, aby móc stworzyć generyczny deque .

Składnia jest prosta

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

Teraz, gdy chcesz utworzyć nowy deque, możesz to zrobić deque<any_data_type> my_deque.

Gdziekolwiek byś użył ValueType, zamień go na T.

C ++ robi to, że pobiera any_data_typei zamienia Tten typ danych podczas kompilacji . Wdrożenie tego w swoim programie nauczy Cię wiele o tym, jak działają szablony w C ++, co będzie pomocne w przyszłych projektach.

Szablony w C ++

Answer 3

Myślę, że to jest motyw twojego kodu: consttam, gdzie to umieściłeś, nie ma żadnych korzyści; i brakuje go w innych miejscach, że powinien tam być. Każda funkcja w programie MyCircularDequepowinna porzucić constfront zewnętrzny, ponieważ te zwracane wartości są skalarne, więc oznaczanie ich constdosłownie nie ma żadnego efektu. insertLast(const int value)ma nieco większy efekt, ale tak naprawdę nie jest ważne.

Najważniejszym miejscem umieścić constjest modyfikacja const-ności thisdla swoich getand ismetod. Muszą constdodać po nawiasach. To rejestruje obietnicę, że metody nie modyfikują żadnych członków.