建立网站第一步,整站seo优化公司,wordpress商品资源,北京网站备案拍照地点文章目录 一、题目二、C# 题解 一、题目 堆盘子。设想有一堆盘子#xff0c;堆太高可能会倒下来。因此#xff0c;在现实生活中#xff0c;盘子堆到一定高度时#xff0c;我们就会另外堆一堆盘子。请实现数据结构 SetOfStacks#xff0c;模拟这种行为。SetOfStacks 应该由… 文章目录 一、题目二、C# 题解 一、题目 堆盘子。设想有一堆盘子堆太高可能会倒下来。因此在现实生活中盘子堆到一定高度时我们就会另外堆一堆盘子。请实现数据结构 SetOfStacks模拟这种行为。SetOfStacks 应该由多个栈组成并且在前一个栈填满时新建一个栈。此外SetOfStacks.push() 和 SetOfStacks.pop() 应该与普通栈的操作方法相同也就是说pop()返回的值应该跟只有一个栈时的情况一样。 进阶实现一个 popAt(int index) 方法根据指定的子栈执行pop操作。 当某个栈为空时应当删除该栈。当栈中没有元素或不存在该栈时poppopAt 应返回 -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] 二、C# 题解 这题不难但是很繁琐。尤其是题目没有说明清楚不仅不给出数据规模而且还会出现栈的大小为 0 的情况真是绷不住了。当中间栈有元素弹出时后面的元素并不前移这点题目也没说也是挺离谱的。
public class StackOfPlates {private class Node {public int val 0; // 若作为头结点则表示该链表串联的元素个数public Node next null;public Node(int v, Node n) {val v;next n;}}private Node[] stack; // 头结点数组每个结点连接一个链表表示一个栈private int MAX_CAP, p -1; // MAX_CAP 表示每个栈最多有几个盘子p 用于指向当前栈private static int MAX_STACK_NUM 999; // 栈的最大个数public StackOfPlates(int cap) {MAX_CAP cap;stack new Node[MAX_STACK_NUM];}public void Push(int val) {// 前置判断条件不给放盘子或者栈达到最大个数if (MAX_CAP 0 || p MAX_STACK_NUM - 1 stack[p].val MAX_CAP) return; // 如果 p 为 -1 或当前栈满则激活新栈if (p -1 || stack[p].val MAX_CAP) stack[p] new Node(0, null); // 压入元素stack[p].next new Node(val, stack[p].next);stack[p].val;}public int Pop() {// 前置判断条件不给放盘子或者没有栈if (MAX_CAP 0 || p -1) return -1; // 弹出元素int result stack[p].next.val;stack[p].next stack[p].next.next;stack[p].val--;// 如果当前栈满则指针前移if (stack[p].val 0) stack[p--] null;return result;}public int PopAt(int index) {// 前置判断条件不给放盘子或没有栈if (MAX_CAP 0 || stack[index] null) return -1;// 弹出元素int result stack[index].next.val;stack[index].next stack[index].next.next;stack[index].val--;// 移除后栈为空则将后面的栈前移if (stack[index].val 0) {for (int i index; i p; i) {stack[i].next stack[i 1].next;stack[i].val stack[i 1].val;stack[i 1].next null;}stack[p--] null;}return result;}
}/*** 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);*/时间复杂度 O ( 1 ) O(1) O(1)。空间复杂度 O ( n ) O(n) O(n)。
