文章目录
- 删除字符串中的所有相邻重复项
- 题目描述：
- 代码实现：
- 代码解析：
- 比较含退格的字符串
- 题目描述：
- 代码实现：
- 代码解析：
- [基本计算器 II](https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/)
- 题目描述：
- 代码实现：
- 代码解析：
- 字符串解码
- 题目描述：
- 代码实现：
- 代码解析：
- 验证栈序列
- 题目描述：
- 代码实现：
- 代码解析：
删除字符串中的所有相邻重复项
题目描述：
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
代码实现：
class Solution
{
public:string removeDuplicates(string s) {string st;for(auto& x : s){if(st.size() && st.back() == x) st.pop_back();else st.push_back(x);}return st;}
};
代码解析：
这道题就是一道消消乐，当两个相邻一样得字符一样，那就直接消除掉，所以我们可以结合之前刷过的题来看，我们可以运用“栈”这个数据结构，来帮助我们完成消消乐。
但是栈这个数据结构还是太大了，所以对于都是小写字母得这道题来说，我们直接使用字符串来模拟就好了。
所以我们直接遍历整个字符串，如果该元素与栈顶元素一致，那就直接删掉栈顶元素。
否则直接加进到栈里即可。
比较含退格的字符串
题目描述：
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
**注意：**如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。
示例 2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。
示例 3：
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。
代码实现：
class Solution
{
public:bool backspaceCompare(string s, string t) {string st1, st2;for(auto& ch : s){if(st1.size() && ch == '#') st1.pop_back();else if(ch != '#') st1 += ch;}for(auto& ch : t){if(st2.size() && ch == '#') st2.pop_back();else if(ch != '#') st2 += ch;}return st1 == st2;}
};
代码解析：
题目意思和上面那道题差不多， 本质还是个小的消消乐，在这里我就不过多赘述了。
基本计算器 II
题目描述：
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
代码实现：
class Solution
{
public:int calculate(string s) {vector<int> st;char op = '+';for(int i = 0; i < s.size(); ){if(s[i] == ' ') ++i;else if(s[i] >= '0' && s[i] <= '9'){int tmp = 0;while(i < s.size() && s[i] >= '0' && s[i] <= '9')tmp = tmp * 10 + (s[i++] - '0');if(op == '+') st.push_back(tmp);else if(op == '-') st.push_back(-tmp);else if(op == '*') st.back() *= tmp;else if(op == '/') st.back() /= tmp;}else{op = s[i];++i;}}int ans = 0;for(auto& x : st) ans += x;return ans;}
};
代码解析：
题目描述是让我们实现一个计算器，只是一个小型得计算器因为只涉及加减乘除。
那么针对这道题来说，我得建议是将所有数字丢到栈里面，
1、如果数字前面得运算符是‘+’那就直接丢到栈里面。
2、如果数字前面的运算符是‘-’那就取相反数丢到栈里面。
3、如果数字前面的运算符是‘*’那就将栈顶元素乘等当前数字。
4、如果数字前面的运算符是‘/’那就将栈顶元素除等当前数字。
还要一种细节问题，我们的数字在字符串中会有连续的数字，那么这种情况我们也要考虑进去。
具体的做法就是，不断的往该数字后面走，走一次乘等10再加上自己，直到走到了一个运算符或者越界之后即可。
同理，在我们查找到元素为数字之后，我们最后的 i 就会在内部被我们移动到运算符上或者越界。
字符串解码
题目描述：
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
代码实现：
class Solution
{
public:string decodeString(string s) {stack<string> st_s;stack<int> st_i;st_s.push("");for(int i = 0; i < s.size();){if(s[i] >= '0' && s[i] <= '9'){int tmp = 0;while(i < s.size() && s[i] >= '0' && s[i] <= '9')tmp = tmp * 10 + (s[i++] - '0');st_i.push(tmp); }else if(s[i] == '['){++i;string tmp = ""; // 一定要在这里创建空数组！while(i < s.size() && s[i] >= 'a' && s[i] <= 'z')tmp += s[i++];st_s.push(tmp);}else if(s[i] == ']'){string tmp = st_s.top();int k = st_i.top();st_i.pop();st_s.pop();while(k--)st_s.top() += tmp;++i;}else if(s[i] >= 'a' && s[i] <= 'z'){st_s.top() += s[i++];}}return st_s.top();}
};
代码解析：
题目描述也是非常的简单啊，但是这个代码有点不好写，其实本质这些栈的题目都是围绕着模拟来展开的。现在就是你给我个2[ac]，我就要给你变成acac。这就是题目的基本意思，但是会有一种情况，题目会给你这样的例子：2[ab2[2[cc]]最后转换就是abccccccccabcccccccc，所以他是会出嵌套的情况，而针对数字，也会有两位数以上的数字，那这里我们还要进行处理。
1、如果遍历到数字，按上题的方式找到两位数及以上入st_i栈。
2、如果遍历到字母，按上题的方式找到一个整个字符串，加在st_s栈顶元素字符串后。
3、如果遍历到’[‘，先++i，最重要的是要先创建一个空字符串tmp，然后凭借记录在tmp里，最后将后面的字符串找到，丢到st_s栈里。
4、如果遍历到’]'，取出st_i栈顶元素，和st_s栈顶元素，分别以k和tmp记录下来，然后丢掉st_s栈顶元素，之后循环k次，给新的st_s栈顶元素 += tmp。
验证栈序列
题目描述：
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
代码实现：
class Solution
{
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i = 0;for(auto& x : pushed){st.push(x);while(st.size() && popped[i] == st.top()){st.pop();++i;}}return i == popped.size();}
};
代码解析：
题目描述我们也好理解，如果有尝试考研的同学肯定有做过这道题，简单来说，拿示例1来看，我们有一个栈，我可以先push1 2 3 4，然后把4给推出去，这样栈剩下就只有1 2 3，接下来想要推5出去，但我没有，所以我就加到5，加到了然后推出去。后面栈仍然是1 2 3，然后想要推出去的就是3 2 1，所以最终栈就是空的了。
