厦门集美网站建设,做网站常见程序,滁州seo网站排名优化,saas建站和开源建站的区别设计循环双端队列
https://leetcode.cn/problems/design-circular-deque/description/
描述 设计实现双端队列。 实现 MyCircularDeque 类: MyCircularDeque(int k) #xff1a;构造函数,双端队列最大为 k 。boolean insertFront()#xff1a;将一个元素添加到双端队列头部…设计循环双端队列
https://leetcode.cn/problems/design-circular-deque/description/
描述 设计实现双端队列。 实现 MyCircularDeque 类: 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
输入
[MyCircularDeque, insertLast, insertLast, insertFront, insertFront, getRear, isFull, deleteLast, insertFront, getFront]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]解释
MyCircularDeque circularDeque new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4提示
1 k 10000 value 1000insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次
Typescript 版算法实现 1 ) 方案1数组
class MyCircularDeque {private capacity: number;private rear: number;private front: number;private elements: number[];constructor(k: number) {this.capacity k 1; // 使用 k1 来区分满和空的情况this.rear 0;this.front 0;this.elements new Arraynumber(this.capacity).fill(0);}insertFront(value: number): boolean {if (this.isFull()) {return false;}this.front (this.front - 1 this.capacity) % this.capacity;this.elements[this.front] value;return true;}insertLast(value: number): boolean {if (this.isFull()) {return false;}this.elements[this.rear] value;this.rear (this.rear 1) % this.capacity;return true;}deleteFront(): boolean {if (this.isEmpty()) {return false;}this.front (this.front 1) % this.capacity;return true;}deleteLast(): boolean {if (this.isEmpty()) {return false;}this.rear (this.rear - 1 this.capacity) % this.capacity;return true;}getFront(): number {if (this.isEmpty()) {return -1;}return this.elements[this.front];}getRear(): number {if (this.isEmpty()) {return -1;}return this.elements[(this.rear - 1 this.capacity) % this.capacity];}isEmpty(): boolean {return this.rear this.front;}isFull(): boolean {return (this.rear 1) % this.capacity this.front;}
}/*** Your MyCircularDeque object will be instantiated and called as such:* var obj new MyCircularDeque(k)* var param_1 obj.insertFront(value)* var param_2 obj.insertLast(value)* var param_3 obj.deleteFront()* var param_4 obj.deleteLast()* var param_5 obj.getFront()* var param_6 obj.getRear()* var param_7 obj.isEmpty()* var param_8 obj.isFull()*/2 ) 方案2链表
// 定义节点结构
class Node {prev: Node | null null;next: Node | null null;val: number;constructor(value: number) {this.val value;}
}class MyCircularDeque {head: Node | null null;tail: Node | null null;capacity: number;size: number 0;constructor(k: number) {this.capacity k;}// 在队列前端插入元素insertFront(value: number): boolean {if (this.isFull()) {return false;}const newNode new Node(value);if (this.isEmpty()) {this.head newNode;this.tail newNode;} else {newNode.next this.head;if (this.head) {this.head.prev newNode;}this.head newNode;}this.size;return true;}// 在队列末端插入元素insertLast(value: number): boolean {if (this.isFull()) {return false;}const newNode new Node(value);if (this.isEmpty()) {this.head newNode;this.tail newNode;} else {if (this.tail) {this.tail.next newNode;newNode.prev this.tail;}this.tail newNode;}this.size;return true;}// 从队列前端删除元素deleteFront(): boolean {if (this.isEmpty()) {return false;}if (this.head) {this.head this.head.next;if (this.head) {this.head.prev null;} else {this.tail null; // 如果删除后队列为空更新尾指针}}this.size--;return true;}// 从队列末端删除元素deleteLast(): boolean {if (this.isEmpty()) {return false;}if (this.tail) {this.tail this.tail.prev;if (this.tail) {this.tail.next null;} else {this.head null; // 如果删除后队列为空更新头指针}}this.size--;return true;}// 获取队列前端的元素getFront(): number {if (this.isEmpty()) {return -1;}return this.head?.val ?? -1;}// 获取队列末端的元素getRear(): number {if (this.isEmpty()) {return -1;}return this.tail?.val ?? -1;}// 检查队列是否为空isEmpty(): boolean {return this.size 0;}// 检查队列是否已满isFull(): boolean {return this.size this.capacity;}
}/*** Your MyCircularDeque object will be instantiated and called as such:* var obj new MyCircularDeque(k)* var param_1 obj.insertFront(value)* var param_2 obj.insertLast(value)* var param_3 obj.deleteFront()* var param_4 obj.deleteLast()* var param_5 obj.getFront()* var param_6 obj.getRear()* var param_7 obj.isEmpty()* var param_8 obj.isFull()*/
