目录
①力扣1047. 删除字符串中的所有相邻重复项
难度 简单
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
1 <= S.length <= 20000S仅由小写英文字母组成。
class Solution {
public:
string removeDuplicates(string s) {
}
};解析代码
本题很像 消消乐游戏，仔细观察消除过程，可以发现本题与之前做过的括号匹配问题是类似的。当前元素是否被消除，需要知道上一个元素的信息，因此可以用栈来保存信息。 但是如果使用 stack 容器来保存的话，最后还需要把结果从栈中取出来。不如直接用字符数组模拟一个栈结构：在数组的尾部尾插尾删，实现栈的进栈和出栈。最后数组存留的内容， 就是最后的结果。
class Solution {
public:
string removeDuplicates(string s) {
string stack = "";
for(auto& e : s)
{
if(stack.size() == 0 || stack.back() != e)
stack += e;
else
stack.pop_back();
}
return stack;
}
};②力扣844. 比较含退格的字符串
难度 简单
给定 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"。
提示：
1 <= s.length, t.length <= 200s和t只含有小写字母以及字符'#'
进阶：
- 你可以用
O(n)的时间复杂度和O(1)的空间复杂度解决该问题吗？
class Solution {
public:
bool backspaceCompare(string s, string t) {
}
};解析代码
和力扣1047. 删除字符串中的所有相邻重复项类似，由于退格的时候需要知道前面元素的信息，而且退格也符合后进先出的特性。因此我们可以使用栈结构来模拟退格的过程。
- 当遇到非 # 字符的时候，直接进栈。
- 当遇到 # 的时候，栈顶元素出栈。
为了方便统计结果，用字符数组string来模拟实现栈结构。
class Solution {
public:
bool backspaceCompare(string s, string t) {
string stack1 = "", stack2 = "";
for(auto& e : s)
{
if(e != '#')
stack1 += e;
else if(stack1.size())
stack1.pop_back();
}
for(auto& e : t)
{
if(e != '#')
stack2 += e;
else if(stack2.size())
stack2.pop_back();
}
return stack1 == stack2;
}
};③力扣227. 基本计算器 II
难度 中等
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2" 输出：7
示例 2：
输入：s = " 3/2 " 输出：1
示例 3：
输入：s = " 3+5 / 2 " 输出：5
提示：
1 <= s.length <= 3 * 10^5s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开s表示一个 有效表达式- 表达式中的所有整数都是非负整数，且在范围
[0, 2^31 - 1]内 - 题目数据保证答案是一个 32-bit 整数
class Solution {
public:
int calculate(string s) {
}
};解析代码
注意到这道题只有加减乘除四个运算，没有括号，并且每一个数都是大于等于 0 的， 这样可以大大地减少需要处理的情况。
由于表达式里面没有括号，因此只用处理加减乘除混合运算即可，这样不需要用到双栈。根据四则运算的顺序，我们可以先计算乘除法，然后再计算加减法。由此可以得出下面的结论：
- 当一个数前面是 '+' 号的时候，这⼀个数是否会被立即计算是不确定的，因此可以先入栈。
- 当一个数前面是 '-' 号的时候，这⼀个数是否被立即计算也是不确定的，但是这个数已经和前面的负号绑定了，因此可以将这个数的相反数入栈。
- 当一个数前面是 '*' 号的时候，这⼀个数可以立即与前面的⼀个数相乘，此时让将栈顶的元素乘上这个数；
- 当一个数前面是 '/' 号的时候，这⼀个数也是可以立即被计算的，因此让栈顶元素除以这个数。
当遍历完全部的表达式的时候，栈中剩余的元素之和就是最终结果，这里用数组模拟栈：
class Solution {
public:
int calculate(string s) {
int n = s.size(), i = 0;
vector<int> stack(n);
char op = '+';
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'); // 提取数字
}
if(op == '+')
stack.push_back(tmp);
else if(op == '-')
stack.push_back(-tmp);
else if(op == '*')
stack.back() *= tmp;
else // (op == '/')
stack.back() /= tmp;
}
else
op = s[i++];
}
int sum = 0;
for(auto& e : stack)
{
sum += e;
}
return sum;
}
};④力扣394. 字符串解码
难度 中等
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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"
提示：
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
class Solution {
public:
string decodeString(string s) {
}
};解析代码
两个栈解法思路： 对于 3[ab2[cd]] ，我先解码内部的，再解码外部（为了方便区分，使用了空格）： 3[ab2[cd]] -> 3[abcd cd] -> abcdcd abcdcd abcdcd 在解码 cd 的时候，需要保存 3 ab 2 这些元素的信息，并且这些信息使用的顺序是从后往前，正好符合栈的结构。
因此可以定义两个栈结构，一个用来保存解码前的重复次数 k （左括号前的数字），一个用来保存解码之前字符串的信息（左括号前的字符串信息）。
class Solution {
public:
string decodeString(string s) {
stack<int> st1;
stack<string> st2;
st2.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');
st1.push(tmp);
}
else if(s[i] >= 'a' && s[i] <= 'z')
{
string tmp = "";
while(i < n && s[i] >= 'a' && s[i] <= 'z')
tmp += s[i++];
st2.top() += tmp;
}
else if(s[i] == '[')
{
++i;
string tmp = "";
while(s[i] >= 'a' && s[i] <= 'z')
tmp += s[i++];
st2.push(tmp);
}
else // if(s[i] == ']')
{
string tmp = "";
for(int j = 0; j < st1.top(); ++j)
tmp += st2.top();
st2.pop();
st2.top() += tmp;
st1.pop();
++i;
}
}
return st2.top();
}
};⑤力扣946. 验证栈序列
难度 中等
给定 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 之前弹出。
提示：
1 <= pushed.length <= 10000 <= pushed[i] <= 1000pushed的所有元素 互不相同popped.length == pushed.lengthpopped是pushed的一个排列
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
}
};解析代码
思路就是用栈来模拟进出栈的流程。 一直让元素进栈，进栈的同时判断是否需要出栈。当所有元素模拟完毕之后，如果栈中还有元素，那么就是一个非法的序列。否则就是一个合法的序列。
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
if(pushed.size() != popped.size())
return false;
stack<int> st;
int i = 0;
for(auto& e : pushed)
{
st.push(e); // 不匹配就持续入，匹配就持续出
while(!st.empty() && st.top() == popped[i])
{
st.pop();
++i;
}
}
// return i == popped.size();
return st.empty();
}
};本篇完。
下一篇动态规划类型的是子序列dp类型的OJ。
下下篇是队列_宽搜bfs类型的OJ。
