20. 有效的括号
题目链接：20. 有效的括号
文档讲解：代码随想录
状态：so easy
思路： 使用栈，如果是左括号就入栈，如果是右括号则判断是否和栈顶括号匹配，如果匹配就出栈，否则判断遍历完字符串后栈中是否还有残留。
题解：
public boolean isValid(String s) {
if (s.length() % 2 != 0)
return false;
char[] chars = s.toCharArray();
Deque<Character> stack = new ArrayDeque<>();
for (char c : chars) {
// 如果当前字符是开放括号，将其压入栈中
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
}
// 如果当前字符是闭合括号，并且栈不为空且栈顶元素与当前闭合括号匹配
// 则弹出栈顶元素，表示括号匹配成功
else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.poll();
} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.poll();
} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.poll();
} else {
return false;
}
}
return stack.isEmpty();
}
1047. 删除字符串中的所有相邻重复项
题目链接：1047. 删除字符串中的所有相邻重复项
文档讲解：代码随想录
状态：还行
思路： 使用栈，栈顶元素如果和即将入栈元素相同就出栈。
普通栈解法：
public String removeDuplicates2(String s) {
char[] chars = s.toCharArray();
Deque<Character> stack = new ArrayDeque<>();
for (char c : chars) {
Character peek = stack.peek();
if (peek != null && peek == c) {
stack.poll();
} else {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.poll());
}
return sb.toString();
}
数组模拟栈 ：
public String removeDuplicates(String s) {
// 将输入字符串转换为字符数组
char[] cs = s.toCharArray();
// 用于模拟栈的数组
char[] stack = new char[s.length()];
// 栈顶指针
int top = -1;
// 遍历输入字符串的每个字符
for (char c : cs) {
if (top >= 0 && stack[top] == c) {
// 如果栈不为空且栈顶元素与当前字符相同，弹出栈顶元素
top--;
} else {
// 否则，将当前字符压入栈
stack[++top] = c;
}
}
// 将栈中的字符组成字符串
return new String(stack, 0, top + 1);
}
双指针： 本质上和数组模拟栈的逻辑是一样的
public String removeDuplicates(String s) {
char[] ch = s.toCharArray();
int fast = 0;
int slow = 0;
while(fast < s.length()){
// 直接用fast指针覆盖slow指针的值
ch[slow] = ch[fast];
// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
if(slow > 0 && ch[slow] == ch[slow - 1]){
slow--;
}else{
slow++;
}
fast++;
}
return new String(ch,0,slow);
}
150. 逆波兰表达式求值
题目链接：150. 逆波兰表达式求值
文档讲解：代码随想录
状态：还可以
思路： 逆波兰表达式一般使用栈，遇到运算符就将运算符前两个数拿出来做对应计算然后再入栈。
自带栈解法：
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
if (!token.equals("+") && !token.equals("-") && !token.equals("*") && !token.equals("/")) {
stack.push(Integer.valueOf(token));
} else {
int second = stack.pop(); // 出栈两个操作数
int first = stack.pop();
switch (token) {
case "+":
stack.push(first + second); // 将计算结果入栈
break;
case "-":
stack.push(first - second);
break;
case "*":
stack.push(first * second);
break;
case "/":
stack.push(first / second);
break;
}
}
}
return stack.pop();
}
数组模拟栈：
class Solution {
public int evalRPN(String[] tokens) {
int[] stack = new int[tokens.length];
int top = -1; // 栈顶指针，初始化为-1表示空栈
for (String token : tokens) {
if ("+-*/".contains(token)) {
int b = stack[top--]; // 出栈两个操作数
int a = stack[top--];
stack[++top] = calculate(a, b, token); // 将计算结果入栈
} else {
stack[++top] = Integer.parseInt(token); // 将操作数入栈
}
}
return stack[top]; // 返回栈顶元素即为最终结果
}
private int calculate(int a, int b, String operator) {
switch (operator) {
case "+":
return a + b;
case "-":
return a - b;
case "*":
return a * b;
case "/":
return a / b;
default:
throw new IllegalArgumentException("Invalid operator: " + operator);
}
}
}
数组模拟栈的总结：
关键点在于：
- 定义目标类型的数组作为模拟栈；
- 初始化top为-1（表示一个空栈）
- 遍历元素：
- 如果条件满足则出栈，top–
- 如果不满足则入栈，++top
