【LeetCode】每日一题 2023_11_28 设计前中后队列（数组/链表/双端队列）

刷题前唠嗑

LeetCode？启动！！！

这道题的难度，才是我想象中的中等题的难度好吧，昨天那玩意对我来说还是太难了。。。

题目：设计前中后队列

题目链接：1670. 设计前中后队列

题目描述

代码与解题思路

type FrontMiddleBackQueue struct {queue []intsize int
}func Constructor() FrontMiddleBackQueue {return FrontMiddleBackQueue {queue: make([]int, 1001), size: 0,}
}func (this *FrontMiddleBackQueue) PushFront(val int)  {tmp := make([]int, 1001)tmp[0] = valfor i := 1; i < this.size+1; i++ {tmp[i] = this.queue[i-1]}this.queue = tmpthis.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] = valfor i := this.size/2+1; i < this.size+1; i++ {tmp[i] = this.queue[i-1]}this.queue = tmpthis.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] = valthis.queue = tmpthis.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.Listright *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  *Dequeright *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  []intright []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
}

用官方题解评论区大佬的话来说就是，双端队列考思路，链表解法考代码能力。这就是这道题考察的点。

结语

终于，又做出了一道每日一题，晕倒了