文章目录
- 1.有效的括号
- 1.1题目
- 1.2解法：栈
- 2.删除字符串中的所有相邻重复项
- 2.1题目
- 2.2解法：栈
- 3.逆波兰表达式求值
- 3.1题目
- 3.2解法：栈
1.有效的括号
1.1题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号
- 示例一：
输入：s = "()"
输出：true
- 示例二：
输入：s = "()[]{}"
输出：true
- 示例三：
输入：s = "(]"
输出：false
1.2解法：栈
-
题目核心：要求左括号隔壁要有对应的有括号匹配
-
讨论三种不匹配的情况
-
字符串里左方向的括号多余了 ，所以不匹配
-
括号没有多余，但是 括号的类型没有匹配上
-
字符串里右方向的括号多余了，所以不匹配。
-
-
解法：栈
- 若为左括号，则将对应的右括号入栈
- 若为右括号，则取出栈顶元素，并判断是否该为右括号类型，不是返回false即可
- 相当于左括号——>同样类型的右括号进栈；右括号——>出栈（并判断栈顶元素是否为该类型的右括号）
-
注意：
- Java中Deuqe接口进栈方法为 push(i)；
- 查看栈顶元素方法为 peek()
- 取出栈顶元素方法为 pop()
public boolean isValid(String s) {
Deque<Character> deque=new LinkedList<>();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
//1、若为左括号，则将对应的右括号类型进栈
if(c=='('){
deque.push(')');
}else if(c=='{'){
deque.push('}');
}else if(c=='['){
deque.push(']');
}else if(deque.isEmpty() || deque.peek()!=c){
//2、右括号，取出栈顶元素并判断是否为该右括号类型
return false;
}else{
deque.pop();
}
}
return deque.isEmpty();
}
2.删除字符串中的所有相邻重复项
2.1题目
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
- 示例一：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
2.2解法：栈
- 核心：使用栈解法
- 若为栈为空或者插入元素与栈顶元素不相同，则插入该元素；否则将栈顶元素出栈
- 最后遍历栈，将栈顶元素放置在字符串前面
public String removeDuplicates(String s) {
Deque<Character> deque=new LinkedList<>();
char[] arr=s.toCharArray();
for(char ch:arr){
if(deque.isEmpty() || deque.peek()!=ch ){
deque.push(ch);
}else{
deque.pop();
}
}
String str="";
while(!deque.isEmpty()){
str=deque.pop()+str;
}
return str;
}
3.逆波兰表达式求值
3.1题目
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
-
有效的算符为
'+'、'-'、'*'和'/'。 -
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
-
两个整数之间的除法总是 向零截断 。
-
表达式中不含除零运算。
-
输入是一个根据逆波兰表示法表示的算术表达式。
-
答案及所有中间计算结果可以用 32 位 整数表示
-
示例一：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
- 示例二：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
- 示例三：
输入：tokens = ["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
3.2解法：栈
-
核心：使用栈解法
-
解析逆波兰表达式：
( 1 + 2 ) * ( 3 + 4 ) //逆波兰表达式 ( ( 1 2 + ) ( 3 4 + ) * ) -
关键：四个关键字符：+、*、-、/：若为上述这个字符，则取出栈顶的两个元素，进行运算之后再放进栈里面
-
注意：-、/两个运算的特殊性：若num1为第一个栈顶元素，num2为第二个栈顶元素
duque.push( num2-num1 ) duque.push( num2/num1 )
public int evalRPN(String[] tokens) {
Deque<Integer> deque=new LinkedList<>();
for(String s:tokens){
if(s.equals("+")){
deque.push( deque.pop()+deque.pop() );
}else if(s.equals("*")){
deque.push( deque.pop()*deque.pop() );
}else if(s.equals("-")){
int num1=deque.pop();
int num2=deque.pop();
deque.push( num2-num1 );
}else if(s.equals("/")){
int num1=deque.pop();
int num2=deque.pop();
deque.push( num2/num1);
}else{
deque.push(Integer.valueOf(s));
}
}
return deque.pop();
}
