LeetCode 641: Conception Circulaire Deque
Je poste une solution pour le "Design Circular Deque" de LeetCode. Si vous souhaitez passer en revue, veuillez le faire. Merci!
Problème
Concevez votre implémentation de la file d'attente circulaire double (deque).
Votre implémentation doit prendre en charge les opérations suivantes:
MyCircularDeque(k): Constructeur, définissez la taille du deque sur k.insertFront(): Ajoute un élément à l'avant de Deque. Renvoie true si l'opération réussit.insertLast(): Ajoute un élément à l'arrière de Deque. Renvoie true si l'opération réussit.deleteFront(): Supprime un élément de l'avant de Deque. Renvoie true si l'opération réussit.deleteLast(): Supprime un élément de l'arrière de Deque. Renvoie true si l'opération réussit.getFront(): Obtient l'élément avant du Deque. Si le deque est vide, renvoie -1.getRear(): Obtient le dernier élément de Deque. Si le deque est vide, renvoie -1.isEmpty(): Vérifie si Deque est vide ou non.isFull(): Vérifie si Deque est plein ou non.
Exemple:
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
Remarque:
- Toutes les valeurs seront comprises entre [0, 1000].
- Le nombre d'opérations sera de l'ordre de [1, 1000].
- Veuillez ne pas utiliser la bibliothèque Deque intégrée.
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;
};
Réponses
Utiliser le même type pour le contenu deque et les tailles / indices (
k, count, head, tail) semble faux. Au moins,ketcountdevrait l'êtrestd::vector::size_type.Puisque vous sauvegardez le deque avec
std::vector, faitesheadettaillesstd::vector::iteratorregards plus idiomatiques.kn'est pas le nom le plus descriptif. Considérezcapacity.Je ne suis pas sûr que ce
std::vectorsoit le meilleur conteneur pour sauvegarder le deque de taille fixe. Après tout, le butstd::vectorest d'avoir une taille dynamique.std::array, ou même un vieux tableau de style C, semble plus naturel.
Vous pouvez appeler stream.reserve(k)le constructeur pour améliorer l'efficacité du vecteur car vous savez que vous n'aurez que des kéléments, donc vous .reserve()pré-allouerez la mémoire.
Préférez utiliser std::size_tplusint
int k seraitstd::size_t k
Vous n'avez pas déclaré de constructeur de copie ni d' opérateur d'affectation de copie . Cela peut entraîner des problèmes si vous souhaitez en attribuer un Dequeà un autre.
Inline certaines fonctions membres de votre structcomme isEmpty(), getRear(), getFront() peut améliorer les performances de votre conteneur, mais il sera un commerce pour l' espace.
Si vous faites cela dans le seul but de relever le défi, vous pouvez ignorer la partie suivante
Modèles
À l'heure actuelle, votre dequeest destiné à être utilisé std::uint_fast16_t. Mais que faire si je voulais faire un dequedes noms? Ou dequedes valeurs décimales différentes? Je ne peux pas simplement créer 15 classes pour chacun des types de données.
Par conséquent, j'utiliserai des modèles en C ++ pour pouvoir créer un générique deque .
La syntaxe est simple
template < typename T >
struct deque
{
public:
// public member functions
private:
std::vector< T > stream;
};
Maintenant, lorsque vous souhaitez créer un nouveau deque, vous pouvez le faire deque<any_data_type> my_deque.
Où que vous utilisiez ValueType, vous le remplacez par T.
Ce que fait C ++, c'est qu'il prend any_data_typeet remplace Tpar ce type de données pendant la compilation . L'implémentation de cela dans votre programme vous en apprendra beaucoup sur le fonctionnement des modèles en C ++, ce qui vous sera utile dans vos futurs projets.
Modèles en C ++
Je pense que c'est un thème pour votre code:, constlà où vous l'avez mis, n'a aucun avantage; et il manque à d'autres endroits qu'il devrait être là. Chaque fonction dans MyCircularDequedevrait supprimer l' constavant, car ces valeurs de retour sont scalaires, leur marquage constn'a donc littéralement aucun effet. insertLast(const int value)a un peu plus d'effet mais n'est vraiment pas important.
L'endroit le plus important à mettre constest de modifier la const-ness de thisvos méthodes getet is. Ils doivent avoir constajouté après les parenthèses. Cela enregistre une promesse que les méthodes ne modifient aucun membre.