代码随想录算法训练营day11 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值
目录
- 有效的括号
- 思路
- 解题方法
- 复杂度
- Code
- 删除字符串中的所有相邻重复项
- 思路
- 解题方法
- 复杂度
- Code
- 逆波兰表达式求值
- 思路
- 解题方法
- 复杂度
- Code
- ���结
有效的括号
链接: 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
思路
括号匹配是使用栈解决的经典问题。
我们首先要弄清楚，字符串里的括号不匹配有几种情况。
-
第一种情况，字符串里左方向的括号多余，所以不匹配。
-
第二种情况，括号没有多余，但是括号的类型没有匹配上。
-
第三种情况，字符串里面右方向的括号多余了，所以不匹配。
解题方法
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
字符串遍历完之后，栈是空的，就说明全都匹配了
复杂度
时间复杂度：O(n)
空间复杂度：O(n)
Code
注：
在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多
class Solution { public: bool isValid(string s) { if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求 stack st; for (int i = 0; i还有另一种写法：
class Solution { public: bool isValid(string s) { stack left; for (char c : s) { if (c == '(' || c == '{' || c == '[') left.push(c); else // 字符 c 是右括号 if (!left.empty() && leftOf(c) == left.top()) left.pop(); else // 和最近的左括号不匹配 return false; } // 是否所有的左括号都被匹配了 return left.empty(); } char leftOf(char c) { if (c == '}') return '{'; if (c == ')') return '('; return '['; } };删除字符串中的所有相邻重复项
链接: 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入：“abbaca”
输出：“ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
思路
本题要删除相邻相同元素，相对于20. 有效的括号来说其实也是匹配问题，20. 有效的括号 是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作。
本题也是用栈来解决的经典题目。
那么栈里应该放的是什么元素呢？
我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，
那么如何记录前面遍历过的元素呢？
所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。
然后再去做对应的消除操作。
注：
因为从栈里弹出的元素是倒序的，所以要再对字符串进行反转，就能得到最终的结果。
解题方法
复杂度
- 法一
时间复杂度：O(n)
空间复杂度：O(n)
- 法二
时间复杂度：O(n)
空间复杂度：O(1)
Code
class Solution { public: string removeDuplicates(string S) { stack st; for (char s : S) { if (st.empty() || s != st.top()) { st.push(s); } else { st.pop(); // s 与 st.top()相等的情况 } } string result = ""; while (!st.empty()) { // 将栈中元素放到result字符串汇总 result += st.top(); st.pop(); } reverse (result.begin(), result.end()); // 此时字符串需要反转一下 return result; } };可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作
class Solution { public: string removeDuplicates(string S) { string result; for(char s : S) { if(result.empty() || result.back() != s) { result.push_back(s); } else { result.pop_back(); } } return result; } };逆波兰表达式求值
链接: 逆波兰表达式求值
给你一个字符串数组 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 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。
递归就是用栈来实现的。
所以栈与递归之间在某种程度上是可以转换的
解题方法
其实逆波兰表达式相当于是二叉树中的后序遍历。 大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。
但我们没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后序遍历的方式把二叉树序列化了，就可以了。
在进一步看，本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这岂不就是一个相邻字符串消除的过程，和1047.删除字符串中的所有相邻重复项很像。
复杂度
时间复杂度：O(n)
空间复杂度：O(n)
Code
class Solution { public: int evalRPN(vector& tokens) { // 力扣修改了后台测试数据，需要用longlong stack st; for (int i = 0; i总结
- 第一题写代码之前要分析好有哪几种不匹配的情况，如果不在动手之前分析好，写出的代码也会有很多问题。
- 第三题不难，但第一次做的话，会很难想到。
- 参考文档
- 链接: 有效的括号
- 链接: 删除字符串中的所有相邻重复项
- 链接: 逆波兰表达式求值
-