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
大体步骤如下:
这个问题需要实现一个类,其中含有、、和四个方法。这个类可以理解成是具有固定容量的多个栈构成的一种数据结构。根据题目描述和提供的 Go 代码文件,这里来分步骤描述大体过程,然后讨论总的时间复杂度和总的空间复杂度。
DinnerPlates
Constructor
Push
Pop
PopAtStack
1.Constructor:
- •当创建实例时,通过调用方法初始化一个 DinnerPlates 类型的实例。需要传入一个参数表示栈的最大容量。在这个方法中,将存储到实例字段中,并初始化、和三个切片。
- DinnerPlates
- Constructor
- capacity
- capacity
- stack
- top
- poppedPos
2.Push:
- •当调用方法时,将给定的整数值推入从左到右第一个没有满的栈。
- Push
- val
- •如果所有栈都已满,应该创建一个新的栈来存储。
- val
- •如果有栈未满,则将推入最左侧未满的栈中,并更新数组和数组。
- val
- top
- stack
3.Pop:
- •当调用方法时,应该返回最右侧非空栈顶的值,并将其从栈中删除。如果所有的栈都为空,返回 -1。
- Pop
- •如果有非空的栈,应该找到最右侧非空栈并返回它的栈顶的值,然后将其值从栈中删除。
4.PopAtStack:
- •当调用方法时,应该返回指定栈的栈顶的值,并将其从栈中删除。如果指定的栈为空,返回 -1。
- PopAtStack
- index
- index
- •需要更新数组和数组,以确保栈的一致性。
- top
- poppedPos
总的时间复杂度:
- •Push 方法的时间复杂度为 O(1)。
- •Pop 方法的时间复杂度为 O(1)。
- •PopAtStack 方法的时间复杂度为 O(log n),其中 n 是被删除的元素的数量。
总的空间复杂度:
- •需要 O(n) 的空间来存储栈中的所有元素,其中 n 是所有栈的元素数量。
- go完整代码如下:
packagemain
import(
"fmt"
"sort"
)
typeDinnerPlatesstruct{
capacityint
stack[]int
top[]int
poppedPos[]int
}
funcConstructor(capacityint)DinnerPlates{
returnDinnerPlates{capacity,[]int{},[]int{},[]int{}}
}
func(this*DinnerPlates)Push(valint){
iflen(this.poppedPos)==0{
pos:=len(this.stack)
this.stack=append(this.stack,val)
ifpos%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{
forlen(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]
ifpos%this.capacity==0{
this.top=this.top[:len(this.top)-1]
}
}
iflen(this.stack)==0{
return-1
}else{
pos:=len(this.stack)-1
val:=this.stack[pos]
this.stack=this.stack[:pos]
ifpos%this.capacity==0&&len(this.top)>0{
this.top=this.top[:len(this.top)-1]
}elseiflen(this.top)>0{
this.top[len(this.top)-1]-=1
}
returnval
}
}
func(this*DinnerPlates)PopAtStack(indexint)int{
ifindex>=len(this.top){
return-1
}
stackTop:=this.top[index]
ifstackTop<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
returnthis.stack[pos]
}
funcmain(){
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())
}
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.