网站建设问题清单,开发app软件需要多少费用,酒店管理专业建设规划,wordpress侧边栏缩略图1.用两个栈实现一个队列。队列的声明如下#xff0c;请实现它的两个函数 appendTail 和 deleteHead #xff0c;分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素#xff0c;deleteHead 操作返回 -1 )
解题过程记录#xff1a;本题就是用两个栈请实现它的两个函数 appendTail 和 deleteHead 分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素deleteHead 操作返回 -1 )
解题过程记录本题就是用两个栈其中一个作为输入栈另外一个作为输出栈由于栈的特点是先进后出有序数字全部进栈然后再出栈会使这个数字序列逆序然后逆序数字序列再一次经过进栈出栈操作会再次逆序经过这两次逆序原本的数字序列的顺序会保持不变符合队列先进先出的特点。
第一次提交未通过出队列时直接把输入栈的数字压入输出栈忽略了此时输出栈中可能还会有数据如果输出栈中有数据序列顺序前后并不符合先进先出的特点。
class CQueue {StackIntegers1null,s2null;public CQueue() {s1new Stack();s2new Stack();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {while(!s1.isEmpty()){s2.push(s1.pop());}if (s2.isEmpty()){return -1;}return s2.pop();}
}
第二次提交未通过调用appendTail函数出队列先判断s1输入栈中是否有数据如果有并且s2输出栈中为空将s1的数据全部压入s2输出栈两栈全为空返回-1。思路混乱错误
class CQueue {StackIntegers1null,s2null;public CQueue() {s1new Stack();s2new Stack();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {while(!s1.isEmpty()){if(s2.isEmpty()){s2.push(s1.pop());}}if (s2.isEmpty()){return -1;}return s2.pop();}
}
第三次提交通过 只有出stack为空的时候才将进stack的数据全部倒入出stack。
class CQueue {StackIntegers1null,s2null;public CQueue() {s1new Stack();s2new Stack();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {if (s2.isEmpty()){if(s1.isEmpty()){return -1;}while(!s1.isEmpty()){s2.push(s1.pop());}}return s2.pop();}
}2.定义栈的数据结构请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中调用 min、push 及 pop 的时间复杂度都是 O(1)。示例 inStack minStack new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); -- 返回 -3.
minStack.pop();
minStack.top(); -- 返回 0.
minStack.min(); -- 返回 -2.
解法一使用主栈s存储数字序列用一个辅助栈stackTemp同步记录主栈中的最小值。具体来说当一个元素要入栈时我们取当前辅助栈的栈顶存储的最小值与当前元素比较得出最小值将这个最小值插入辅助栈中当一个元素要出栈时我们把辅助栈的栈顶元素也一并弹出在任意一个时刻栈内元素的最小值就存储在辅助栈的栈顶元素中。
class MinStack {/** initialize your data structure here. */StackInteger snull;StackIntegerstackTempnull;public MinStack() {snew Stack();stackTempnew Stack();}public void push(int x) {s.push(x);if(stackTemp.isEmpty()){stackTemp.push(x);}else{stackTemp.push(Math.min(x,stackTemp.peek()));}}public void pop() {s.pop();stackTemp.pop();}public int top() {return s.peek();}public int min() {return stackTemp.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj new MinStack();* obj.push(x);* obj.pop();* int param_3 obj.top();* int param_4 obj.min();*/
解法二不使用辅助栈保留当前最小值和差值这种方法称为差值法。
解法思路讲解差值法就是在向栈中插入数据的同时同步记录并更新栈中的最小值向栈中插入值x栈中保存的不再是原值而是x与最小值的差值即x-min。按照这种思路push函数如下
public void push(int x) {if (stack.isEmpty()) {stack.push(x);min x;//栈为空插入的第一个值作为当前最小值} else {stack.push(x - min);//栈不为空后续插入栈中的值是x-minmin Math.min(min, x);//每插入一个新值需要同步更新最小值}}
入栈序列523-21栈实际保存的值5-31-43当前最小值522-2-2
如果用min记录当前栈中的最小值用min与栈中的元素进行运算就很容易复原原序列的真实值。通过上面的表格举个例子入栈序列5 2 3 -2 1 经过x-min运算存入栈中实际值为 5 -3 1 -4 3。此时栈顶元素为3是一个整数即x-min0,也即xmin说明x不是最小值如果此时查看栈顶元素直接返回min栈顶元素即可复原真实值但是如果栈顶元素为负数说明入栈的元素比当前栈中的最小值还要小那么最小值min就是原值x还有一种特殊情况由于我们向栈中插入第一个元素的时候没有做x-min操作而是直接将真实值插入栈中并且将它作为最小值所以当栈中仅有一个元素的时候栈顶元素min真实值。综合上述三种情况故top函数 public int top() {if (stack.peek() 0 || stack.size()1) {return min;} else {return (min stack.peek());}}
前面我们分析过如果当前栈顶元素为正数说明该元素不与最小值对应可以直接pop无需更新min;如果栈顶元素为负数说明该元素与最小值对应而且pop出的元素就是最小值pop出后我们需要确定栈中剩余元素的最小值,假设push该元素的时候插入栈中的值为value,那么valuex-min公式变形得minx-value。经过上面的分析pop函数为 public void pop() {if (stack.peek() 0) {min min - stack.pop();} else {stack.pop();}} 我们回看push函数中的一行代码 stack.push(x - min) 这里题目要求传入的值x是int类型假设x为Integer.MAX_VALUEmin为Integer.MIN_VALUE这样x-min运算势必会溢出因此min需要改为long 类型相关的算数运算也要在long类型下进行因此代码优化为
import java.util.Stack;public class MinStack {StackLong stack null;long min;public MinStack() {stack new Stack();}public void push(int x) {if (stack.isEmpty()) {stack.push((long)x);min (long)x;} else {stack.push((long)(x - min));min Math.min(min, x);}}public void pop() {if (stack.peek() 0) {min min - stack.pop();} else {stack.pop();}}public int top() {if (stack.peek() 0 || stack.size()1) {return (int)min;} else {return (int)(min stack.peek());}}public int min() {return (int)min;}
}
