【一道难题】,Python交流,技术交流,鱼C论坛

Hello. 发表于 2020-6-18 21:16:42

【一道难题】

本帖最后由 Hello. 于 2020-6-18 21:18 编辑

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 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"]
[,,,,,,,,,,,[],[],[],[],[]]
输出：

解释：
DinnerPlates D = DinnerPlates(2);// 初始化，栈最大容量 capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);       // 栈的现状为： 24
                                 135
                                 ﹈﹈﹈
D.popAtStack(0); // 返回 2。栈的现状为：    4
                                       135
                                       ﹈﹈﹈
D.push(20);    // 栈的现状为：204
                              135
                              ﹈﹈﹈
D.push(21);    // 栈的现状为：204 21
                              135
                              ﹈﹈﹈
D.popAtStack(0); // 返回 20。栈的现状为：    4 21
                                       135
                                       ﹈﹈﹈
D.popAtStack(2); // 返回 21。栈的现状为：    4
                                       135
                                       ﹈﹈﹈
D.pop()          // 返回 5。栈的现状为：    4
                                       13
                                       ﹈﹈
D.pop()          // 返回 4。栈的现状为： 13
                                       ﹈﹈
D.pop()          // 返回 3。栈的现状为： 1
                                       ﹈
D.pop()          // 返回 1。现在没有栈。
D.pop()          // 返回 -1。仍然没有栈。

提示：

1 <= capacity <= 20000
1 <= val <= 20000
0 <= index <= 100000
最多会对 push，pop，和 popAtStack 进行 200000 次调用

卡了两小时，希望大牛点拨一下！{:10_281:}

Hello. 发表于 2020-6-18 21:20:07

﹈好吧这个东东打不出来

赚小钱 发表于 2020-6-18 22:20:22

不会写python，可以提供一下我的思路。
需要编写两个类 `class Stack` 与 `class DinnerPlates`

class Stack {
int pop();
void push();
bool is_full();
bool is_empty();
}

class DinnerPlates {
map<int, Stack> buckets; // 虽然有无限个栈，但是在代码中，不能真有无限个，内存受不了，因此 key: >=0 stack 的编号， value: stack
int capacity,
}

永恒的蓝色梦想 发表于 2020-6-19 10:05:38

本帖最后由永恒的蓝色梦想于 2020-6-19 10:44 编辑

力扣上不是有题解吗……可以参考一下的

java2python 发表于 2020-6-19 13:30:14

确实，网上检索“LeetCode-Python-1172”

赚小钱 发表于 2020-6-19 15:10:52

赚小钱发表于 2020-6-18 22:20
不会写python，可以提供一下我的思路。
需要编写两个类 `class Stack` 与 `class DinnerPlates`

自己做了一下，原来还有时间要求。
我在 DinnerPlates的数据结构中，添加了两个 Heap，元素为 stack 的 index。
一个在 Push 时使用，保存所有不满的stack的index，一个在 Pop 时使用，保存所有非空的stack 的index。
因为Push要求从左到右的顺序，所以，是一个最小堆。
Pop 要求从右到左的顺序，所以，是一个最大堆。

java2python 发表于 2020-6-19 19:32:56

你可能用的是C，怎么语句后面都是分号：
用python写了个，没有用python的heapq
#DinnerPlates(int capacity) - 给出栈的最大容量 capacity。
#void push(int val) - 将给出的正整数 val 推入从左往右第一个没有满的栈。
#int pop() - 返回从右往左第一个非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。
#int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。

class DP:
stacks = []
stacks_index = []
capacity = 5

@staticmethod
def DinnerPlates(capacity):
   DP.capacity = capacity

@staticmethod
def free_pos(start=None, end =None):
   if start == None:
         start,end = 0,len(DP.stacks)
   selected = DP.stacks_index
   return (end-start)* DP.capacity - sum(DP.stacks_index)

@staticmethod
def first_free(start,end):
   if start == end-1:
         if DP.stacks_index < DP.capacity:
            return start
         else:
            return -1

   middle = (start + end)//2
   part1 = DP.first_free(start,middle)
   return part1 if part1 !=-1 else DP.first_free(middle,end)

@staticmethod
def first_filled(start,end):
   if start == end-1:
         if DP.stacks_index > 0:
            return start
         else:
            return -1

   middle = (start + end)//2
   part1 = DP.first_filled(middle,end)
   return part1 if part1 !=-1 else DP.first_filled(start,middle)

@staticmethod
def push(val):
   if DP.free_pos()>0:
         index = DP.first_free(0,len(DP.stacks))
   else:
         index = len(DP.stacks)
         stack = [-1 for i in range(DP.capacity)]
         DP.stacks.append(stack)
         DP.stacks_index.append(0)
   DP.stacks] = val
   DP.stacks_index += 1
@staticmethod
def pop():
   if sum(DP.stacks_index) == 0:
         return -1
   else:
         index = DP.first_filled(0,len(DP.stacks))
         DP.stacks_index -= 1
         return DP.stacks]
@staticmethod
def popAtStack(index):
   if index < len(DP.stacks) and DP.stacks_index > 0:
         DP.stacks_index -= 1
         return DP.stacks]
   else:
         return -1

DP.DinnerPlates(2)
DP.push(1)
DP.push(2)
DP.push(3)
DP.push(4)
DP.push(5)
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.popAtStack(0)
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.push(20)
print(DP.stacks,DP.stacks_index,DP.capacity)
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.popAtStack(0)
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.push(20)
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.push(21)
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.popAtStack(0)
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.popAtStack(2)
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.pop()
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.pop()
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.pop()
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.pop()
print(DP.stacks,DP.stacks_index,DP.capacity)
DP.pop()
print(DP.stacks,DP.stacks_index,DP.capacity)

结果（栈列表，以及各栈的栈顶指针，指针为零，栈内值不设置为-1的，主要看栈顶指针）：
栈列表，栈顶指针，最后一个2是容量（这个可以无视）
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2
[, , ] 2

lijiachen 发表于 2020-6-20 11:36:47

java2python 发表于 2020-6-19 19:32
你可能用的是C，怎么语句后面都是分号：
用python写了个，没有用python的heapq

{:10_275:}

页: [1]

鱼C论坛's Archiver

【一道难题】