【一道难题】

Hello.

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

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

  提示：

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

卡了两小时，希望大牛点拨一下！

Hello.

﹈好吧这个东东打不出来

赚小钱

不会写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,
}

永恒的蓝色梦想

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

java2python

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

赚小钱

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

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

java2python

你可能用的是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[start:end]
        return (end-start)* DP.capacity - sum(DP.stacks_index)
        
    @staticmethod
    def first_free(start,end):
        if start == end-1:
            if DP.stacks_index[start] < 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[start] > 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[index][DP.stacks_index[index]] = val
        DP.stacks_index[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[index] -= 1
            return DP.stacks[index][DP.stacks_index[index]]
    @staticmethod
    def popAtStack(index):
        if index < len(DP.stacks) and DP.stacks_index[index] > 0:
            DP.stacks_index[index] -= 1
            return DP.stacks[index][DP.stacks_index[index]]
        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是容量（这个可以无视）
[[1, 2], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 2], [3, 4], [5, -1]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, 21]] [2, 2, 2] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 2] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 0] 2
[[1, 20], [3, 4], [5, 21]] [1, 1, 0] 2
[[1, 20], [3, 4], [5, 21]] [1, 0, 0] 2
[[1, 20], [3, 4], [5, 21]] [0, 0, 0] 2
[[1, 20], [3, 4], [5, 21]] [0, 0, 0] 2

lijiachen

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