襄阳做淘宝网站推广,360官网入口,wordpress点击慢,合同协议模板♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥ ♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥ ♥♥♥我们一起努力成为更好的自己~♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥ ✨✨✨✨✨✨个人… ♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥ ♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥ ♥♥♥我们一起努力成为更好的自己~♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥ ✨✨✨✨✨✨个人主页✨✨✨✨✨✨ 这一篇博客我们来探讨一下有关于栈的算法练习题准备好了吗~我们发车去探索算法的奥秘啦~
目录
前言
删除字符串中所有相邻重复项
比较含退格的字符串
基本计算器Ⅱ
字符串解码
验证栈序列 前言 我们先来简单复习一下栈这个数据结构栈Stack是一种后进先出的数据结构我们可以想象一叠盘子你通常会把新洗好的盘子放在最上面入栈而当你需要用一个盘子时你会从最上面拿走一个出栈你无法直接从中间或底部抽出一个盘子栈的工作原理正是如此。 话不多说我们上题~
删除字符串中所有相邻重复项
删除字符串中所有相邻重复项 看这题目有点眼熟既然要删除重复字符我们就得记录前面一个字符判断是否重复这也就使用到我们强大的数据结构——栈。 算法思路栈模拟过程 ①创建一个空栈 ②遍历字符串如果栈不为空并且栈顶元素与当前字符相等那么栈顶元素出栈否则当前字符入栈 ③栈中剩余字符出栈保存到字符串中 代码实现
//删除字符串中所有相邻重复项
class Solution
{
public:string removeDuplicates(string s){//使用数据结构容器——栈stackchar st;//遍历字符串for (auto e : s){//如果栈不为空并且栈顶元素与当前字符相等那么栈顶元素出栈if (st.size() e st.top()){st.pop();}//否则当前字符入栈(包括空栈的情况)else{st.push(e);}}string ret;//保存返回结果while (!st.empty()){ret st.top();st.pop();}//逆序字符串就是正确结果reverse(ret.begin(), ret.end());return ret;}
}; 顺利通过~不过这里的代码看起来还是有一些繁琐我们有没有什么办法优化一下主要在于栈中保存的仅仅是字符需要进行提取才能得到我们的答案那我们可以与字符串联系起来~
优化思路因为要返回的是字符串我们可以使用字符串来模拟栈工作的过程字符串最后一个位置也就是我们的栈顶~
代码实现
class Solution
{
public:string removeDuplicates(string s){//字符串模拟栈string st;for (auto e : s){if (st.size() st.back() e){st.pop_back();}else{st e;}}return st;}
}; 顺利通过~
比较含退格的字符串
比较含退格的字符串 这一个题目与第一个题目类似都是使用栈模拟这个过程我们这里直接给出优化的算法思路~ 算法思路字符串模拟栈实现过程 ①根据题目要求每一个字符串进行相同的变化封装成一个函数changeS ②changS函数内部使用字符串模拟栈当栈不为空并且当前字符为‘#时栈顶元素出栈否则当前字符不为’#‘就入栈如果对空文本输入退格字符文本继续为空 ③判断两个字符串变化后是否相等 代码实现
//比较含退格的字符
class Solution
{
public:bool backspaceCompare(string s, string t){return changeS(s) changeS(t);}string changeS(string s){string ret;for (auto e : s){//当栈不为空并且当前字符为‘#时栈顶元素出栈if (ret.size() e #){ret.pop_back();}else if (e ! #)//小写字母入栈{ret.push_back(e);}}return ret;}
}; 顺利通过~
基本计算器Ⅱ
基本计算器Ⅱ 题目要求我们实现一个简单的计算器我们这里给出一个巧妙的算法思路~ 算法思路使用栈保存正数或者负数 ①栈存储中间结果栈用于存储需要累加的值正数或负数乘除运算立即计算并更新栈顶 ②运算符延迟处理遇到新运算符时只记录遇到下一个数字时才应用上一个运算符 ③处理优先级通过立即计算乘除运算实现先乘除后加减 ④空格直接跳过 ⑤栈中所有数据相加就是计算结果 运算符处理规则
前一个运算符当前数字处理方式st.push(val)-st.push(-val)*st.top() * val/st.top() / val
代码实现
//基本计算器Ⅱ
class Solution
{
public:int calculate(string s){int n s.size();char c ;//运算符号记录stackint st;//栈保存计算结果int i 0;//记录下标while (i n){//如果是空格直接跳过if (s[i] )i;//如果是数字else if (s[i] 0 s[i] 9){//提取数字int val 0;//保存数据while (s[i] 0 s[i] 9){val val * 10 (s[i] - 0);i;}//判断数字前面的运算符if (c ){st.push(val);}else if (c -){st.push(-val);}else if (c *){st.top() * val;}else if (c /){st.top() / val;}}//如果是其他也就是运算符更新符号else{c s[i];}}//取栈中元素相加得到运算结果int ret 0;while (!st.empty()){ret st.top();st.pop();}//返回结果return ret;}
}; 顺利通过~这个题目也可以使用数组模拟栈实现功能大家感兴趣可以自己试一试~
字符串解码
字符串解码 我们需要根据要求进行字符串解码好在给出的字符串是没有空格的并且[ ]也是正确匹配的我们可以进行分情况讨论处理。 算法思路分情况讨论 ①双栈结构使用两个独立栈协同工作 st_int存储数字重复次数 st_str存储字符串片段初始化时st_str压入空字符串作为结果容器 ②四类字符处理逻辑 数字0-9 连续解析完整数字如12→12压入st_int 左括号[ 提取后续连续小写字母如[abc→abc作为新片段压入st_str 小写字母a-z 直接拼接到st_str栈顶字符串末尾 右括号] 弹出st_int栈顶数字n和st_str栈顶字符串s将s重复n次后拼接到新栈顶 ③嵌套解码机制 遇到[时压入新层级遇到]时完成当前层级解码 内层字符串先解码如3[c]→ccc 结果拼接到外层字符串如abccc→abccc 支持任意深度嵌套如3[a2[c]]→accaccacc ④结果生成 最终返回st_str栈顶字符串 初始空字符串作为基础容器 所有层级解码完成后栈顶即完整结果 时间复杂度O(n)空间复杂度O(解码字符串长度) 代码实现
//字符串解码
class Solution
{
public:string decodeString(string s){stackint st_int;//保存数字stackstring st_str;//保存字符串st_str.push();//插入空字符串分别后续变形int i 0;while (i s.size()){//分情况讨论//如果是数字提取数字入数字栈if (s[i] 0 s[i] 9){int tmp 0;while (s[i] 0 s[i] 9){tmp 10 * tmp (s[i] - 0);i;}st_int.push(tmp);}//如果是[,提取后续字符保存到字符栈else if (s[i] [){i;string tmp;while (s[i] a s[i] z){tmp s[i];i;}st_str.push(tmp);}//如果是字符那么加到字符栈栈顶字符串末尾else if (s[i] a s[i] z){st_str.top() s[i];i;}//如果是],就取数字栈和字符栈栈顶进行拼接else if (s[i] ]){string s st_str.top();int n st_int.top();st_int.pop();st_str.pop();for (int j 0; j n; j){st_str.top() s;//新字符栈拼接重复的字符}i;}}return st_str.top();//字符栈顶就是需要的结果}
}; 顺利通过~
验证栈序列
验证栈序列 我们以前都做过类似的文字题那么使用代码怎么解决呢答案是进行模拟就可以了~ 算法思路使用栈模拟 ①模拟核心逻辑使用栈 st 实时模拟入栈/出栈操作指针 i 跟踪 popped 序列当前位置验证其合法性 ②入栈与即时匹配遍历 pushed 序列每个元素立即入栈入栈后循环检查当栈非空且栈顶元素等于 popped[i] 时→ 弹出栈顶元素→ i 指针后移匹配成功 代码实现
//验证栈序列
class Solution
{
public:bool validateStackSequences(vectorint pushed, vectorint popped){stackint st;int i 0;//用于遍历出栈序列for (auto e : pushed)//遍历进栈序列{st.push(e);while (st.size() st.top() popped[i]){st.pop();i;}}//通过判断栈是否为空或者i是否走到末尾判断是否为合法出栈序列return st.empty();//return ipopped.size();}
}; 顺利通过~ ♥♥♥本篇博客内容结束期待与各位优秀程序员交流有什么问题请私信♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ✨✨✨✨✨✨个人主页✨✨✨✨✨✨
