LeetCode 641: Design Circular Deque

Question

ฉันกำลังโพสต์วิธีแก้ปัญหาสำหรับ "Design Circular Deque" ของ LeetCode หากคุณต้องการตรวจสอบโปรดดำเนินการดังกล่าว ขอบคุณ!

ปัญหา

ออกแบบการใช้งานคิวแบบวงกลมสองชั้น (deque)

การใช้งานของคุณควรสนับสนุนการดำเนินการต่อไปนี้:

• MyCircularDeque(k): Constructor กำหนดขนาดของ deque เป็น k
• insertFront(): เพิ่มไอเทมที่ด้านหน้าของ Deque คืนค่าจริงหากการดำเนินการสำเร็จ
• insertLast(): เพิ่มรายการที่ด้านหลังของ Deque คืนค่าจริงหากการดำเนินการสำเร็จ
• deleteFront(): ลบรายการจากด้านหน้าของ Deque คืนค่าจริงหากการดำเนินการสำเร็จ
• deleteLast(): ลบรายการจากด้านหลังของ Deque คืนค่าจริงหากการดำเนินการสำเร็จ
• getFront(): รับไอเท็มด้านหน้าจาก Deque ถ้า deque ว่างเปล่าให้คืนค่า -1
• getRear(): รับไอเทมสุดท้ายจาก Deque ถ้า deque ว่างเปล่าให้คืนค่า -1
• isEmpty(): ตรวจสอบว่า Deque ว่างเปล่าหรือไม่
• isFull(): ตรวจสอบว่า Deque เต็มหรือไม่

ตัวอย่าง:

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

บันทึก:

• ค่าทั้งหมดจะอยู่ในช่วง [0, 1000]
• จำนวนการดำเนินการจะอยู่ในช่วง [1, 1000]
• โปรดอย่าใช้ห้องสมุด Deque ในตัว

รหัส:

// 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 และขนาด / ดัชนี ( k, count, head, tail) รู้สึกผิด อย่างน้อยkและควรจะเป็นcountstd::vector::size_type

• เมื่อคุณสำรอง deque กับstd::vectorทำให้headและลักษณะสำนวนมากขึ้นtailstd::vector::iterator

• kไม่ใช่ชื่อที่สื่อความหมายได้ชัดเจนที่สุด พิจารณาcapacity.

• ฉันไม่แน่ใจว่าstd::vectorเป็นคอนเทนเนอร์ที่ดีที่สุดในการสำรอง deque ขนาดคงที่ ท้ายที่สุดประเด็นstd::vectorคือการมีขนาดไดนามิก std::arrayหรือแม้แต่อาร์เรย์สไตล์ C แบบเก่าก็ดูเป็นธรรมชาติมากขึ้น

Answer 2

คุณสามารถเรียกstream.reserve(k)ใช้ตัวสร้างเพื่อปรับปรุงประสิทธิภาพของเวกเตอร์ได้เนื่องจากคุณรู้ว่าคุณจะมีkองค์ประกอบเท่านั้นดังนั้น.reserve()จะจัดสรรหน่วยความจำไว้ล่วงหน้า

ชอบใช้std::size_tมากกว่าint
int kจะเป็นstd::size_t k

คุณยังไม่ได้ประกาศให้เป็นตัวสร้างสำเนาหรือมิได้ดำเนินการกำหนดสำเนา ซึ่งอาจทำให้เกิดปัญหาได้หากคุณต้องการมอบหมายDequeให้อีกคนหนึ่ง

การจัดฟังก์ชั่นสมาชิกบางส่วนของคุณstructเช่นisEmpty(), getRear(), getFront() สามารถปรับปรุงประสิทธิภาพการทำงานของภาชนะของคุณ แต่มันจะเป็นการค้าสำหรับพื้นที่

หากคุณทำสิ่งนี้เพื่อจุดประสงค์เดียวในการทำภารกิจให้สำเร็จคุณสามารถเพิกเฉยต่อส่วนถัดไปได้

เทมเพลต

ตอนนี้คุณจะผูกพันกับการใช้งานdeque std::uint_fast16_tแต่ถ้าฉันต้องการสร้างdequeชื่อล่ะ? หรือdequeค่าทศนิยมที่แตกต่างกัน? ฉันไม่สามารถสร้าง 15 คลาสสำหรับข้อมูลแต่ละประเภทได้

ดังนั้นผมจะใช้แม่แบบใน C ++ ดังนั้นฉันสามารถสร้างทั่วไป deque

ไวยากรณ์เป็นเรื่องง่าย

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

ตอนนี้เมื่อคุณต้องการที่จะสร้าง deque deque<any_data_type> my_dequeใหม่ที่คุณสามารถทำได้

เมื่อใดก็ตามที่คุณจะใช้คุณแทนที่ด้วยValueTypeT

อะไร c ++ ไม่สามารถที่จะใช้เวลาany_data_typeและแทนที่Tด้วยชนิดข้อมูลว่าในช่วงเวลารวบรวม การนำสิ่งนี้ไปใช้ในโปรแกรมของคุณจะสอนคุณมากมายเกี่ยวกับการทำงานของเทมเพลตใน C ++ ซึ่งจะเป็นประโยชน์ในโครงการในอนาคตของคุณ

เทมเพลตใน C ++

Answer 3

ฉันคิดว่านี่เป็นธีมสำหรับโค้ดของคุณ: constที่คุณใส่ไว้ไม่มีประโยชน์ใด ๆ และมันหายไปจากที่อื่นที่ควรจะมี ทุกฟังก์ชั่นในMyCircularDequeควรวางconstไว้ด้านหน้าเนื่องจากค่าที่ส่งคืนเหล่านั้นเป็นสเกลาร์ดังนั้นการทำเครื่องหมายconstจึงไม่มีผลอย่างแท้จริง insertLast(const int value)มีผลมากกว่าเล็กน้อย แต่ไม่สำคัญจริงๆ

สถานที่สำคัญที่สุดที่จะนำconstคือการปรับเปลี่ยน const-Ness ของthisคุณgetและisวิธีการ พวกเขาจำเป็นต้องconstเพิ่มหลังวงเล็บ นี่เป็นการลงทะเบียนสัญญาว่าวิธีการนี้จะไม่แก้ไขสมาชิกใด ๆ