今日总结：继续准备期末，今天的算法题目比较简单，晚上看看能不能再整理一篇前端的笔记。
Day 11
01. 有效的括号（No. 20）
题目链接
代码随想录题解
1.1 题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
1.2 笔记
还记得刚开始刷力扣的时候看到这个题一点思路没有，现在学习了栈的知识，发现这道题通过栈可以很轻松的解决。
为什么会想到用栈呢？
栈是“先进后出”的数据结构，并且可以方便的弹出，在这种验证匹配的题目非常好用，这道题先来单独看一个右括号，如果在后面立刻找到了对应的左括号那就可以直接弹出，但如果碰到的是另一个右括号，
如果存在对应的话，那这第二个右括号肯定要比第一个先找到它的左括号即先弹出。
比如：
{{}}在遍历过程中第一个{要比第二个{晚找到它对应的}
这正好符合了先进后出的特点。
所以想到了一个思路：我们将这个 String 转化为 char[] 从前向后依次遍历这个数组，如果遇到 右括号 就将其存到栈里，遇到左括号我们就检查栈中的 栈顶元素 是否和这个括号匹配，按照上面的规律，栈顶元素一定是 最先 找到对应的左括号的。
由此引出了三个错误的情况：
- 我们遍历到左括号的时候发现栈中没有元素，即左括号多出来了。
- 发现栈顶元素和左括号中的元素不对应
- 遍历完成栈中仍有元素，右括号多出来了
只要在循环中去处理这几个问题，这道题就解决了。
1.3 代码
class Solution {
Stack<Character> s = new Stack<>(); // 存放左括号的栈
HashMap<Character, Integer> left = new HashMap<>(); // 左括号
HashMap<Character, Integer> right = new HashMap<>(); // 右括号
public boolean isValid(String s) {
// 初始化 Map，key 为括号，value 为给它的分组
left.put('(', 1);
left.put('{', 2);
left.put('[', 3);
right.put(')', 1);
right.put('}', 2);
right.put(']', 3);
char[] charArray = s.toCharArray();
return check(charArray);
}
public boolean check(char[] charArray) {
for (char c : charArray) {
if (left.containsKey(c)) {
// 右括号直接放入栈中
s.push(c);
} else {
Integer key = right.get(c); // 得到它的组号
// 错误情况二：左括号多了
if (s.empty()) {
return false;
}
// 错误情况一：左右不匹配
if (!left.get(s.pop()).equals(key)) {
return false;
}
}
}
// 错误情况三：右括号多了
if (!s.empty()) {
return false;
}
return true;
}
}
02. 删除字符串中所有相邻的重复项
题目链接
代码随想录题解
2.1 题目
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入：“abbaca”
输出：“ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
提示：
1 <= S.length <= 20000S仅由小写英文字母组成。
2.2 笔记
在刷章节性的题目的时候，最重要的是总结什么时候要使用这种方法求解，因为我们已经知道这道题一定可以用这类方法作答。
栈的题目我们要检查求解的内容是否可以通过先进后出的特质来求解，这道题和上面那题一样是找对应，我们仍然可以得到：
先入栈的肯定比后入栈的后找到对应
接下来就是处理删除的情况了，我首先想到的是和上一道题那样把 遍历过 的存到栈中，遇到相邻的就删除，但删除字符串的时间复杂度很高，而且比较难以操作。
所以换一个想法，可以用栈来存储最终的结果，我们遍历字符串的时候依次将元素存入栈中，如果遇到了相同的元素代表可以删除，就将这个元素弹出，完成遍历后栈中存储的就是需要的结果字符串：
但注意栈的弹出顺序和输入顺序相反，我们最后要处理这个顺序问题。
2.3 代码
class Solution {
// 初始化使用的队列
Stack<Character> stack = new Stack<>();
public String removeDuplicates(String s) {
char[] charArray = s.toCharArray();
for (char c : charArray) {
if (stack.isEmpty()) {
// 为空则直接放入
stack.push(c);
} else {
if (stack.peek() == c) {
// 如果相同则弹出栈内的元素再进行下一个循环
stack.pop();
} else {
stack.push(c);
}
}
}
char[] res = new char[stack.size()];
int length = stack.size() - 1;
// 倒序填充结果数组，处理逆序情况
while (!stack.empty()) {
res[length] = stack.pop();
length--;
}
return String.valueOf(res);
}
}
03. 逆波兰表达式（No. 150）
题目链接
代码随想录题解
3.1 题目
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,“13”,“5”,“/”,“+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：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
提示：
1 <= tokens.length <= 104tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
3.2 笔记
这道题相信曾经做过用栈实现计算器的朋友肯定不陌生，这道题相当于用栈实现计算器的简化版本，因为不用考虑运算符的优先级，逆波兰表达式的顺序就代表了计算的次序。
如何通过栈来实现计算呢？
将数字一个一个压入栈，当遇到运算符的时候从栈中弹出数字，计算完成后再压入栈，代替原本的两个数字去参与运算，之后再去寻找下一个运算符。
因为传入的是字符串，所以我们要考虑如何判断是数字还是运算符，判断是否是数字要分为三种情况：
- 仅有一位的数字
- 多位的数字
- 负数
仅有一位的数字可以通过 s.charAt(0) 来判断是否属于0 - 9 负数和多位的数字 s.charAt(1) 来判断
3.3 代码
class Solution {
Stack<Integer> stack = new Stack<>();
ArrayList<String> num = new ArrayList<>();
public int evalRPN(String[] tokens) {
// 用来判断是否为数字
num.add("0");
num.add("1");
num.add("2");
num.add("3");
num.add("4");
num.add("5");
num.add("6");
num.add("7");
num.add("8");
num.add("9");
return doCount(tokens);
}
public int doCount(String[] tokens) {
for (String s : tokens) {
if (isNum(s)) {
stack.push(Integer.valueOf(s));
} else {
Integer b = stack.pop();
Integer a = stack.pop();
stack.add(doOperator(a, b, s));
}
}
return stack.pop();
}
public int doOperator(Integer a, Integer b, String operator) {
// 对取出来的内容进行计算
return switch (operator) {
case "+" -> a + b;
case "-" -> a - b;
case "*" -> a * b;
default -> a / b;
};
}
// 判断是否是数字
public boolean isNum(String s) {
if (s.length() == 1) {
return num.contains(String.valueOf(s.charAt(0)));
} else if (s.length() >= 2) {
return num.contains(String.valueOf(s.charAt(0))) ||
num.contains(String.valueOf(s.charAt(1)));
} else {
return false;
}
}
}
