有关做美食的网站,公众号开发是前端还是后端,网络营销工具的作用,网站推广平台有哪些举例分析
与上两篇问中画图方法一样#xff0c;我们可以用举例模拟的方法思考分析复杂问题。当一眼不能看出问题的规律的时候#xff0c;我们可以用几个具体的例子来模拟一下问题的过程。这样就和我们在程序出现问题时候的debug一样#xff0c;走一下整个流程#xff0c;可…举例分析
与上两篇问中画图方法一样我们可以用举例模拟的方法思考分析复杂问题。当一眼不能看出问题的规律的时候我们可以用几个具体的例子来模拟一下问题的过程。这样就和我们在程序出现问题时候的debug一样走一下整个流程可以直观的看到整个过程。具体的例子还能帮助我们确保代码的质量在编码完成后可以将例子当做测试用例来模拟运行看每一步操作后的结果和我们预期的是不是一样的。
包含min方法的栈
题目定义栈的数据结构请在改类型中实现一个能够得到栈的最小元素min函数。在改栈中调用minpushpop的时间复杂度O(1)此处与普通栈不同点在于需要知道每次栈变动时候最小值。并且难点在于O(1)的时间复杂度我们第一反应是标记最小值这样可以在O(1)时间得到最小元素。但是最小值出栈后次小的值就变成最小值此时是无法获取这个值另外一个思路每次入栈对栈中元素进行排序这样能拿到最小值在栈首会在尾。但是这样就违背了栈的后进先出的原则就不是栈了。分析到此处发现一个栈A并不能解决问题我们用一个辅助的栈空间B每次添加一个元素到A时候将添加元素与最小元素比较临时变量保存最小元素将最小元素添加到B即使最小元素没有变化仍然重复添加到B占位用。我们用如下案例分析
步骤操作数据栈A辅助栈B最小值1压入33332压入63,63,333压入43,6,43,3,334压入453,6,4,453,3,3,335压入03,6,4,45,03,3,3,3,006压入23,6,4,45,0,23,3,3,3,0,00如上表格我们将最小元素每次都添加到辅助栈B中就能保证辅助栈的栈顶是最小元素。 当最小元素从数据栈弹窗我们同时操作辅助栈弹窗这样保证辅助栈下一个值是最小值。 每一步操作数据栈辅助站都同步可以保证辅助栈顶永远都是数据栈中所有数据的最小值 实现方法是在之前文章数据结构与算法–简单栈实现及其应用基础上完成。实现如下
/*** 包含min方法的栈实现* author liaojiamin* Date:Created in 16:02 2021/4/2*/
public class MyStackWithMin {private static MyStack dataStack new MyStack();private static MyStack minStack new MyStack();public static void push(int num){if(dataStack.size() 0 minStack.size() 0){dataStack.push(num);minStack.push(num);}else {dataStack.push(num);if((int)minStack.getTop() num){minStack.push(num);}else {minStack.push(minStack.getTop());}}}public static int pop(){if(dataStack.size() 0 || minStack.size() 0){return Integer.MAX_VALUE;}minStack.pop();return (int)dataStack.pop();}public static int min(){if(minStack.size() 0){return Integer.MAX_VALUE;}return (int)minStack.pop();}public static void main(String[] args) {Random random new Random();for (int i 0; i 100; i) {int temp random.nextInt(100);System.out.println(temp);push(temp);}System.out.println(min());}
}栈的压入弹出序列
题目输入两个整数序列第一个序列表示栈的压入顺序判断第二个序列是否可能是栈的弹出顺序假设入站的所有数字均不相等例如1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是可能的一个出栈但是4,3,5,1,2就不可能是出栈的方式我们依然用案例的方法分析如下表格分析题中两种情况。
步骤操作栈弹出数字1压入112压入21,23压入31,2,34压入41,2,3,45弹出1,2,346压入51,2,3,57弹出1,2,358弹出1,239弹出1210弹出1
如上表格中每一个步骤操作我们在第五步骤时候弹出4,压入5之后持续弹出就能得到对应的弹出序列。我们用同样的方式来递推第二个序列
步骤操作栈弹出数字1压入112压入21,23压入31,2,34压入41,2,3,45弹出1,2,346弹出1,237压入51,2,58弹出1,259下一个弹出的是1但是1 不在栈顶压栈序列已经都入栈操作无法继续
如上两表格分析入栈出栈过程我们可以判断一个序列是不是栈的弹出序列有如下规律 如果下一个弹出的数字正好是栈顶数字那么直接弹出如果下一个弹出的数字不在栈顶我们吧压栈序列中还没有入栈的数字压入辅助栈持续压入直到下一个需要弹出的数字压入栈顶位置如果所有数字都压入了栈但是还没找到下一个弹出的数字那么该序列不存在一个弹出序列。综上有如下实现
/*** 存在栈A的入栈系列S判断给出的序列B是否可能是A 的出序列例如1,2,3,4,5 入栈4,5,3,2,1 出栈* author liaojiamin* Date:Created in 16:54 2021/4/2*/
public class ValidateIsPopOrder {public static boolean validateIsPopOrder(int[] orderPush, int[] orderPop){if(orderPush null || orderPop null){return false;}if(orderPush.length ! orderPop.length){return false;}MyStack myStack new MyStack();int length orderPop.length;int pushPosition 0;int popPosition 0;while (pushPosition length || popPosition length){while (myStack.size() 0 (int)myStack.getTop() orderPop[popPosition] popPosition length){myStack.pop();popPosition;}if(pushPosition length){myStack.push(orderPush[pushPosition]);pushPosition ;}if(pushPosition length myStack ! null (int)myStack.getTop() ! orderPop[popPosition]){return false;}}return !(myStack.size() ! 0);}public static void main(String[] args) {int[] push {1,2,3,4,5};
// int[] pop {4,5,3,2,1};
// int[] pop {3,2,1,5,4};int[] pop {4,3,5,1,2};System.out.println(validateIsPopOrder(push, pop));}
}以上两个问题都是比较复杂的问题并且需要多个步骤分析才能得出结果初看时候很少有思路的这个时候我们通过举例分析一步一步来看当最后一步符合或者卡在某一个步骤时候我们此时往往能从当前的状态看出解题的思路。
上一篇数据结构与算法–解决问题的方法-顺时针打印矩阵 下一篇数据结构与算法–广度优先打印二叉树
