佛山营销型网站建设公司,济南建设网站制作优化分析,电商公司的网上设计,陇西做网站的广告店【LeetCode】设计数据结构|List、Stack、Queue、DLinkedList 文章目录 【LeetCode】设计数据结构|List、Stack、Queue、DLinkedList[toc]设计链表#xff08;中等#xff09;用栈实现队列#xff08;简单#xff09;用队列实现栈#xff08;简单#xff09;设计循环队列[toc]设计链表中等用栈实现队列简单用队列实现栈简单设计循环队列中等设计循环双端队列中等设计前中后队列中等
设计链表中等
707. 设计链表
冗余版
class MyLinkedList {class ListNode {int val;ListNode next;ListNode(int val) {this.val val;}}int size;ListNode dummyHead;public MyLinkedList() {this.size 0;this.dummyHead new ListNode(-1);}public int get(int index) {if (index 1 size) return -1;ListNode node dummyHead.next;for (int i 0; i index; i) {node node.next;}return node.val;}public void addAtHead(int val) {ListNode newNode new ListNode(val);newNode.next dummyHead.next;dummyHead.next newNode;size;}public void addAtTail(int val) {ListNode node dummyHead;while (node.next ! null) {node node.next;}node.next new ListNode(val);size;}public void addAtIndex(int index, int val) {ListNode newNode new ListNode(val);ListNode node dummyHead;for (int i 0; i index; i) {node node.next;if (node null) return;}newNode.next node.next;node.next newNode;size;}public void deleteAtIndex(int index) {if (index 0 || index size) return;ListNode node dummyHead;for (int i 0; i index; i) {node node.next;}ListNode deleteNode node.next;node.next deleteNode.next;// 清除野指针deleteNode null;size--;}
}代码复用简化版
class MyLinkedList {class ListNode {int val;ListNode next;ListNode(int val) {this.val val;}}int size;ListNode dummyHead;public MyLinkedList() {this.size 0;this.dummyHead new ListNode(-1);}public int get(int index) {if (index 1 size) return -1;ListNode node dummyHead.next;for (int i 0; i index; i) {node node.next;}return node.val;}public void addAtHead(int val) {this.addAtIndex(0, val);}public void addAtTail(int val) {this.addAtIndex(size, val);}public void addAtIndex(int index, int val) {ListNode newNode new ListNode(val);ListNode node dummyHead;for (int i 0; i index; i) {node node.next;if (node null) return;}newNode.next node.next;node.next newNode;size;}public void deleteAtIndex(int index) {if (index 0 || index size) return;ListNode node dummyHead;for (int i 0; i index; i) {node node.next;}ListNode deleteNode node.next;node.next deleteNode.next;// 清除野指针deleteNode null;size--;}
}用栈实现队列简单
232. 用栈实现队列
class MyQueue {StackInteger a;StackInteger b;public MyQueue() {this.a new StackInteger();this.b new StackInteger();}public void push(int x) {a.push(x);}public int pop() {if (b.isEmpty()) {while (!a.isEmpty()) {b.push(a.pop());}}return b.pop();}public int peek() {if (b.isEmpty()) {while (!a.isEmpty()) {b.push(a.pop());}}return b.peek();}public boolean empty() {return a.isEmpty() b.isEmpty();}
}用队列实现栈简单
225. 用队列实现栈
方法一双队列实现
class MyStack {QueueInteger a;QueueInteger b;public MyStack() {this.a new LinkedListInteger();this.b new LinkedListInteger();}public void push(int x) {while (!a.isEmpty()) {b.offer(a.poll());}a.offer(x);while (!b.isEmpty()) {a.offer(b.poll());}}public int pop() {return a.poll();}public int top() {return a.peek();}public boolean empty() {return a.isEmpty();}
}方法二单队列实现
class MyStack {QueueInteger a;public MyStack() {this.a new LinkedListInteger();}public void push(int x) {a.offer(x);for (int i 0; i a.size() - 1; i) {a.offer(a.poll());}}public int pop() {return a.poll();}public int top() {return a.peek();}public boolean empty() {return a.isEmpty();}
}设计循环队列中等
622. 设计循环队列
使用数组实现
class MyCircularQueue {private int capacity;private int front, rear;private int[] elements;public MyCircularQueue(int k) {this.capacity k 1;this.front this.rear 0;this.elements new int[k 1];}public boolean enQueue(int value) {if (isFull()) return false;elements[rear] value;rear (rear 1) % capacity;return true;}public boolean deQueue() {if (isEmpty()) return false;front (front 1) % capacity;return true;}public int Front() {return isEmpty() ? -1 : elements[front];}public int Rear() {return isEmpty() ? -1 : elements[(rear - 1 capacity) % capacity];}public boolean isEmpty() {return rear front;}public boolean isFull() {return (rear 1) % capacity front;}
}使用链表实现
class MyCircularQueue {class ListNode {int val;ListNode next;ListNode(int val) {this.val val;}}int capacity, size;ListNode head, tail;public MyCircularQueue(int k) {this.size 0;this.capacity k;}public boolean enQueue(int value) {if (isFull()) return false;ListNode node new ListNode(value);if (isEmpty()) {head tail node;} else {tail.next node;tail node;}size;return true;}public boolean deQueue() {if (isEmpty()) return false;ListNode node head;head head.next;node null;size--;return true;}public int Front() {return isEmpty() ? -1 : head.val;}public int Rear() {return isEmpty() ? -1 : tail.val;}public boolean isEmpty() {return size 0;}public boolean isFull() {return size capacity;}
}设计循环双端队列中等
641. 设计循环双端队列
方法一数组实现
class MyCircularDeque {private int capacity;private int front, rear;private int[] elements;public MyCircularDeque(int k) {this.capacity k 1;this.front this.rear 0;this.elements new int[k 1];}public boolean insertFront(int value) {if (isFull()) return false;front (front - 1 capacity) % capacity;elements[front] value;return true;}public boolean insertLast(int value) {if (isFull()) return false;elements[rear] value;rear (rear 1 capacity) % capacity;return true;}public boolean deleteFront() {if (isEmpty()) return false;front (front 1) % capacity;return true;}public boolean deleteLast() {if (isEmpty()) return false;rear (rear - 1 capacity) % capacity;return true;}public int getFront() {return isEmpty() ? -1 : elements[front];}public int getRear() {return isEmpty() ? -1 : elements[(rear - 1 capacity) % capacity];}public boolean isEmpty() {return front rear;}public boolean isFull() {return (rear 1) % capacity front;}
}方法二链表实现
class MyCircularDeque {class DLinkedNode {int val;DLinkedNode prev;DLinkedNode next;DLinkedNode (int val) {this.val val;}}private int size, capacity;private DLinkedNode dummyHead, dummyTail;public MyCircularDeque(int k) {this.size 0;this.capacity k;// 设置一个虚的头结点和尾节点this.dummyHead new DLinkedNode(-1);this.dummyTail new DLinkedNode(-1);this.dummyHead.next this.dummyTail;this.dummyTail.prev this.dummyHead;}public boolean insertFront(int value) {if (isFull()) return false;DLinkedNode node new DLinkedNode(value);node.next dummyHead.next;node.prev dummyHead;dummyHead.next.prev node;dummyHead.next node;size;return true;}public boolean insertLast(int value) {if (isFull()) return false;DLinkedNode node new DLinkedNode(value);node.next dummyTail;node.prev dummyTail.prev;dummyTail.prev.next node;dummyTail.prev node;size;return true;}public boolean deleteFront() {if (isEmpty()) return false;DLinkedNode node dummyHead.next;node.next.prev dummyHead;dummyHead.next node.next;node null;size--;return true;}public boolean deleteLast() {if (isEmpty()) return false;DLinkedNode node dummyTail.prev;node.next.prev node.prev;node.prev.next node.next;node null;size--;return true;}public int getFront() {return isEmpty() ? -1 : dummyHead.next.val;}public int getRear() {return isEmpty() ? -1 : dummyTail.prev.val;}public boolean isEmpty() {// return dummyHead.next dummyTail;// return dummyTail.prev dummyHead;return size 0;}public boolean isFull() {return size capacity;}
}设计前中后队列中等
1670. 设计前中后队列
class FrontMiddleBackQueue {// 保持 leftQueue.size() rightQueue.size()// or leftQueue.size() 1 rightQueue.size()// 注意中位数是按进入数字流中的数字的先后顺序来看的别搞反啦private LinkedListInteger leftQueue;private LinkedListInteger rightQueue;public FrontMiddleBackQueue() {leftQueue new LinkedListInteger();rightQueue new LinkedListInteger();}public void pushFront(int val) {if (leftQueue.size() rightQueue.size()) {rightQueue.offerFirst(val);} else {leftQueue.offerFirst(rightQueue.pollLast());rightQueue.offerFirst(val);}}public void pushMiddle(int val) {if (rightQueue.isEmpty()) {rightQueue.offerLast(val);} else if (leftQueue.size() rightQueue.size()) {rightQueue.offerLast(val);} else {leftQueue.offerFirst(rightQueue.pollLast());rightQueue.offerLast(val);}}public void pushBack(int val) {leftQueue.offerLast(val);if (leftQueue.size() rightQueue.size()) {rightQueue.offerLast(leftQueue.pollFirst());}}public int popFront() {if (rightQueue.isEmpty()) return -1;int val rightQueue.pollFirst();if (leftQueue.size() rightQueue.size()) {rightQueue.offerLast(leftQueue.pollFirst());}return val;}public int popMiddle() {if (rightQueue.isEmpty()) return -1;int val rightQueue.pollLast();if (leftQueue.size() rightQueue.size()) {rightQueue.offerLast(leftQueue.pollFirst());}return val;}public int popBack() {if (rightQueue.isEmpty()) return -1;if (leftQueue.size() rightQueue.size()) {leftQueue.offerFirst(rightQueue.pollLast());}return leftQueue.pollLast();}
}
