【刷题18】栈专题
一、删除字符串中的所有相邻重复项
题目：
思路：栈
- 当栈为空，就进栈；或者遍历到的该元素与栈顶元素不同，进栈
- 栈不为空且遍历到的该元素与栈顶元素相同，删除栈顶元素
- 给返回值，逆置，返回
代码：
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
string ret;
for(auto &e : s)
{
if(st.empty() || st.top() != e)
st.push(e);
else
st.pop();
}
while(!st.empty())
{
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
二、比较含退格的字符串
题目：
思路：栈
- 与上题的思路差不多，注意的是，栈为空时，入栈的数据不能是 ‘#’
- 最后比较字符串即可
代码：
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<char> st1, st2;
string str1, str2;
for(auto &e : s)
{
if(st1.empty() || e != '#')
{
if(e != '#') st1.push(e);
}
else
st1.pop();
}
while(!st1.empty())
{
str1 += st1.top();
st1.pop();
}
//
for(auto &e : t)
{
if(st2.empty() || e != '#')
{
if(e != '#') st2.push(e);
}
else
st2.pop();
}
while(!st2.empty())
{
str2 += st2.top();
st2.pop();
}
//
if(str1.size() != str2.size()) return false;//
for(int i=0; i<str1.size(); i++)
{
if(str1[i] != str2[i]) return false;
}
return true;
}
};
三、基本计算器ll
题目：
思路：栈-模拟
- 用一个栈，定义变量tmp初始化为0，ch初始化为加号，因为刚开始遇到的数字都是正数
- 遍历字符串，是空格，continue
- 是操作符，ch更新为当前操作符，tmp刷新为0
- 是操作数，先提取tmp。tmp+=当前操作数，因为可能是连续的操作数，所以判断后一个是不是操作数，如果是，tmp*=10，再continue
- 保证tmp提取完，根据ch，是加号，tmp直接入栈；是减号，负tmp入栈；是乘号，栈顶元素乘tmp；是除号，栈顶元素除tmp
- 最后把栈的所有元素加起来，就是返回结果
代码：
class Solution {
public:
int calculate(string s) {
stack<int> st;
char ch = '+';
int tmp = 0;
for(int i=0; i<s.size(); i++)
{
if(s[i] == ' ') continue;
if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
{
ch = s[i];
tmp = 0;
}
else
{
tmp += s[i]-'0';
if(s[i+1] >= '0' && s[i+1] <='9')
{
tmp *= 10;
continue;
}
//
if(ch == '+') st.push(tmp);
else if(ch == '-') st.push(-tmp);
else if(ch == '*') st.top() *= tmp;
else st.top() /= tmp;
}
}
int ret = 0;
while(!st.empty())
{
ret += st.top();
st.pop();
}
return ret;
}
};
四、字符串解码
题目：
思路：栈-模拟
- 两个栈，一个放字符串，另一个放数字
- 细节，字符串栈先放入一个空串，方便后面+=另一个字符串
分情况讨论：
- 遇到数字，提取该数字，放入数字栈
- 遇到 [ ，把后面的字符串提取出来，push到字符串栈
- 遇到 ] ，取字符串栈的栈顶元素tmp和取数字栈的栈顶元素k，然后原来的字符串栈的栈顶pop，新的字符串栈的top += k个tmp
- 单独字符，没有在 [ ] 里面的字符串，提取该字符串，然后字符串栈的top += 该字符串
- 最后返回字符串栈的top
代码：
class Solution {
public:
string decodeString(string s) {
stack<string> st;// 字符串栈
stack<int> nums; // 数字栈
st.push(""); // 细节处理
int i = 0, n = s.size();
while(i < n)
{
// 遇到数字，放入数字栈
if(s[i] >= '0' && s[i] <= '9')
{
int tmp = 0;
while(s[i] >= '0' && s[i] <= '9')
{
tmp = tmp*10 + (s[i]-'0');
i++;
}
nums.push(tmp);
}
// 遇到 [ ，提取后面的字符串，push
else if(s[i] == '[')
{
i++;
string tmp = "";
while(s[i] >= 'a' && s[i] <= 'z')
{
tmp += s[i];
i++;
}
st.push(tmp);
}
// 遇到 ] ，解析，放在字符串栈 栈顶的后面
else if(s[i] == ']')
{
int k = nums.top();
nums.pop();
string tmp = st.top();
st.pop();
while(k--)
{
st.top() += tmp;
}
i++;
}
// 单独字符，提取字符串，放在字符串栈 栈顶的后面
else
{
string tmp = "";
while(s[i] >= 'a' && s[i] <= 'z')
{
tmp += s[i];
i++;
}
st.top() += tmp;
}
}
return st.top();
}
};
五、验证序列栈
题目：
思路：刷题17 的 栈的压入弹出
代码：
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st;
int i = 0, j = 0;
while(i < pushed.size())
{
st.push(pushed[i++]);
while(!st.empty() && st.top() == popped[j])
{
st.pop();
j++;
}
}
return j == popped.size() ? true : false;
}
};
原文地址：https://blog.csdn.net/2301_77459845/article/details/143586415
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！