20 有效括号
https://leetcode.com/problems/valid-parentheses/description/
经典栈问题，把左括号转化后填进栈中
如果不是左括号，看栈为空不为空，栈是空的或栈顶不是对应的右括号 false
都不是就推出栈顶，最后看栈为不为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution{
public boolean isValid(String s){
Stack<Character> checkP = new Stack<>();
for (int i = 0; i < s.length(); i++){
char stream = s.charAt(i);
if (stream == '('){
checkP.push(')');
} else if (stream == '{'){
checkP.push('}');
} else if (stream == '['){
checkP.push(']');
} else if (checkP.isEmpty() || checkP.peek() != stream){
return false;
} else {
checkP.pop();
}
}
return checkP.isEmpty();
}
}
|
1047 删除字符串中的所有相邻重复项
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/submissions/1137766541/
栈的另一经典问题
查看字符串中的栈顶元素，如果为空或者不是当前stream元素，push进去
是当前stream元素，把栈顶pop出来
因为当前栈是倒序所以把顺序反过来打印
第一种 用栈解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution{
public String removeDuplicates(String s){
Deque<Character> result = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++){
char stream = s.charAt(i);
if (result.isEmpty() || result.peek() != stream){
result.push(stream);
} else {
result.pop();
}
}
String str = "";
while (!result.isEmpty()){
str = result.pop() + str;
}
return str;
}
}
|
第二种用字符串直接作为栈
利用StringBuilder 检查stream里面的值，原理和栈相同，不用倒序插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution{
public String removeDuplicates(String s){
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++){
if (sb.length() == 0 || sb.charAt(sb.length() - 1) != s.charAt(i)){
sb.append(s.charAt(i));
} else {
sb.deleteCharAt(sb.length() - 1);
}
}
return sb.toString();
}
}
|
第三种 双指针
把快指针的值覆盖到慢指针处
比较慢指针位置和慢指针前一位置，相同慢指针减一，不同慢指针加一
快指针一直遍历整个数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution{
public String removeDuplicates(String s){
int left = 0;
int right = 0;
char[] result = s.toCharArray();
while (right < s.length()){
result[left] = result[right];
if (left > 0 && result[left] == result[left - 1]){
left--;
} else {
left++;
}
right++;
}
return new String(result, 0, left);
}
}
|
150 逆波兰表达式求值
逆波兰表达式是一种后缀表达式，所谓后缀是指运算符写在后面
用栈来实现，读到’+’, ‘-‘ , ‘*’ , ‘/‘ 后推出栈顶两个元素进行运算，之后把结果推回栈顶
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution{
public int evalRPN(String[] tokens){
Deque<Integer> result = new ArrayDeque<>();
for (String i : tokens){
if (i.equals("+")){
result.push(result.pop() + result.pop());
} else if (i.equals("-")){
result.push(-result.pop() + result.pop());
} else if (i.equals("*")){
result.push(result.pop() * result.pop());
} else if (i.equals("/")){
int divisor = result.pop();
int dividend = result.pop();
result.push(dividend / divisor);
} else {
result.push(Integer.valueOf(i));
}
}
return result.pop();
}
}
|