当前位置：首页 > news >正文

算法分析 —— 《栈》

news 来源：原创 2025/9/11 1:21:54

文章目录

删除字符串中的所有相邻重复项
- 题目描述：
- 代码实现：
- 代码解析：
比较含退格的字符串
- 题目描述：
- 代码实现：
- 代码解析：
[基本计算器 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;}
};

代码解析：

这道题就是一道消消乐，当两个相邻一样得字符一样，那就直接消除掉，所以我们可以结合之前刷过的题来看，我们可以运用“栈”这个数据结构，来帮助我们完成消消乐。

但是栈这个数据结构还是太大了，所以对于都是小写字母得这道题来说，我们直接使用字符串来模拟就好了。

所以我们直接遍历整个字符串，如果该元素与栈顶元素一致，那就直接删掉栈顶元素。

否则直接加进到栈里即可。

基本计算器 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，所以最终栈就是空的了。

文章目录

题目描述：

代码实现：

代码解析：

题目描述：

代码实现：

代码解析：

题目描述：

代码实现：

代码解析：

题目描述：

代码实现：

代码解析：

题目描述：

代码实现：

代码解析：

相关文章：