2024/09/28 Leetcode Daily Porblem

641. Design Circular Deque
難度: 中等

題意

實作一個雙向佇列的類，支援以下操作:

• MyCircularDeque(int k): 初始化佇列，最大容量為 k。
• boolean insertFront()：在佇列前端插入一個元素。如果操作成功則回傳 true，否則回傳 false。
• boolean insertLast()：在佇列後端插入一個元素。如果操作成功則回傳 true，否則回傳 false。
• boolean deleteFront()：從佇列前端刪除一個元素。如果操作成功則回傳 true，否則回傳 false。
• boolean deleteLast()：從佇列後端刪除一個元素。如果操作成功則回傳 true，否則回傳 false。
• int getFront()：回傳佇列前端的元素。如果佇列為空，則回傳 -1。
• int getRear()：回傳佇列後端的元素。如果佇列為空，則回傳 -1。
• boolean isEmpty()：如果佇列為空，回傳 true，否則回傳 false。
• boolean isFull()：如果佇列已滿，回傳 true，否則回傳 false。

思路1

直接套用C++ STL std::deque做，稍微封裝一下即可

實作1

class MyCircularDeque {
private:
    size_t capacity;
    deque<int> dq;
public:
    MyCircularDeque(int k) {
        this->capacity = (size_t)k;
        this->dq = deque<int>{};
    }
    
    bool insertFront(int value) {
        if(this->dq.size() == this->capacity)
            return false;
        else
            this->dq.push_front(value);
        return true;
    }
    
    bool insertLast(int value) {
        if(this->dq.size() == this->capacity)
            return false;
        else
            this->dq.push_back(value);
        return true;
    }
    
    bool deleteFront() {
        if(this->dq.empty())
            return false;
        else
            this->dq.pop_front();
        return true;

    }
    
    bool deleteLast() {
        if(this->dq.empty())
            return false;
        else
            this->dq.pop_back();
        return true;
    }
    
    int getFront() {
        if(this->dq.empty())
            return -1;
        return this->dq.front();
    }
    
    int getRear() {
        if(this->dq.empty())
            return -1;
        return this->dq.back();
    }
    
    bool isEmpty() {
        return this->dq.empty();
    }
    
    bool isFull() {
        return this->dq.size() == this->capacity;
    }
};

結果1

這樣也行XDD
Accepted 51 / 51 test cases passed.
Runtime: 21 ms
Memory Usage: 22.7 MB

思路2

用STL可行，但就失去練習實作資料結構的機會了。
改用array base的方法，並新增capacity, size, head, tail來幫助解題。
一開始head要在tail前方，各自代表頭尾要插入的索引位置。

新增、刪除、查詢頭、查詢尾後要注意head和tail的移動方向

為了避免tail head往左右移動時超出邊界，一律以往右移動再取capacity模數處理。

實作2

class MyCircularDeque
{
private:
    size_t capacity;
    size_t size;
    size_t head, tail;
    vector<int> dq;

public:
    MyCircularDeque(int k)
    {
        this->capacity = (size_t)k;
        this->dq = vector<int>(this->capacity);
        this->size = 0;
        this->head = this->capacity - 1;
        this->tail = 0;
    }

    bool insertFront(int value)
    {
        if (this->isFull())
            return false;
        else
        {
            this->dq[this->head] = value;
            this->head = (this->head + this->capacity - 1) % capacity;
            this->size++;
        }
        return true;
    }

    bool insertLast(int value)
    {
        if (this->isFull())
            return false;
        else
        {
            this->dq[this->tail] = value;
            this->tail = (this->tail + 1) % capacity;
            this->size++;
        }
        return true;
    }

    bool deleteFront()
    {
        if (this->isEmpty())
            return false;
        else
        {
            this->head = (this->head + 1) % capacity;
            this->size--;
        }
        return true;
    }

    bool deleteLast()
    {
        if (this->isEmpty())
            return false;
        else
        {
            this->tail = (this->tail + capacity - 1) % capacity;
            this->size--;
        }
        return true;
    }

    int getFront()
    {
        if (this->isEmpty())
            return -1;
        return this->dq[(this->head + 1) % capacity];
    }

    int getRear()
    {
        if (this->isEmpty())
            return -1;
        return this->dq[(this->tail + capacity - 1) % capacity];
    }

    bool isEmpty()
    {
        return this->size == 0;
    }

    bool isFull()
    {
        return this->size == this->capacity;
    }
};

結果2

Accepted
51/51 cases passed (20 ms)
Your runtime beats 64.1 % of cpp submissions
Your memory usage beats 48.19 % of cpp submissions (22.7 MB)

總結

慘烈XD，array base試了一陣子才發覺tail要再head前方。