LeetCode 641: Design Circular Deque
Estou postando uma solução para o "Design Circular Deque" do LeetCode. Se você gostaria de revisar, por favor, faça-o. Obrigado!
Problema
Projete sua implementação da fila dupla circular (deque).
Sua implementação deve suportar as seguintes operações:
MyCircularDeque(k): Construtor, defina o tamanho do deque como k.insertFront(): Adiciona um item na frente do Deque. Retorna verdadeiro se a operação for bem-sucedida.insertLast(): Adiciona um item na parte traseira do Deque. Retorna verdadeiro se a operação for bem-sucedida.deleteFront(): Exclui um item da frente do Deque. Retorna verdadeiro se a operação for bem-sucedida.deleteLast(): Exclui um item da parte traseira do Deque. Retorna verdadeiro se a operação for bem-sucedida.getFront(): Obtém o item frontal do Deque. Se o deque estiver vazio, retorne -1.getRear(): Obtém o último item de Deque. Se o deque estiver vazio, retorne -1.isEmpty(): Verifica se Deque está vazio ou não.isFull(): Verifica se o Deque está cheio ou não.
Exemplo:
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:
- Todos os valores estarão na faixa de [0, 1000].
- O número de operações estará na faixa de [1, 1000].
- Não use a biblioteca interna Deque.
Código:
// 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;
};
Respostas
Usar o mesmo tipo para o conteúdo deque e os tamanhos / índices (
k, count, head, tail) parece errado. Pelo menos,kecountdeveria serstd::vector::size_type.Já que você está fazendo backup do deque com
std::vector, tornandoheadetailosstd::vector::iteratorlooks mais idiomáticos.knão é o nome mais descritivo. Considerecapacity.Não tenho certeza se esse
std::vectoré o melhor contêiner para fazer backup do deque de tamanho fixo. Afinal, o objetivostd::vectoré ter um tamanho dinâmico.std::array, ou até mesmo uma matriz simples no estilo C, parece mais natural.
Você pode chamar stream.reserve(k)o construtor para melhorar a eficiência do vetor porque você sabe que terá apenas kelementos, então .reserve()irá pré-alocar a memória.
Preferem usar std::size_tmaisint
int k seriastd::size_t k
Você não declarou um construtor de cópia nem um operador de atribuição de cópia . Isso pode causar problemas se você quiser atribuir um Dequea outro.
Inlining algumas funções de membro de sua structcomo isEmpty(), getRear(), getFront() pode melhorar o desempenho de seu recipiente, mas vai ser um comércio para o espaço.
Se você está fazendo isso com o único propósito de completar o desafio, você pode ignorar a próxima parte
Modelos
Agora, você dequeestá fadado a usar std::uint_fast16_t. Mas e se eu quisesse fazer uma dequesérie de nomes? Ou um dequede diferentes valores decimais? Não posso simplesmente criar 15 classes para cada um dos tipos de dados.
Portanto, usarei modelos em C ++ para criar um genérico deque .
A sintaxe é simples
template < typename T >
struct deque
{
public:
// public member functions
private:
std::vector< T > stream;
};
Agora, quando você quiser criar um novo deque, pode fazer deque<any_data_type> my_deque.
Onde quer que você use ValueType, você o substitui por T.
O que o C ++ faz é pegar any_data_typee substituir Tesse tipo de dados durante o tempo de compilação . Implementar isso em seu programa ensinará muito sobre como os modelos funcionam em C ++, o que será útil em seus projetos futuros.
Modelos em C ++
Acho que este é um tema para o seu código: constonde você o colocou, não tem nenhum benefício; e está faltando em outros lugares que deveria estar lá. Cada função in MyCircularDequedeve ser descartada na constfrente, porque esses valores de retorno são escalares, portanto marcá-los não consttem literalmente nenhum efeito. insertLast(const int value)tem um pouco mais de efeito, mas não é realmente importante.
O lugar mais importante para colocar consté modificar a constância de thisseus métodos gete is. Eles precisam ser constadicionados após os parênteses. Isso registra uma promessa de que os métodos não modificam nenhum membro.