您的位置:首页 > 游戏 > 手游 > 广州高端网站设计公司排名_sketchup模型库免费下载_百度 官网_电商怎么推广自己的产品

广州高端网站设计公司排名_sketchup模型库免费下载_百度 官网_电商怎么推广自己的产品

2025/3/16 5:53:23 来源:https://blog.csdn.net/2301_79722622/article/details/146243801  浏览:    关键词:广州高端网站设计公司排名_sketchup模型库免费下载_百度 官网_电商怎么推广自己的产品
广州高端网站设计公司排名_sketchup模型库免费下载_百度 官网_电商怎么推广自己的产品

文章目录

  • 删除字符串中所有相邻重复项
    • 题解
    • 代码
  • 比较含退格的字符串
    • 题解
    • 代码
  • 基本计算器II
    • 题解
    • 代码
  • 字符串解码
    • 题解
    • 代码
  • 验证栈序列
    • 题解
    • 代码
  • 总结

删除字符串中所有相邻重复项

题目链接
在这里插入图片描述

题解

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] 可能是超大的

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com