面试 16:栈的压入压出队列(剑指 Offer 第 22 题) (2)

i = 1,栈内元素为{1,2,3},栈顶元素不等于 pop[1] = 5,进入 else 语句。push 数组还有数据,直接 push,结束后 j = 5,栈内元素为 {1,2,3,5},栈顶刚好等于 pop[1],故弹出数字 5,退出 while 循环;

i = 2,栈内元素为{1,2,3},栈顶元素刚刚等于 pop[2] ,弹出数字 3;

i = 3,栈内元素为 {1,2},栈顶元素刚等于 pop[3],弹出数字 2;

i = 4,栈内元素为 {1},栈顶元素刚刚等于 pop[4],弹出数字 1;

for 循环能直接执行结束,返回 ture,测试通过。

传入 {1,2,3,4,5} 和 {4,3,5,1,2}:

进入循环,i = 0,pop[i] = 4,由于同上,所以直接进入到上面的步骤 3;

此时 i = 1,栈内元素为 {1,2,3},因为栈顶元素等于 pop[1],弹出数字 3;

i = 2,栈内元素为 {1,2},栈顶元素不等于 pop[2],进入 else 语句,此时 push 数组还有元素 {5},所以进入 while 循环。push 后栈内元素为 {1,2,5},栈顶元素等于 pop[2],所以弹出数字 5,退出 while 循环;

i = 3,栈内元素为{1,2},pop[3] = 1,和栈顶元素不相等,所以进入 else 语句,由于 push 里面已经没有了元素,所以直接返回 false,测试通过。

传入 {1} 和 {2}:

进入循环,i = 0,pop[i] = 2,进入 else 语句,不相等,直接进入 while 循环,push 后栈内元素为 {1},栈顶元素和 pop[i] 不相等,此时 j = 1,不符合 while 循环条件。循环结束,外循环也结束,返回 true。测试不通过。

修复程序逻辑

所以我们现在应该着重处理一下单个数字的情况,分析后明显可以得到,我们要判断这种情况只需要再判断结束 for 循环后栈内是否还有元素和 push 里面还是否有元素即可。

所以在最后增加一个条件判断即可。

public class Test16 { private static boolean isPushStack(int[] push, int[] pop) { if (push == null || pop == null || pop.length != push.length) return false; Stack<Integer> stack = new Stack<>(); int j = 0; for (int i = 0; i < pop.length; i++) { // 第一步判断栈顶元素是否和 pop[i] 相等 if (!stack.isEmpty() && pop[i] == stack.peek()) { // 如果相等则直接 pop() stack.pop(); } else { // 栈顶和 pop[i] 不相等,则判断 push 数组还有没有数据 // 如果 push 数组没数据了,栈顶元素又不等于 pop[i],则说明不符合要求 if (j == push.length) return false; while (j < push.length) { // 如果还有数据,则直接 push stack.push(push[j]); ++j; // push 后继续判断栈顶元素是否和 pop[i] 相等; if (pop[i] == stack.peek()) { // 如果相等则弹出栈,并且推出内层循环 stack.pop(); break; } } } } // 增加判断 if (!stack.isEmpty() && j == push.length) return false; return true; } public static void main(String[] args) { int[] push = {1, 2, 3, 4, 5}; int[] pop1 = {4, 5, 3, 2, 1}; int[] pop2 = {3, 5, 4, 2, 1}; int[] pop3 = {4, 3, 5, 1, 2}; int[] pop4 = {3, 5, 4, 1, 2}; System.out.println(isPushStack(push, pop1)); System.out.println(isPushStack(push, pop2)); System.out.println(isPushStack(push, pop3)); System.out.println(isPushStack(push, pop4)); int[] push1 = {1}; int[] pop5 = {2}; System.out.println(isPushStack(push1, pop5)); int[] push2 = {1}; int[] pop6 = {1}; System.out.println(isPushStack(push2, pop6)); } }

上面在代码逻辑上并没有做多少操作,所以我们只需要再传入 {1} 和 {1} 测试就可以了。

直接进入到 while 循环,push 后栈内元素为 {1},因为栈顶元素刚刚等于 pop[0],所以推出数字 1。此后栈内无元素,所以直接返回 true。

总结

我亲爱的小伙伴想必也一定在上面的分析中收获到东西了吧,这也是南尘给大家的箴言。

在思路不是很清晰的时候画表或者画图来处理;

在验证测试用例的时候,一定从简单的开始,比如上面,我们其实更加建议先验证单个数字的情况。

拓展延伸

本次学习的方法将非常有效,不信大家可以试试下明天的拓展题。

面试题:从上到下打印二叉树的每个结点,同一层按照从左到右的顺序打印。例如数的结构如下:

​ 1
2 3
4 5 6 7

则依次打印 1、2、3、4、5、6、7

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpwdss.html