深度学习算法之栈
66.删除字符串中的所有相邻重复项
题目链接
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入：“abbaca” 输出：“ca” 解释： 例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
这个很像那个消消乐的游戏，我们一直在重复进行消除操作
利用栈做一下模拟就行了 直接用数组就可以模拟这个栈结构 好处就是：模拟完毕之后，数组里面存的就是最终结果
class Solution {
public:
string removeDuplicates(string s)
{
string ret;//搞一个数组模拟栈结果
for(auto ch:s)
{
//出栈
//我们栈内是需要存在数据的才能进行删除操作的
if(ret.size()&&ch==ret.back()) ret.pop_back();//如果当前的字符等于我们最后一个字符的话，那么就将这个栈顶元素删除掉
//入栈
else ret+=ch;
}
// 循环结束之后ret里面的就是最终的结果了
return ret;
}
};这段代码检查 ret 是否为空 (ret.size())，以及当前字符 ch 是否与栈顶字符（即 ret.back()）相同。如果相同，则执行 ret.pop_back()，即删除栈顶字符，相当于“出栈”操作。
67.比较含退格的字符串
题目链接
给定 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)
{
return changeStr(s)==changeStr(t);//判断这两个字符串的返回值是否相等
{
}
}
string changeStr(string& s)
{
string ret;//用数组模拟栈结构
for(char ch:s)
{
if(ch!='#')ret+=ch;//我们直接入栈就行了
else
{
if(ret.size())ret.pop_back();//如果我们的ret中是存在数据的话，那么我们就进行pop操作
}
}
return ret;
}
};68.基本计算器 II
题目链接
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意： 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入： s = “3+2x2” 输出 7
示例 2：
输入： s = " 3/2 " 输出： 1
示例 3：
输入： s = " 3+5 / 2 " 输出： 5
1 <= s.length <= 3 * 105s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开s表示一个 有效表达式- 表达式中的所有整数都是非负整数，且在范围
[0, 231 - 1]内 - 题目数据保证答案是一个 32-bit 整数
表达式求值 解法：利用栈来模拟计算过程 创建两个栈，一个栈存的是数据，一个栈存的是我们的操作符，并且里面存有一个初始化的值是’+’ 如果我们遇到的是减号的话，我们直接让下一个数字前面带上一个负号，就是相当于将这个数字减去
如果我们遇到了乘号的话，那么我们将此时栈顶的数字拿出来，和还没有入栈的那个数字进行相乘的操作然后再将结果放进去 如果是除号的话，我们大胆将前面的那个数拿过来和后面还没入栈的那个数字进行相除的操作
当我们遍历完我们需要计算的数组后，我们将栈中的数据都进行相加一次就可以得到最后的结果了
这个就是分情况讨论 当前的操作符就是tmp
- 1.遇到操作符：更新操作符
- 2.遇到数字：
- 1.先把数字提取出来
- 2.分情况讨论，根据op的符号
- 1.op== ‘+’，tmp直接入栈
- 2.op== ‘-’,-tmp入栈
- 3.op== ‘*’，直接乘到栈顶元素上
- 4.op== ‘/’,直接除到栈顶元素上
class Solution {
public:
int calculate(string s)
{
vector<int>st;//用一个数组模拟栈结构
int i=0,n=s.size();//i用来遍历，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');//当我们此时的i不越界，并且此时遍历到的是一个数字
if(op=='+')st.push_back(tmp);//如果此时的符号是加号的话，我们直接将此时栈顶的元素插入
else if(op=='-') st.push_back(-tmp);//如果是负号的话，那么我们直接插入这个数的相反数
else if(op=='*') st.back()*=tmp;//直接将栈顶的元素乘到tmp中去
else if(op=='/') st.back()/=tmp;
}
else//如果不是一个字符的话，那么我们就更新下我们的操作符
{
op=s[i];//将我们此时的操作符更新为这个遍历到的操作符
i++;
}
}
//当整个while循环结束之后，我们的st里面存的就是最后的结果了
int ret=0;
for(auto x:st)ret+=x;
return ret;
}
};分情况进行问题的讨论
69.字符串解码
题目链接 给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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”
对于我们这个的话，我们需要先将最里面的括号进行解码的操作，2[c]就是cc a2[c]就是acc 3[a2[cc]]=accaccacc
这个题我们依旧是使用栈进行问题的解决操作 我们依旧利用栈，将每个元素都遍历存档进去，当我们遇到右括号的时候，说明我们之前是存在左括号的，然后我们进行出栈的操作，直到匹配到第一个左括号
我们创建两个数组，一个数组存放string、一个数组存放int 我们如果遇到的是数字的话就放在右边的栈中，如果遇到的是字符的话就是左边的栈中，如果遇到左括号的话并且后面还是一个字符的话直接把左括号后面的那一位字符放到栈中去，如果遇到了右括号的话，我们直接将栈顶元素取出，如下，这里我们直接将bc和2取出进行解码操作，并且解析完成之后，我们并不能直接将解析结果丢到栈中去，而是放到栈顶元素的后面去
对于我们这里的话，我们又碰到了一个右括号，那么我们将两个栈顶元素都拿出来，进行解码，解码之后我们需要放到栈顶元素的后面，但是左边的栈顶里面就没有元素了，所以为了避免这种情况，我们在栈的初始化的时候在里面放一个空字符 解法：用栈来模拟
分情况讨论：
- 1.遇到数字：提取这个数字，放入到"数字栈"
- 2.遇到‘[’，：将后面的字符串提取出来，放入"字符串栈"中
- 3.遇到‘]’：直接拿出两个栈的栈顶进行解码操作，然后放到栈顶的字符串后面追加
- 4.遇到单独的字符，提取出来这个字符，直接放在字符串栈的字符串后面
class Solution
{
public:
string decodeString(string s)
{
//创建两个栈
stack<int>nums;
stack<string>st;
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')//取出当前位置的字符---这里不会假i<n的，因为数字之后是肯定存在东西的
{
tmp=tmp*10+(s[i]-'0');//如果我们这里一直是数字的话我们就乘10加上
i++;//一直加到不是数字为止
}
nums.push(tmp);//将这个数字插入到数字栈中去
}
else if(s[i]=='[')//如果遇到的是一个左括号的话，是将左括号右边的字符串提取出来
{
//我们需要将左括号右边的字符串提取出来
i++;
string tmp;
while(s[i]>='a'&&s[i]<='z')//遇到的是一个字符,这里不用加上i<n这个条件，因为遇到左括号之后肯定是有一个右括号的
{
tmp+=s[i];
i++;
}
//将这个字符丢到字符栈中去
st.push(tmp);
}
else if(s[i]==']')//遇到右括号的话我们直接进行解析的操作
{
//我们需要将两个栈的栈顶元素拿到
string tmp=st.top();
st.pop();
int k=nums.top();
nums.pop();
while(k--)//重复k次
{
st.top()+=tmp;//直接将我们的tmp追加在此时的栈顶元素的后面
}
i++;//当遇到这个右括号的时候，我们需要跳过这个右括号
}
else//遇到的是一个孤单的字符串，后面没有右括号和其他的东西了
{
//将这个字符串提取出来
string tmp;
while(i<n&&s[i]>='a'&&s[i]<='z')//遇到的是一个字符,这里要加上i<n这个条件，因为我们这里后面可能什么都没有的，避免越界情况的出现
{
tmp+=s[i];
i++;
}
st.top()+=tmp;// 将这个元素放到栈顶元素后面追加着
}
}
//当整个循环结束后，我们将栈顶元素返回就行了，因为此时栈顶存的就是最后的结果了
return st.top();
}
};70.验证栈序列
题目链接
给定 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的一个排列
给你一个进栈序列，给你一个出栈序列，判断这个栈是否合法
借助栈模拟即可 1.让元素一直进栈 2.进栈的同时判断是都出栈即可
所有元素进栈完毕之后，判断i是否已经遍历完毕，或者判断栈是否为空即可
class Solution
{
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
{
stack<int>st;
int i=0;
int n=popped.size();
for(auto x:pushed)
{
st.push(x);//一直进栈，直到满足下面的条件后进入到循环中
while(st.size()&&st.top()==popped[i])//当我们此时的栈顶元素等于我们要出栈的元素的话
{
st.pop();//出栈操作
i++;
}
}
return i==n;//判断此时我们的popped这个栈中的元素是否都出完了，如果出完了话就说明这两个栈是相同的
}
};腾讯云开发者
