文章目录
- 刷题前唠嗑
- 题目：设计前中后队列
- 题目描述
- 代码与解题思路
- 偷看大佬题解
- 结语
刷题前唠嗑
LeetCode？启动！！！
这道题的难度，才是我想象中的中等题的难度好吧，昨天那玩意对我来说还是太难了。。。
题目：设计前中后队列
题目链接：1670. 设计前中后队列
题目描述
代码与解题思路
type FrontMiddleBackQueue struct {
queue []int
size int
}
func Constructor() FrontMiddleBackQueue {
return FrontMiddleBackQueue {
queue: make([]int, 1001),
size: 0,
}
}
func (this *FrontMiddleBackQueue) PushFront(val int) {
tmp := make([]int, 1001)
tmp[0] = val
for i := 1; i < this.size+1; i++ {
tmp[i] = this.queue[i-1]
}
this.queue = tmp
this.size++
}
func (this *FrontMiddleBackQueue) PushMiddle(val int) {
tmp := make([]int, 1001)
for i := 0; i < this.size/2; i++ {
tmp[i] = this.queue[i]
}
tmp[this.size/2] = val
for i := this.size/2+1; i < this.size+1; i++ {
tmp[i] = this.queue[i-1]
}
this.queue = tmp
this.size++
}
func (this *FrontMiddleBackQueue) PushBack(val int) {
tmp := make([]int, 1001)
for i := 0; i < this.size; i++ {
tmp[i] = this.queue[i]
}
tmp[this.size] = val
this.queue = tmp
this.size++
}
func (this *FrontMiddleBackQueue) PopFront() int {
if this.size == 0 {
return -1
}
ans := this.queue[0]
this.queue = this.queue[1:]
this.size--
return ans
}
func (this *FrontMiddleBackQueue) PopMiddle() int {
if this.size == 0 {
return -1
}
ans := this.queue[(this.size-1)/2]
this.queue = append(this.queue[:(this.size-1)/2], this.queue[(this.size-1)/2+1:]...)
this.size--
return ans
}
func (this *FrontMiddleBackQueue) PopBack() int {
if this.size == 0 {
return -1
}
ans := this.queue[this.size-1]
this.queue = this.queue[:this.size-1]
this.size--
return ans
}
快来欣赏一下我的数组屎山，当时一开始做的时候我在想是用链表做还是数组做，链表做肯定是更优的，但是我感觉链表可能比较麻烦（事实证明数组更麻烦。。。早知道用链表写了，后悔）
题目的思路就是：跟着题目要求写就行了，主要考察的是代码能力
偷看大佬题解
Go 链表实现：
// 第一种写法：链表
type FrontMiddleBackQueue struct {
left *list.List
right *list.List
}
func Constructor() FrontMiddleBackQueue {
return FrontMiddleBackQueue{
left: list.New(),
right: list.New(),
}
}
// 调整长度，保证 0 <= right.Len() - left.Len() <= 1
// 从而保证可以在正中间插入删除元素
func (q *FrontMiddleBackQueue) balance() {
if q.left.Len() > q.right.Len() {
q.right.PushFront(q.left.Remove(q.left.Back()))
} else if q.right.Len() > q.left.Len()+1 {
q.left.PushBack(q.right.Remove(q.right.Front()))
}
}
func (q *FrontMiddleBackQueue) PushFront(val int) {
q.left.PushFront(val)
q.balance()
}
func (q *FrontMiddleBackQueue) PushMiddle(val int) {
if q.left.Len() < q.right.Len() {
q.left.PushBack(val)
} else {
q.right.PushFront(val)
}
}
func (q *FrontMiddleBackQueue) PushBack(val int) {
q.right.PushBack(val)
q.balance()
}
func (q *FrontMiddleBackQueue) PopFront() (val int) {
if q.right.Len() == 0 { // 整个队列为空
return -1
}
if q.left.Len() > 0 {
val = q.left.Remove(q.left.Front()).(int)
} else {
val = q.right.Remove(q.right.Front()).(int)
}
q.balance()
return
}
func (q *FrontMiddleBackQueue) PopMiddle() int {
if q.right.Len() == 0 { // 整个队列为空
return -1
}
if q.left.Len() == q.right.Len() {
return q.left.Remove(q.left.Back()).(int)
}
return q.right.Remove(q.right.Front()).(int)
}
func (q *FrontMiddleBackQueue) PopBack() int {
if q.right.Len() == 0 { // 整个队列为空
return -1
}
val := q.right.Remove(q.right.Back()).(int)
q.balance()
return val
}
Go 双端队列实现
// 第二种写法：四个 slice
type FrontMiddleBackQueue struct {
left *Deque
right *Deque
}
func Constructor() FrontMiddleBackQueue {
return FrontMiddleBackQueue{
left: &Deque{},
right: &Deque{},
}
}
// 调整长度，保证 0 <= right.Len() - left.Len() <= 1
// 从而保证可以在正中间插入删除元素
func (q *FrontMiddleBackQueue) balance() {
if q.left.Len() > q.right.Len() {
q.right.PushFront(q.left.PopBack())
} else if q.right.Len() > q.left.Len()+1 {
q.left.PushBack(q.right.PopFront())
}
}
func (q *FrontMiddleBackQueue) PushFront(val int) {
q.left.PushFront(val)
q.balance()
}
func (q *FrontMiddleBackQueue) PushMiddle(val int) {
if q.left.Len() < q.right.Len() {
q.left.PushBack(val)
} else {
q.right.PushFront(val)
}
}
func (q *FrontMiddleBackQueue) PushBack(val int) {
q.right.PushBack(val)
q.balance()
}
func (q *FrontMiddleBackQueue) PopFront() (val int) {
if q.right.Len() == 0 { // 整个队列为空
return -1
}
if q.left.Len() > 0 {
val = q.left.PopFront()
} else {
val = q.right.PopFront()
}
q.balance()
return
}
func (q *FrontMiddleBackQueue) PopMiddle() int {
if q.right.Len() == 0 { // 整个队列为空
return -1
}
if q.left.Len() == q.right.Len() {
return q.left.PopBack()
}
return q.right.PopFront()
}
func (q *FrontMiddleBackQueue) PopBack() int {
if q.right.Len() == 0 { // 整个队列为空
return -1
}
val := q.right.PopBack()
q.balance()
return val
}
// 两个 slice 头对头，即可实现双端队列
// 但这并不是一个「工业级」的实现，因为 slice 没有「缩容」的概念
// 这意味着在大量的 pop 操作后，会产生大量无法被自动 GC 的空间
type Deque struct {
left []int
right []int
}
func (q Deque) Empty() bool {
return len(q.left) == 0 && len(q.right) == 0
}
func (q Deque) Len() int {
return len(q.left) + len(q.right)
}
func (q *Deque) PushFront(v int) {
q.left = append(q.left, v)
}
func (q *Deque) PushBack(v int) {
q.right = append(q.right, v)
}
func (q *Deque) PopFront() (v int) {
if len(q.left) > 0 {
q.left, v = q.left[:len(q.left)-1], q.left[len(q.left)-1]
} else {
v, q.right = q.right[0], q.right[1:]
}
return
}
func (q *Deque) PopBack() (v int) {
if len(q.right) > 0 {
q.right, v = q.right[:len(q.right)-1], q.right[len(q.right)-1]
} else {
v, q.left = q.left[0], q.left[1:]
}
return
}
用官方题解评论区大佬的话来说就是，双端队列考思路，链表解法考代码能力。这就是这道题考察的点。
结语
终于，又做出了一道每日一题，晕倒了
