安徽省同济建设集团网站,做视频添加字幕的网站,泰安招工招聘信息,jq效果较多的网站文章目录 删除字符串中的所有相邻重复项比较含退格的字符串基本计算机II字符串解码验证栈序列 栈是一种先进后出的数据结构#xff0c;其操作主要有 进栈、压栈#xff08;Push#xff09; 出栈#xff08;Pop#xff09; 常见的使用栈的算法题
中缀转后缀逆波兰表达式求… 文章目录 删除字符串中的所有相邻重复项比较含退格的字符串基本计算机II字符串解码验证栈序列 栈是一种先进后出的数据结构其操作主要有 进栈、压栈Push 出栈Pop 常见的使用栈的算法题
中缀转后缀逆波兰表达式求值括号匹配深度优先搜索
删除字符串中的所有相邻重复项 题目删除字符串中的所有相邻重复项 思路
用栈的思想来模拟遍历字符串如果栈为空或栈顶元素和进栈元素不相同字符进栈否则即栈顶元素和进栈元素相同则pop栈顶元素但是最后留在栈中的字符就是需要返回的并且是逆序的所以我们直接用原来的字符串模拟栈
C代码
class Solution
{
public:string removeDuplicates(string s) {string res;for(auto ch : s){if(res.size() res.back() ch) res.pop_back();else res.push_back(ch);}return res;}
};比较含退格的字符串 题目比较含退格的字符串 思路
利用栈的思想封装一个check函数来返回退格后的字符串chech函数的实现遍历字符串如果不是#直接加到res上否则如果res中没有元素但是遇到了#直接跳过不用pop_back()
C代码
class Solution
{
public:string check(string s){string res;for(auto ch : s){if(ch ! #) res ch; // 如果不是‘#’。直接加到res上else{if(res.size()) // 如果res中没有元素但是遇到了‘#’应该直接跳过不用pop_back()res.pop_back();} }return res;}bool backspaceCompare(string s, string t) {return check(s) check(t); // 检查退格后的字符串是否相等}
};基本计算机II 题目基本计算器 II 思路
由于运算符只有(, -, *, /)这四种我们使用一个数组来模拟栈插入每一个数使用一个前缀字符来进行运算符的标记初始设为加当操作符op遇到加减都更新遇到乘除则与栈顶元素计算遍历结束后我们将栈中元素相加
C代码
class Solution
{
public:// 1. 遇到操作符更新操作符op// 2. 遇到数字// 1. 先将数字提取到tmp中// 2. 根据op分类讨论// ①op , tmp入栈// ②op -, -tmp入栈// ③op *, 直接和栈顶元素相×// ④op /, 直接和栈顶元素相÷int calculate(string s) {char op ;int i 0, n s.size();vectorint v; // 模拟栈while(i n){if(s[i] ) i;else if(0 s[i] s[i] 9){// 数字提取到tmp中int tmp 0;while(i n 0 s[i] s[i] 9)tmp 10 * tmp (s[i] - 0);if(op ) v.push_back(tmp);else if(op -) v.push_back(-tmp);else if(op *) v.back() * tmp;else v.back() / tmp;}else {op s[i];i;}}int res 0;for(auto x : v){res x;}return res;}
};字符串解码 题目字符串解码 思路
定义两个栈一个字符串、一个int变量遇到数字放入数字栈遇到[把后面的字符串提取、放入字符串栈遇到]取出两栈顶元素解析放入字符串栈的栈顶元素后面遇到字符 提取字符放入字符串栈的栈顶元素后面
C代码
class Solution
{
public:// 两个栈一个字符串、一个int变量// 1. 遇到数字放入数字栈// 2. 遇到[把后面的字符串提取、放入字符串栈// 3. 遇到]取出两栈顶元素解析放入字符串栈的栈顶元素后面// 4. 遇到字符 提取字符放入字符串栈的栈顶元素后面string decodeString(string s) {stackstring ss;stackint si;int i 0, n s.size();ss.push();while(i n){if(s[i] 0 s[i] 9) {int t 0;while (0 s[i] s[i] 9)t 10 * t (s[i] - 0);si.push(t);}else if(s[i] [) {i;string t ;while(s[i] a s[i] z)t s[i];ss.push(t);}else if(s[i] ]){string t ss.top();ss.pop();int j si.top();si.pop();while(j--){ss.top() t;}i; // 跳过右括号}else{string t ;while(i n s[i] a s[i] z)t s[i];ss.top() t;}}return ss.top();}
};验证栈序列 题目验证栈序列 思路 用一个栈来模拟这个过程最后栈为空则说明相匹配否则说明不匹配 用i来遍历pop数组确定要出栈的元素判断栈顶元素是否等于要出栈的元素如果相等则出栈并i到下一个要出栈的元素上 class Solution
{
public:bool validateStackSequences(vectorint pushed, vectorint popped) {stackint s;int n popped.size();int i 0; // 标志位确定要出栈的元素for(auto ch : pushed){s.push(ch);// 判断栈顶元素是否等于要出栈的元素如果相等则出栈并将标志位挪到下一个要出栈的元素上while(s.size() s.top() popped[i]) {s.pop();i;}}return s.empty(); }
};
