20.有效的括号
文章：4. 有效的括号
题目：20. 有效的括号
视频：栈的拿手好戏！| LeetCode：20. 有效的括号_哔哩哔哩_bilibili
用栈来解决的经典问题。
不匹配的场景有三种：
数量、类型、顺序
剪枝：如果字符串为奇数，则一定有不匹配的括号，直接返回多余即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean isValid(String s) {
if(s.length()%2 ==1 )return false;
Stack<Character> stack = new Stack<>();
for(int i = 0 ; i < s.length();i++){
if(s.charAt(i) == '(')stack.push(')');
else if(s.charAt(i) == '{')stack.push('}');
else if(s.charAt(i) == '[')stack.push(']');
else if(stack.isEmpty() || s.charAt(i) != stack.peek())return false;
else stack.pop();
}
return stack.isEmpty();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func isValid(s string) bool {
hash := map[byte]byte{')':'(','}':'{',']':'['}
stack := make([]byte,0)
if s ==""{
return false
}
for i :=0 ;i<len(s);i++{
if(s[i] =='(' || s[i]=='{' || s[i] == '['){
stack = append(stack,s[i])
}else if len(stack) > 0 && stack[len(stack)-1] == hash[s[i]]{
stack = stack[:len(stack)-1]
}else {
return false
}
}
return len(stack) ==0
}
|
1047.删除字符串中的所有相邻重复项
文章：5. 删除字符串中的所有相邻重复项
题目：1047. 删除字符串中的所有相邻重复项
视频：栈的好戏还要继续！| LeetCode：1047. 删除字符串中的所有相邻重复项_哔哩哔哩_bilibili
【思路】
相近字母重复的消除，需要模拟栈的输入输出 -> 使用字符串模拟栈
使用栈来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String removeDuplicates(String s) {
Stack<Character> stack = new Stack<>();
for (int i =0;i<s.length();i++){
char c = s.charAt(i);
if(stack.isEmpty() || stack.peek()!= c){
stack.push(c);
}else{
stack.pop();
}
}
String str ="";
while(!stack.isEmpty()){
str = stack.pop()+str;
}
return str;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func removeDuplicates(s string) string {
var b []byte
top:=0
for i:=0;i<len(s);i++{
if len(b) == 0 || b[len(b)-1]!= s[i]{
b = append(b,s[i])
top++
}else{
b=b[:len(b)-1]
top--
}
}
return string(b)
}
|
150.逆波兰表达式求值
文章：6. 逆波兰表达式求值
题目：150. 逆波兰表达式求值
视频：栈的最后表演！ | LeetCode：150. 逆波兰表达式求值_哔哩哔哩_bilibili
【思路】
逆波兰表达式 == 后缀表达式 左右中
也就是用栈来解决这个问题。
易错点：使用equals函数比较字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<>();
for(String s : tokens){
if("+".equals(s)){
stack.push(stack.pop()+stack.pop());
}else if("-".equals(s)){
stack.push(-stack.pop()+stack.pop());
}else if("*".equals(s)){
stack.push(stack.pop()*stack.pop());
}else if("/".equals(s)){
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2/temp1);
}else{
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
|
学习到了将字符串类型转换为Int类型： Strconv.Atoi()
如果能够转换为整型则为数字，转换失败则为四则运算符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func evalRPN(tokens []string) int {
stack := []int{}
for _,s := range tokens{
val,err := strconv.Atoi(s)
if err ==nil{
stack = append(stack,val)
}else{
num1,num2 := stack[len(stack)-2],stack[len(stack)-1]
stack = stack[:len(stack)-2]
switch s{
case"+":
stack = append(stack,num1+num2)
case"-":
stack = append(stack,num1-num2)
case"*":
stack = append(stack,num1*num2)
case"/" :
stack = append(stack,num1/num2)
}
}
}
return stack[0]
}
|
【算法总结】
今天学习了三种常见的栈的用法：辨别括号、删除重复项（类似连连看）、逆波兰表达式（后缀表达式）
- 辨别括号是否有效：使用栈来判断，需要考虑三种无效的情况{数量、类型、顺序}
- 删除所有相邻的重复项：使用字符串来模拟栈（Java使用StringBuffer、Go使用切片）
- 逆波兰表达式：使用栈来解决该问题
【语法总结】
使用equals函数比较字符串
需要改动字符串的话使用StringBuilder或StringBuffer更合适
需要分清楚什么时候对切片进行初始化
学习到了将字符串类型转换为Int类型： Strconv.Atoi()
