LeetCode 641: Tasarım Dairesel Tasarım

Question

LeetCode'un "Design Circular Deque" için bir çözüm yayınlıyorum. İncelemek isterseniz lütfen yapın. Teşekkür ederim!

Sorun

Dairesel çift uçlu kuyruk (deque) uygulamanızı tasarlayın.

Uygulamanız aşağıdaki işlemleri desteklemelidir:

• MyCircularDeque(k): Yapıcı, sekmenin boyutunu k olarak ayarlayın.
• insertFront(): Deque'in önüne bir öğe ekler. İşlem başarılı olursa true döndür.
• insertLast(): Deque'in arkasına bir öğe ekler. İşlem başarılı olursa true döndür.
• deleteFront(): Deque'in önünden bir öğeyi siler. İşlem başarılı olursa true döndür.
• deleteLast(): Deque'in arkasından bir öğeyi siler. İşlem başarılı olursa true döndür.
• getFront(): Deque'den ön öğeyi alır. Kuyruk boşsa -1 döndür.
• getRear(): Deque'den son öğeyi alır. Kuyruk boşsa -1 döndür.
• isEmpty(): Deque'in boş olup olmadığını kontrol eder.
• isFull(): Deque'in dolu olup olmadığını kontrol eder.

Misal:

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

Not:

• Tüm değerler [0, 1000] aralığında olacaktır.
• İşlem sayısı [1, 1000] aralığında olacaktır.
• Lütfen yerleşik Deque kitaplığını kullanmayın.

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

• Deque içerikleri ve boyutlar / indeksler ( k, count, head, tail) için aynı türü kullanmak yanlış geliyor. En azından kve countolmalı std::vector::size_type.

• Birlikte deque yedekleme olduğundan std::vector, yapım headve görünüm daha deyimsel.tailstd::vector::iterator

• ken açıklayıcı isim değil. Düşünün capacity.

• std::vectorSabit boyutlu dekoru yedeklemek için en iyi konteynerin bu olduğundan emin değilim . Sonuçta, std::vectorönemli olan dinamik bir boyuta sahip olmaktır. std::arrayhatta eski C-tarzı bir dizi bile daha doğal görünüyor.

Answer 2

stream.reserve(k)Yapıcıyı vektörün verimliliğini artırmak için çağırabilirsiniz çünkü yalnızca kelemanlara sahip olacağınızı biliyorsunuz , bu yüzden .reserve()belleği önceden ayıracaksınız.

Kullanmayı tercih std::size_tüzerindeint
int k olacağınıstd::size_t k

Bir kopya oluşturucu veya kopya atama operatörü bildirmediniz . Birini Dequediğerine atamak istiyorsanız bu sorunlara neden olabilir .

Satır içine almak için bazı üye işlevlerini structbeğendiniz isEmpty(), getRear(), getFront() olabilir kapsayıcınızın performansını artırmakla kalmaz, alan için bir ticaret olacak.

Bunu sadece mücadeleyi tamamlamak amacıyla yapıyorsanız, bir sonraki bölümü göz ardı edebilirsiniz.

Şablonlar

Şu anda dequekullanmak zorunda std::uint_fast16_t. Ama ya bir dequeisim yapmak istersem ? Veya dequefarklı ondalık değerler? Veri türlerinin her biri için 15 sınıf oluşturamıyorum.

Bu nedenle, C ++ 'da şablonları kullanacağım, böylece bir jenerik deque .

Sözdizimi basittir

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

Şimdi yeni bir dekor yaratmak istediğinizde yapabilirsiniz deque<any_data_type> my_deque.

Nereyi kullanırsanız kullanın ValueType, yerine koyarsınız T.

C ++ 'ın yaptığı şey, derleme sırasında bu veri türünü alıp any_data_typedeğiştirmesidir . Bunu programınızda uygulamak, şablonların C ++ 'da nasıl çalıştığı hakkında size çok şey öğretecek ve bu da gelecekteki projelerinizde yardımcı olacaktır.T

C ++ 'da Şablonlar

Answer 3

Sanırım bu, kodunuz için bir tema: constkoyduğunuz yerde hiçbir faydası yok; ve orada olması gereken diğer yerlerden eksik. Her bir işlev, öne doğru MyCircularDequebırakmalıdır const, çünkü bu dönüş değerleri skalerdir, bu yüzden onları işaretlemenin consttam anlamıyla hiçbir etkisi yoktur. insertLast(const int value)biraz daha fazla etkiye sahiptir, ancak gerçekten önemli değildir.

Koyulacak en önemli yer, sizin ve yöntemlerinizin constsabitliğini değiştirmektir . Parantezlerden sonra eklenmeleri gerekir . Bu, yöntemlerin herhangi bir üyeyi değiştirmeyeceği vaadini kaydeder.thisgetisconst