删除字符串中所有相邻重复项
题解
1. 用字符串模拟栈的行为，字符串的尾部插入和删除，并且这样得到的答案是不需要逆置的
代码
class Solution
{
public:
string removeDuplicates(string s)
{
string st;
for(auto ch : s)
{
if(st.size() && ch == st.back())
{
st.pop_back();
}
else st.push_back(ch);
// 栈为空或者栈顶和数组中的元素不同的情况
}
return st;
}
};
比较含退格的字符串
题解
1. 用字符串模拟栈的行为，和上一题基本上是一样的套路
代码
class Solution
{
public:
bool backspaceCompare(string s, string t)
{
return cmpstring(s) == cmpstring(t);
}
string cmpstring(string s)
{
string st;
for(auto ch : s)
{
if(ch != '#') st += ch;
else
{
// 处理字符串中只有#的情况
if(st.size()) st.pop_back();
}
}
return st;
}
};
基本计算器II
题解
这题可以使用一个数组模拟栈和一个变量存储运算符
1. 遇到空格直接跳过
2. 遇到数字，第一个数之前的运算符肯定是’+‘，因为题目说明了是非负整数，如果一个数字之前的符号是’+‘或者是’-'就直接加入到栈中，如果是乘号或者是除号就取出栈顶的元素和下一个数进行计算，计算完后再把这个数字加入到栈中，最后栈里面的元素相加就是最终答案
3. 遇到是运算符，就更新运算符，并且移动到下一个位置
代码
class Solution
{
public:
int calculate(string s)
{
// 空格的情况如何处理 -> i++
// 表达式的基本上都会使用栈处理
vector<int> st;
char op = '+';
int i = 0;
int n = s.size();
while(i < n)
{
if(s[i] == ' ') i++;
else if(s[i] >= '0' && s[i] <= '9')
{
int tmp = 0;
while(i < n && (s[i] >= '0'&& s[i] <= '9'))
tmp = tmp * 10 + (s[i++] - '0');
// tmp可能是一个多位数
if(op == '+') st.push_back(tmp);
else if(op == '-') st.push_back(-tmp);
else if(op == '*') st.back() *= tmp;
else st.back() /= tmp;
// 栈顶元素和下一个数相除,并且除完之后就等于重新加入栈顶了
}
else
{
op = s[i];
i++;
}
}
int ret = 0;
for(auto x : st) ret += x;
return ret;
}
};
字符串解码
题解
分情况讨论
1. 先放入一个空串，防止出现取栈顶元素取不到的情况
2. 遇到左括号，把字符串提取出来，放入栈中，而不是放入栈顶元素的后面，因为前面可能还有数字要加倍这个字符串
3. 遇到右括号，把字符串的栈顶元素和数字栈的栈顶元素提取出来，进行加倍，这就是最近的匹配
4. 遇到普通的前面不带数字的字符串，直接提取出来，放入字符串栈顶元素的后面
代码
class Solution
{
public:
string decodeString(string s)
{
stack<string> st;
stack<int> ret;
st.push("");
int i = 0;
int n = s.size();
while(i < n)
{
if(s[i] >= '0' && s[i] <= '9')
{
int tmp = 0;
while(i < n && (s[i] >= '0' && s[i] <= '9'))
{
tmp = tmp * 10 + (s[i++] - '0');
}
ret.push(tmp);
}
else if(s[i] == '[')
{
i++;
string p = "";
while(i < n && s[i] >= 'a' && s[i] <= 'z')
{
p += s[i++];
}
st.push(p);
}
else if(s[i] == ']')
{
int k = ret.top();
ret.pop();
string tmp = st.top();
st.pop();
while(k--)
{
st.top() += tmp;
}
// 怎么把栈顶的字符串提取出来
// st.top()
i++;
}
else
{
string q;
while(i < n && s[i] >= 'a' && s[i] <= 'z')
{
q += s[i++];
}
st.top() += q;
}
}
return st.top();
}
};
验证栈序列
题解
1. 保证让数据一直进栈
2. 并且在进栈的同时，判断是否出栈
3. 所有元素进栈完毕之后，如果popped的i == n说明栈合法，否则不合法，或者是栈为空，也是合法的，否则是不合法的
代码
class Solution
{
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
{
stack<int> st;
int n = pushed.size();
int i = 0;
int j = 0;
while(i < n)
{
st.push(pushed[i++]);
while(!st.empty() && st.top() == popped[j])
{
st.pop();
j++;
}
}
return st.empty() ? true : false;
}
};
总结
什么时候可以使用栈？
1. 字符串表达式求值，括号匹配，删除相同的相邻元素，最近保存的先出去，都应该用栈来解决
2. 需要处理最近或最后出现的数据
3. 在DFS中，栈用于存储待访问的节点
4. 检查字符串是否为回文
5. 撤销操作: 需要支持回退功能
怎么使用栈解决问题？
1. 模拟
2. 用字符串或者数组模拟栈，st.back()，st.pop_back()，st.push_back()
3. 分情况讨论
提取字符串中长数字字符转为整形的方法
int tmp = 0
int tmp = tmp * 10 + (s[i] - ‘0’)
s[i] - ‘0’ 防止溢出，tmp * 10 + s[i] 可能是超大的