LeetCode 641: Design Circular Deque
Ich veröffentliche eine Lösung für LeetCodes "Design Circular Deque". Wenn Sie eine Bewertung abgeben möchten, tun Sie dies bitte. Dankeschön!
Problem
Entwerfen Sie Ihre Implementierung der kreisförmigen Warteschlange mit zwei Enden (deque).
Ihre Implementierung sollte folgende Vorgänge unterstützen:
MyCircularDeque(k): Konstruktor, stellen Sie die Größe der Deque auf k ein.insertFront(): Fügt einen Gegenstand an der Vorderseite von Deque hinzu. Geben Sie true zurück, wenn der Vorgang erfolgreich ist.insertLast(): Fügt einen Gegenstand auf der Rückseite von Deque hinzu. Geben Sie true zurück, wenn der Vorgang erfolgreich ist.deleteFront(): Löscht einen Gegenstand von der Vorderseite von Deque. Geben Sie true zurück, wenn der Vorgang erfolgreich ist.deleteLast(): Löscht einen Gegenstand von der Rückseite von Deque. Geben Sie true zurück, wenn der Vorgang erfolgreich ist.getFront(): Ruft den vorderen Gegenstand aus der Deque ab. Wenn die Deque leer ist, geben Sie -1 zurück.getRear(): Ruft den letzten Gegenstand von Deque ab. Wenn die Deque leer ist, geben Sie -1 zurück.isEmpty(): Überprüft, ob Deque leer ist oder nicht.isFull(): Überprüft, ob Deque voll ist oder nicht.
Beispiel:
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
Hinweis:
- Alle Werte liegen im Bereich von [0, 1000].
- Die Anzahl der Operationen liegt im Bereich von [1, 1000].
- Bitte benutzen Sie nicht die eingebaute Deque-Bibliothek.
Code:
// 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;
};
Antworten
Die Verwendung des gleichen Typs für den Deque-Inhalt und die Größen / Indizes (
k, count, head, tail) fühlt sich falsch an. Zumindestkundcountsollte es seinstd::vector::size_type.Da Sie die Deque mit sichern
std::vector, machenheadundtaildasstd::vector::iteratorsieht idiomatischer aus.kist nicht der aussagekräftigste Name. Überlegen Siecapacity.Ich bin mir nicht sicher, ob dies
std::vectorder beste Behälter ist, um die Deque mit fester Größe zu sichern. Schließlichstd::vectorgeht es darum, eine dynamische Größe zu haben.std::arrayoder sogar ein einfaches altes Array im C-Stil sieht natürlicher aus.
Sie können stream.reserve(k)den Konstruktor aufrufen , um die Effizienz des Vektors zu verbessern, da Sie wissen, dass Sie nur kElemente haben und .reserve()den Speicher vorab zuweisen.
Bevorzugen mit std::size_tüberint
int k wärestd::size_t k
Sie haben weder einen Kopierkonstruktor noch einen Kopierzuweisungsoperator deklariert . Dies kann zu Problemen führen, wenn Sie Dequeeinander zuweisen möchten.
Inlining einige Elementfunktionen Ihres structwie isEmpty(), getRear(), getFront() können Sie die Leistung Ihres Behälters verbessern, aber es wird ein Handel für Raum.
Wenn Sie dies nur zum Abschluss der Herausforderung tun, können Sie den nächsten Teil ignorieren
Vorlagen
Im Moment ist Ihr dequeverpflichtet zu verwenden std::uint_fast16_t. Aber was ist, wenn ich einen dequeNamen machen wollte ? Oder ein dequevon verschiedenen Dezimalwerten? Ich kann nicht einfach 15 Klassen für jeden Datentyp erstellen.
Daher werde ich Vorlagen in C ++ verwenden, damit ich ein generisches erstellen kann deque.
Die Syntax ist einfach
template < typename T >
struct deque
{
public:
// public member functions
private:
std::vector< T > stream;
};
Wenn Sie jetzt eine neue Deque erstellen möchten, können Sie dies tun deque<any_data_type> my_deque.
Wo immer Sie es verwenden würden ValueType, ersetzen Sie es durch T.
Was C ++ tut, ist, dass es während der Kompilierungszeit diesen Datentyp benötigt any_data_typeund durch diesen ersetzt . Wenn Sie dies in Ihrem Programm implementieren, erfahren Sie viel über die Funktionsweise von Vorlagen in C ++, was in Ihren zukünftigen Projekten hilfreich sein wird.T
Vorlagen in C ++
Ich denke, dies ist ein Thema für Ihren Code: constWo Sie es hingelegt haben, hat es keinen Nutzen; und es fehlt an anderen Orten, dass es dort sein sollte. Jede einzelne Funktion in MyCircularDequesollte nach constaußen fallen, da diese Rückgabewerte skalar sind und das Markieren constbuchstäblich keine Auswirkung hat. insertLast(const int value)hat etwas mehr Wirkung, ist aber wirklich nicht wichtig.
Der wichtigste Ort constist, die Konstanz thisfür Ihre getund isMethoden zu ändern . Sie müssen nach den Klammern consthinzugefügt haben . Dies registriert ein Versprechen, dass die Methoden keine Mitglieder ändern.