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

文章目录

刷题前唠嗑
题目：设计前中后队列
- 题目描述
- 代码与解题思路
- 偷看大佬题解
结语

刷题前唠嗑

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
}