首页 / JAVA / Java栈 习题回顾
Java栈 习题回顾
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java栈 习题回顾，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6095字，纯文字阅读大概需要9分钟。
内容图文
1.栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
示例1
输入：[1,2,3,4,5],[4,3,5,1,2]
输出：false
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0){
return false;
}
int popIndex = 0; //表示弹出序列popA的的下标
//借助辅助栈
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < pushA.length; i++){
//不断把pushA中元素压入辅助栈中，当栈顶元素和popA元素不相等继续入栈
stack.push(pushA[i]);
//当栈顶元素和popA元素相等时，开始出栈
while(!stack.isEmpty() && stack.peek() == popA[popIndex]){
stack.pop();
popIndex++;
}
}
//当辅助栈没有元素时，说明符合弹出顺序，返回true
return stack.isEmpty();
}
}
2.逆波兰表达式求值 leetcode 150
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
示例 1：
输入: [“2”, “1”, “+”, “3”, “*”]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入: [“4”, “13”, “5”, “/”, “+”]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入: [“10”, “6”, “9”, “3”, “+”, “-11”, “", “/”, "”, “17”, “+”, “5”, “+”]
输出: 22
解释:
该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String t : tokens) {
switch (t){
case "+":
stack.push(stack.pop() + stack.pop());
break;
case "-":
int num = stack.pop();
stack.push(stack.pop() - num);
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "/":
int num2 = stack.pop();
stack.push(stack.pop() / num2);
break;
default:
stack.push(Integer.valueOf(t));
}
}
return stack.pop();
}
3.棒球比赛 leetcode 682
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
整数 x - 表示本回合新获得分数 x
“+” - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
“D” - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
“C” - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
示例 1：
输入：ops = [“5”,“2”,“C”,“D”,"+"]
输出：30
解释：
“5” - 记录加 5 ，记录现在是 [5]
“2” - 记录加 2 ，记录现在是 [5, 2]
“C” - 使前一次得分的记录无效并将其移除，记录现在是 [5].
“D” - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
“+” - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
所有得分的总和 5 + 10 + 15 = 30
示例 2：
输入：ops = [“1”]
输出：1
public int calPoints(String[] ops) {
Stack<Integer> s=new Stack<>();
int top=0,tmp=0,sum=0;
for(String str:ops){
if(str.equals("C")){
sum-=s.pop();
}
else if(str.equals("D")){
sum+=s.push(2*s.peek());
}
else if(str.equals("+")){
top=s.pop();
tmp=top+s.peek();
s.push(top);
sum+=s.push(tmp);
}
else{
s.push(Integer.parseInt(str));
sum+=Integer.parseInt(str);
}
}
return sum;
}
/上面的方法是别人对官方方法进行优化，本质维护了栈，减少了时间
public int calPoints(String[] ops) {
Stack<Integer> stack = new Stack();
for(String op : ops) {
if (op.equals("+")) {
int top = stack.pop();
int newtop = top + stack.peek();
stack.push(top);
stack.push(newtop);
} else if (op.equals("C")) {
stack.pop();
} else if (op.equals("D")) {
stack.push(2 * stack.peek());
} else {
stack.push(Integer.valueOf(op));
}
}
int ans = 0;
for(int score : stack) ans += score;
return ans;
}
4.比较含有退格的字符串 leetcode 844
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：S = “ab#c”, T = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：S = “ab##”, T = “c#d#”
输出：true
解释：S 和 T 都会变成 “”。
示例 3：
输入：S = “a##c”, T = “#a#c”
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：
输入：S = “a#c”, T = “b”
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
1.双栈思想
public boolean backspaceCompare(String S, String T) {
Stack<Character> stackS = new Stack<>();
Stack<Character> stackT = new Stack<>();
char[] sArr = S.toCharArray(), tArr = T.toCharArray();
for (int i = 0; i < sArr.length; i++) {
if (sArr[i] == '#') {
if (!stackS.isEmpty()) {
stackS.pop();
}
} else {
stackS.push(sArr[i]);
}
}
for (int i = 0; i < tArr.length; i++) {
if (tArr[i] == '#') {
if (!stackT.isEmpty()) {
stackT.pop();
}
} else {
stackT.push(tArr[i]);
}
}
while (!stackS.isEmpty() && !stackT.isEmpty()) {
if (stackS.peek() != stackT.peek()) return false;
stackS.pop();
stackT.pop();
}
return stackS.isEmpty() && stackT.isEmpty();
}
2.
public boolean backspaceCompare(String S, String T) {
return build(S).equals(build(T));
}
//用字符串实现栈的思想也可以 比如下面注释的ret
public String build(String str) {
// StringBuffer ret = new StringBuffer();
Stack<Character> stack = new Stack<>();
// int length = str.length();
char[] arr= str.toCharArray(); //把字符串转换为字符数组
for (int i = 0; i < arr.length; ++i) {
char ch = str.charAt(i);
//当元素不为#时，添加在ret后面
if (ch != '#') {
// ret.append(ch);
stack.push(ch);
} else {
//当元素为#时，判断ret的长度，当长度大于0时，删除上一个添加的元素
if (!stack.isEmpty()) {
// ret.deleteCharAt(ret.length() - 1);
stack.pop();
}else{
continue;
}
}
}
// return ret.toString();
return String.valueOf(stack);
}
内容总结
以上是互联网集市为您收集整理的Java栈 习题回顾全部内容，希望文章能够帮你解决Java栈 习题回顾所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。