LeetCode 641: Design Circular Deque
Sto pubblicando una soluzione per "Design Circular Deque" di LeetCode. Se desideri rivedere, fallo. Grazie!
Problema
Progetta la tua implementazione della coda circolare a doppia estremità (deque).
La tua implementazione dovrebbe supportare le seguenti operazioni:
MyCircularDeque(k): Costruttore, imposta la dimensione del deque su k.insertFront(): Aggiunge un elemento nella parte anteriore di Deque. Restituisce true se l'operazione ha esito positivo.insertLast(): Aggiunge un elemento nella parte posteriore di Deque. Restituisce true se l'operazione ha esito positivo.deleteFront(): Elimina un elemento dalla parte anteriore di Deque. Restituisce true se l'operazione ha esito positivo.deleteLast(): Elimina un elemento dal retro di Deque. Restituisce true se l'operazione ha esito positivo.getFront(): Ottiene l'elemento in primo piano da Deque. Se il deque è vuoto, restituisce -1.getRear(): Ottiene l'ultimo elemento da Deque. Se il deque è vuoto, restituisce -1.isEmpty(): Controlla se Deque è vuoto o meno.isFull(): Controlla se Deque è pieno o meno.
Esempio:
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
Nota:
- Tutti i valori saranno nell'intervallo [0, 1000].
- Il numero di operazioni sarà compreso tra [1, 1000].
- Si prega di non utilizzare la libreria Deque incorporata.
Codice:
// 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;
};
Risposte
L'uso dello stesso tipo per i contenuti deque e le dimensioni / indici (
k, count, head, tail) sembra sbagliato. Almeno,kecountdovrebbe esserestd::vector::size_type.Dal momento che stai sostenendo il deque con
std::vector, rendendoheadetaill'std::vector::iteratoraspetto più idiomatico.knon è il nome più descrittivo. Consideracapacity.Non sono sicuro che
std::vectorsia il miglior contenitore per eseguire il backup della deque di dimensioni fisse. Dopotutto, il puntostd::vectorè avere una dimensione dinamica.std::array, o anche un semplice array vecchio stile C, sembra più naturale.
Puoi chiamare stream.reserve(k)il costruttore per migliorare l'efficienza del vettore perché sai che avrai solo kelementi, quindi .reserve()pre-allocherai la memoria.
Preferire utilizzare std::size_toltreint
int k sarebbestd::size_t k
Non hai dichiarato un costruttore di copie né un operatore di assegnazione di copie . Ciò può causare problemi se si desidera assegnarne uno Dequeall'altro.
Inlining alcune funzioni membro della vostra struct, come isEmpty(), getRear(), getFront() può migliorare le prestazioni del vostro contenitore, ma sarà un mestiere per lo spazio.
Se lo stai facendo al solo scopo di completare la sfida, puoi ignorare la parte successiva
Modelli
In questo momento, il tuo dequeè destinato a usare std::uint_fast16_t. Ma se volessi fare una dequelista di nomi? O dequedi valori decimali diversi? Non posso creare solo 15 classi per ciascuno dei tipi di dati.
Quindi, userò modelli in C ++ in modo da poter creare un generico deque .
La sintassi è semplice
template < typename T >
struct deque
{
public:
// public member functions
private:
std::vector< T > stream;
};
Ora, quando vuoi creare un nuovo deque, puoi farlo deque<any_data_type> my_deque.
Ovunque tu lo usi ValueType, lo sostituisci con T.
Quello che fa C ++ è che prende any_data_typee sostituisce Tcon quel tipo di dati durante la compilazione . L'implementazione di questo nel tuo programma ti insegnerà molto su come funzionano i modelli in C ++ che saranno utili nei tuoi progetti futuri.
Modelli in C ++
Penso che questo sia un tema per il tuo codice:, constdove l'hai inserito, non ha alcun vantaggio; e manca da altri posti che dovrebbe essere lì. Ogni singola funzione in MyCircularDequedovrebbe escludere la parte constanteriore, perché quei valori di ritorno sono scalari, quindi contrassegnarli non constha letteralmente alcun effetto. insertLast(const int value)ha un effetto leggermente maggiore ma non è davvero importante.
Il posto più importante da mettere constè modificare la costanza dei thistuoi metodi gete is. Devono essere constaggiunti dopo le parentesi. Ciò registra una promessa che i metodi non modificano alcun membro.