训练营Day11
继续学习栈和队列
# 20.有效的括号 (opens new window)
简单题,可以使用s.length()%2!=0
剪枝
class Solution {
public boolean isValid(String s) {
if (s.length()%2!=0){
return false;
}
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '['){
stack.push(s.charAt(i));
}else {
if (stack.isEmpty() || (s.charAt(i)==')' && stack.peek()!='(')
|| (s.charAt(i)=='}' && stack.peek()!='{')
|| (s.charAt(i)==']' && stack.peek()!='[')
){
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 1047.删除字符串中的所有相邻重复项 (opens new window)
使用双端队列,代替栈。然后利用栈的特性去删除重复项
class Solution {
public String removeDuplicates(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
if (stack.isEmpty() || stack.peek() != s.charAt(i)){
stack.push(s.charAt(i));
}else if (stack.peek() == s.charAt(i)){
stack.pop();
}
}
//输出
char[] chars = new char[stack.size()];
for (int i = stack.size()-1; i >=0; i--) {
chars[i] = stack.pop();
}
return new String(chars);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 150.逆波兰表达式求值 (opens new window)
也就是后缀表达式,跟下面的二叉树章节有关。好久没听过这个了,都给忘了
这道题好像上学的时候做过,算是简单的。
class Solution {
//["2","1","+","3","*"]
public int evalRPN(String[] tokens) {
Deque<String> stack1 = new ArrayDeque<>(); //临时结果栈
Set<String> set = new HashSet<>();
set.add("+");
set.add("*");
set.add("/");
set.add("-");
for (String token : tokens) {
if (set.contains(token)){
String a = stack1.pop();
String b = stack1.pop();
if (token.equals("+")){
stack1.push(String.valueOf(Integer.parseInt(b)+Integer.parseInt(a)));
}else if (token.equals("-")){
stack1.push(String.valueOf(Integer.parseInt(b)-Integer.parseInt(a)));
}else if (token.equals("/")){
stack1.push(String.valueOf(Integer.parseInt(b)/Integer.parseInt(a)));
}else if (token.equals("*")){
stack1.push(String.valueOf(Integer.parseInt(b)*Integer.parseInt(a)));
}
}else {
stack1.push(token);
}
}
return Integer.parseInt(stack1.pop());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
上次更新: 2023/07/05, 01:23:13