LeetCode C++ 641. Design Circular Deque【设计/队列】中等
发布日期:2021-07-01 02:52:48
浏览次数:4
分类:技术文章
本文共 3495 字,大约阅读时间需要 11 分钟。
Design your implementation of the circular double-ended queue (deque
). Your implementation should support following operations:
MyCircularDeque(k)
: Constructor, set the size of the deque to bek
.insertFront()
: Adds an item at the front of Deque. Returntrue
if the operation is successful.insertLast()
: Adds an item at the rear of Deque. Returntrue
if the operation is successful.deleteFront()
: Deletes an item from the front of Deque. Returntrue
if the operation is successful.deleteLast()
: Deletes an item from the rear of Deque. Returntrue
if the operation is successful.getFront()
: Gets the front item from the Deque. If the deque is empty, return-1
.getRear()
: Gets the last item from Deque. If the deque is empty, return-1
.isEmpty()
: Checks whether Deque is empty or not.isFull()
: Checks whether Deque is full or not.
Example:
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3circularDeque.insertLast(1); // return truecircularDeque.insertLast(2); // return truecircularDeque.insertFront(3); // return truecircularDeque.insertFront(4); // return false, the queue is fullcircularDeque.getRear(); // return 2circularDeque.isFull(); // return truecircularDeque.deleteLast(); // return truecircularDeque.insertFront(4); // return truecircularDeque.getFront(); // return 4
Note:
- All values will be in the range of
[0, 1000]
. - The number of operations will be in the range of
[1, 1000]
. - Please do not use the built-in Deque library.
题意:设计实现循环双端队列。
思路
实现循环双端队列时,注意下面的 (front, rear]
是一个左开右闭区间。代码如下:
class MyCircularDeque { private: int *deque; int capacity; int front, rear; int size;public: /** Initialize your data structure here. Set the size of the deque to be k. */ MyCircularDeque(int k) { deque = new int[capacity = k]; front = 0, rear = 0; //(,] size = 0; } /** Adds an item at the front of Deque. Return true if the operation is successful. */ bool insertFront(int value) { if (isFull()) return false; ++size; deque[front] = value; front = (front - 1 + capacity) % capacity; return true; } /** Adds an item at the rear of Deque. Return true if the operation is successful. */ bool insertLast(int value) { if (isFull()) return false; ++size; rear = (rear + 1) % capacity; deque[rear] = value; return true; } /** Deletes an item from the front of Deque. Return true if the operation is successful. */ bool deleteFront() { if (isEmpty()) return false; --size; front = (front + 1) % capacity; return true; } /** Deletes an item from the rear of Deque. Return true if the operation is successful. */ bool deleteLast() { if (isEmpty()) return false; --size; rear = (rear - 1 + capacity) % capacity; return true; } /** Get the front item from the deque. */ int getFront() { if (isEmpty()) return -1; return deque[(front + 1) % capacity]; } /** Get the last item from the deque. */ int getRear() { if (isEmpty()) return -1; return deque[rear]; } /** Checks whether the circular deque is empty or not. */ bool isEmpty() { return size == 0; } /** Checks whether the circular deque is full or not. */ bool isFull() { return size == capacity; }};
感觉这些设计题都蛮有意思的,以后可以多做一下。
转载地址:https://memcpy0.blog.csdn.net/article/details/108903110 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月11日 03时19分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
2021-05-18
2019-04-30
基础架构系列篇-NGINX部署VUE
2019-04-30
基础架构系列篇-系统centos7安装kafka
2019-04-30
在 Vue 中用 Axios 异步请求API
2019-04-30
Mysql 之主从复制
2019-04-30
【NLP学习笔记】中文分词(Word Segmentation,WS)
2019-04-30
对于时间复杂度的通俗理解
2019-04-30
如何输入多组数据并输出每组数据的和?
2019-04-30
行阶梯型矩阵
2019-04-30
JAVA学习笔记6 - 数组
2019-04-30
【学习笔记】Android Activity
2019-04-30
location区段
2019-04-30
linux内存的寻址方式
2019-04-30
how2heap-double free
2019-04-30
MyBatisPlus简单入门(SpringBoot)
2019-04-30
xss-labs详解(上)1-10
2019-04-30
xss-labs详解(下)11-20
2019-04-30
Linux png转jpg (convert命令)
2019-04-30
CodeForces - 456C Boredom (dp)
2019-04-30
CodeForces - 1042B Vitamins (思维)
2019-04-30