算法分析——《栈》

文章目录 删除字符串中的所有相邻重复项题目描述：代码实现：代码解析： 比较含退格的字符串题目描述：代码实现：代码解析： [基本计算器 II]( leetcode /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，所以最终栈就是空的了。