2024-03-09:用go语言,我们把无限数量的栈排成一行,按从左到右的次序

2024-03-09:用go语言,我们把无限数量的栈排成一行,按从左到右的次序从 0 开始编号,

每个栈的的最大容量 capacity 都相同。实现一个叫「餐盘」的类 DinnerPlates,

DinnerPlates(int capacity) - 给出栈的最大容量 capacity,

void push(int val) 将给出的正整数 val 推入 从左往右第一个 没有满的栈,

int pop() 返回 从右往左第一个 非空栈顶部的值,并将其从栈中删除,

如果所有的栈都是空的,请返回 -1。

int popAtStack(int index) - 返回编号 index 的栈顶部的值,并将其从栈中删除,

如果编号 index 的栈是空的,请返回 -1。

输入:[“DinnerPlates”,”push”,”push”,”push”,”push”,”push”,”popAtStack”,”push”,”push”,”popAtStack”,”popAtStack”,”pop”,”pop”,”pop”,”pop”,”pop”][[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]。

输出:[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]。

答案2024-03-09:

来自左程云

灵捷3.5

大体步骤如下:

这个问题需要实现一个类 DinnerPlates,其中含有 ConstructorPushPopPopAtStack 四个方法。这个类可以理解成是具有固定容量的多个栈构成的一种数据结构。根据题目描述和提供的 Go 代码文件,这里来分步骤描述大体过程,然后讨论总的时间复杂度和总的空间复杂度。

1.Constructor:

  • 当创建 DinnerPlates 实例时,通过调用 Constructor 方法初始化一个 DinnerPlates 类型的实例。需要传入一个参数 capacity 表示栈的最大容量。在这个方法中,将 capacity 存储到实例字段中,并初始化 stacktoppoppedPos 三个切片。

2.Push:

  • 当调用 Push 方法时,将给定的整数值 val 推入从左到右第一个没有满的栈。

  • 如果所有栈都已满,应该创建一个新的栈来存储 val

  • 如果有栈未满,则将 val 推入最左侧未满的栈中,并更新 top 数组和 stack 数组。

3.Pop:

  • 当调用 Pop 方法时,应该返回最右侧非空栈顶的值,并将其从栈中删除。如果所有的栈都为空,返回 -1。

  • 如果有非空的栈,应该找到最右侧非空栈并返回它的栈顶的值,然后将其值从栈中删除。

4.PopAtStack:

  • 当调用 PopAtStack 方法时,应该返回指定 index 栈的栈顶的值,并将其从栈中删除。如果指定 index 的栈为空,返回 -1。

  • 需要更新 top 数组和 poppedPos 数组,以确保栈的一致性。

总的时间复杂度:

  • Push 方法的时间复杂度为 O(1)。

  • Pop 方法的时间复杂度为 O(1)。

  • PopAtStack 方法的时间复杂度为 O(log n),其中 n 是被删除的元素的数量。

总的空间复杂度:

  • 需要 O(n) 的空间来存储栈中的所有元素,其中 n 是所有栈的元素数量。

    go完整代码如下:

package main

import (
    "fmt"
    "sort"
)

type DinnerPlates struct {
    capacity  int
    stack     []int
    top       []int
    poppedPos []int
}

func Constructor(capacity int) DinnerPlates {
    return DinnerPlates{capacity, []int{}, []int{}, []int{}}
}

func (this *DinnerPlates) Push(val int) {
    if len(this.poppedPos) == 0 {
        pos := len(this.stack)
        this.stack = append(this.stack, val)
        if pos%this.capacity == 0 {
            this.top = append(this.top, 0)
        } else {
            stackPos := len(this.top) - 1
            stackTop := this.top[stackPos]
            this.top[stackPos] = stackTop + 1
        }
    } else {
        pos := this.poppedPos[0]
        this.poppedPos = this.poppedPos[1:]
        this.stack[pos] = val
        index := pos / this.capacity
        stackTop := this.top[index]
        this.top[index] = stackTop + 1
    }
}

func (this *DinnerPlates) Pop() int {
    for len(this.stack) > 0 && len(this.poppedPos) > 0 && this.poppedPos[len(this.poppedPos)-1] == len(this.stack)-1 {
        this.stack = this.stack[:len(this.stack)-1]
        pos := this.poppedPos[len(this.poppedPos)-1]
        this.poppedPos = this.poppedPos[:len(this.poppedPos)-1]
        if pos%this.capacity == 0 {
            this.top = this.top[:len(this.top)-1]
        }
    }
    if len(this.stack) == 0 {
        return -1
    } else {
        pos := len(this.stack) - 1
        val := this.stack[pos]
        this.stack = this.stack[:pos]
        if pos%this.capacity == 0 && len(this.top) > 0 {
            this.top = this.top[:len(this.top)-1]
        } else if len(this.top) > 0 {
            this.top[len(this.top)-1] -= 1
        }
        return val
    }
}

func (this *DinnerPlates) PopAtStack(index int) int {
    if index >= len(this.top) {
        return -1
    }
    stackTop := this.top[index]
    if stackTop < 0 {
        return -1
    }
    this.top[index] = stackTop - 1
    pos := index*this.capacity + stackTop
    i := sort.SearchInts(this.poppedPos, pos)
    this.poppedPos = append(this.poppedPos, 0)
    copy(this.poppedPos[i+1:], this.poppedPos[i:])
    this.poppedPos[i] = pos
    return this.stack[pos]
}

func main() {
    dinnerPlates := Constructor(2)
    dinnerPlates.Push(1)
    dinnerPlates.Push(2)
    dinnerPlates.Push(3)
    dinnerPlates.Push(4)
    dinnerPlates.Push(5)
    fmt.Println(dinnerPlates.PopAtStack(0))
    dinnerPlates.Push(20)
    dinnerPlates.Push(21)
    fmt.Println(dinnerPlates.PopAtStack(0))
    fmt.Println(dinnerPlates.PopAtStack(2))
    fmt.Println(dinnerPlates.Pop())
    fmt.Println(dinnerPlates.Pop())
    fmt.Println(dinnerPlates.Pop())
    fmt.Println(dinnerPlates.Pop())
    fmt.Println(dinnerPlates.Pop())
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
471
粉丝
21
喜欢
37
收藏
22
排名:457
访问:1.9 万
私信
所有博文
社区赞助商