堆盘子

面试题 03.03. 堆盘子

堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。

当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.

示例1:

 输入：
["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
[[1], [1], [2], [1], [], []]
 输出：
[null, null, null, 2, 1, -1]

示例2:

 输入：
["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]
[[2], [1], [2], [3], [0], [0], [0]]
 输出：
[null, null, null, null, 2, 1, 3]

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class StackOfPlates { public: StackOfPlates(int cap) { } void push(int val) { } int pop() { } int popAt(int index) { } }; /** * Your StackOfPlates object will be instantiated and called as such: * StackOfPlates* obj = new StackOfPlates(cap); * obj->push(val); * int param_2 = obj->pop(); * int param_3 = obj->popAt(index); */

golang 解法, 执行用时: 40 ms, 内存消耗: 10 MB, 提交时间: 2022-12-02 11:35:28

type StackOfPlates struct {
	Cap       int
	Stack     [][]int
}


func Constructor(cap int) StackOfPlates {
	s := StackOfPlates{
		Cap:cap,
		Stack:make([][]int, 0),
	}
	return s
}


func (this *StackOfPlates) Push(val int)  {
	if this.Cap == 0 {
		return
	}
	if len(this.Stack) == 0 {
		newPlate := make([]int, 0)
		newPlate = append(newPlate, val)
		this.Stack = append(this.Stack, newPlate)
		return
	}

	lastPlate := this.Stack[len(this.Stack) - 1]
	if len(lastPlate) == this.Cap {
		newPlate := make([]int, 0)
		newPlate = append(newPlate, val)
		this.Stack = append(this.Stack, newPlate)
		return
	}

	lastPlate = append(lastPlate, val)
	this.Stack[len(this.Stack) - 1] = lastPlate
}


func (this *StackOfPlates) Pop() int {
	if len(this.Stack) == 0 {
		return -1
	}
	plate := this.Stack[len(this.Stack) - 1]
	v := plate[len(plate) - 1]
	plate = plate[0:len(plate)-1]
	this.Stack[len(this.Stack) - 1] = plate
	if len(plate) == 0 {
		this.Stack = this.Stack[0:len(this.Stack) - 1]
	}
	return v
}


func (this *StackOfPlates) PopAt(index int) int {
	n := len(this.Stack)
	if index >= n {
		return -1
	}

	plate := this.Stack[index]
	v := plate[len(plate) - 1]
	plate = plate[0:len(plate) - 1]
	this.Stack[index] = plate

	if len(plate) == 0 {
		tmp := this.Stack[index+1:]
		this.Stack = this.Stack[:index]
		this.Stack = append(this.Stack, tmp...)
	}

	return v
}


/**
 * Your StackOfPlates object will be instantiated and called as such:
 * obj := Constructor(cap);
 * obj.Push(val);
 * param_2 := obj.Pop();
 * param_3 := obj.PopAt(index);
 */

python3 解法, 执行用时: 88 ms, 内存消耗: 22.1 MB, 提交时间: 2022-12-02 11:34:18

class StackOfPlates:

    def __init__(self, cap: int):
        self.cap = cap
        self.fullstack = [[]]

    def push(self, val: int) -> None:
        if self.cap <= 0:
            # 如果初始容量小于0 直接return

            return
        if len(self.fullstack)==0 or len(self.fullstack[-1]) == self.cap:
            # 当栈满了，或没有栈了，则新建一个栈
            self.fullstack.append([])

        self.fullstack[-1].append(val)

    def pop(self) -> int:
        if not self.fullstack or not self.fullstack[-1]:
            return -1

        ans = self.fullstack[-1].pop(-1)
        if len(self.fullstack[-1]) == 0:
            # 如果pop后栈为空，则删除该栈
            self.fullstack.pop(-1)
        return ans

    def popAt(self, index: int) -> int:
        if index >= len(self.fullstack) or not self.fullstack[index]:
            return -1

        popitem = self.fullstack[index].pop(-1)
        if len(self.fullstack[index]) == 0:
            self.fullstack.pop(index)

        return popitem


# Your StackOfPlates object will be instantiated and called as such:
# obj = StackOfPlates(cap)
# obj.push(val)
# param_2 = obj.pop()
# param_3 = obj.popAt(index)

python3 解法, 执行用时: 96 ms, 内存消耗: 22.4 MB, 提交时间: 2022-12-02 11:33:20

class StackOfPlates:

    def __init__(self, cap: int):
        self.cap = cap
        self.array = []

    def push(self, val: int) -> None:
        # 处理边界情况：cap == 0 不让push
        if self.cap == 0:
            return

        if not self.array or len(self.array[-1]) >= self.cap:
            self.array.append([val])
        else:
            self.array[-1].append(val)

    def pop(self) -> int:
        val = -1
        if self.array and self.array[-1]:
            val = self.array[-1].pop()
            if not self.array[-1]: self.array.pop()
        return val

    def popAt(self, index: int) -> int:
        val = -1
        if len(self.array) >= index + 1:
            val = self.array[index].pop()
            if not self.array[index]: self.array.pop(index)
        return val




# Your StackOfPlates object will be instantiated and called as such:
# obj = StackOfPlates(cap)
# obj.push(val)
# param_2 = obj.pop()
# param_3 = obj.popAt(index)

cpp 解法, 执行用时: 48 ms, 内存消耗: 26.9 MB, 提交时间: 2022-12-02 11:31:28

class StackOfPlates {
private:
    vector<stack<int>> stacks;
    int capacity;

public:
    StackOfPlates(int cap) : capacity(cap) {}

    void push(int val) {
        if (capacity > 0) {
            if (stacks.empty() or static_cast<int>(stacks.back().size()) >= capacity)
                stacks.emplace_back();
            stacks.back().emplace(val);
        }
    }

    int pop() {
        return popAt(static_cast<int>(stacks.size()) - 1);
    }

    int popAt(int index) {
        int res = -1;
        if (index >= 0 and index < static_cast<int>(stacks.size())) {
            res = stacks[index].top();
            stacks[index].pop();
            if (stacks[index].empty())
                stacks.erase(next(stacks.begin(), index));
        }
        return res;
    }
};

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates* obj = new StackOfPlates(cap);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAt(index);
 */

上一题

下一题

详情