个人网站介绍,六灶网站建设,网页设计与制作工资多少,线上名片制作【ps】本篇有 5 道 leetcode OJ。 目录
一、算法简介
二、相关例题
1#xff09;删除字符串中的所有相邻重复项
.1- 题目解析
.2- 代码编写
2#xff09;比较含退格的字符串
.1- 题目解析
.2- 代码编写
3#xff09;基本计算器 II
.1- 题目解析
.2- 代码编写
4删除字符串中的所有相邻重复项
.1- 题目解析
.2- 代码编写
2比较含退格的字符串
.1- 题目解析
.2- 代码编写
3基本计算器 II
.1- 题目解析
.2- 代码编写
4字符串解码
.1- 题目解析
.2- 代码编写
5验证栈序列
.1- 题目解析
.2- 代码编写 一、算法简介 栈是一种特殊的线性表只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底栈中的数据元素遵守后进先出的原则。它的插入操作叫做进栈或进栈/入栈插入的数据在栈顶删除操作叫做出栈。出的数据也在栈顶。 栈一般与模拟算法结合在一起出题在题目中野经常充当数据的缓存容器来帮助模拟入栈和出栈的过程以求得结果。 二、相关例题
1删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 .1- 题目解析 我们用一个新字符串对每个字符模拟入栈和出栈的过程即可具体方式是遍历字符串从左往右依此将字符入栈尾插入新字符串如果当前字符与栈顶的字符新字符串的末尾字符相同就将栈顶的字符出栈对新字符串尾删且跳过当前字符继续遍历下一个字符。 .2- 代码编写
class Solution {
public:string removeDuplicates(string s) {string ret;for(int i0;is.size();i){//用一个新字符串对每个字符模拟入栈和出栈的过程if(ret.size() s[i]ret.back())ret.pop_back();else rets[i];}return ret;}
}; 2比较含退格的字符串
844. 比较含退格的字符串 .1- 题目解析 类似的这道题也可以用字符串来模拟入栈和出栈的过程但与上道题不同的是出栈的条件变成了若当前字符为 #入栈的条件为若当前字符不为 #。 .2- 代码编写
class Solution {
public:bool backspaceCompare(string s, string t) {return stackString(s)stackString(t);}//用一个新字符串模拟入栈和出栈的过程string stackString(string s){string st;for(auto ch:s){if(ch#){if(st.size())st.pop_back();}else {stch;}}return st;}
}; 3基本计算器 II
227. 基本计算器 II .1- 题目解析 这道题只有加减乘除四个运算没有括号并且每一个数都是大于等于 0 的 这样可以大大地减少需要处理的情况。 由于表达式里面没有括号因此只用处理加减乘除混合运算即可这样不需要用到双栈。根据四则运算的顺序我们可以先计算乘除法然后再计算加减法。由此可以得出下面的结论
当一个数前面是 号的时候这⼀个数是否会被立即计算是不确定的因此可以先入栈。当一个数前面是 - 号的时候这⼀个数是否被立即计算也是不确定的但是这个数已经和前面的负号绑定了因此可以将这个数的相反数入栈。当一个数前面是 * 号的时候这⼀个数可以立即与前面的⼀个数相乘此时让将栈顶的元素乘上这个数当一个数前面是 / 号的时候这⼀个数也是可以立即被计算的因此让栈顶元素除以这个数。 当遍历完完整的表达式时栈中剩余的元素之和就是最终结果。此外这里可以用数组来模拟栈。 .2- 代码编写
class Solution {
public:int calculate(string s) {char op;//表达式开头没有运算符但应默认是号int i0,ns.size();vectorint st;//用数组模拟栈while(in){if(s[i] )i;//跳过空格else if(s[i]0s[i]9){int tmp0;//提取一个完整的操作数while(in s[i]0 s[i]9){tmptmp*10(s[i]-0);}//按运算符处理操作数if(op)st.push_back(tmp);else if(op-)st.push_back(-tmp);else if(op*)st.back()*tmp;else if(op/)st.back()/tmp;}else ops[i];}//累加栈中的数即可得到结果int ret0;for(auto x:st)retx;return ret;}
}; 4字符串解码
394. 字符串解码 .1- 题目解析 本题可以用两个栈来模拟解码的过程其中一个栈存字符另一个栈存数字。 解码的顺序是从括号内部向外部依此解码如3[ab2[cd]] - 3[abcd cd] - abcdcd abcdcd abcdcd 。 .2- 代码编写
class Solution {
public:string decodeString(string s) {stackint nums; //数字栈stackstring st;//字符栈st.push();//预留一个空字符串以防越界访问int i0,ns.size();while(in){//提取数字放入数字栈中if(s[i]0s[i]9){int tmp0;while(s[i]0s[i]9){tmptmp*10(s[i]-0);}nums.push(tmp);}//遇到[提取字符串放入字符栈中else if(s[i][){i;string tmp;while(s[i]as[i]z){tmps[i];}st.push(tmp);}//遇到]解析然后将其尾插到字符栈栈顶字符串的后面else if(s[i]]){string tmpst.top();st.pop();int knums.top();nums.pop();while(k--){st.top()tmp;}i;}//提取字符串直接尾插到字符栈栈顶字符串的后面else{string tmp;while(in s[i]a s[i]z){tmps[i];}st.top()tmp;}}return st.top();}
}; 5验证栈序列
946. 验证栈序列 .1- 题目解析 这是一道经典的栈相关的题目给定一个进栈序列再给定一个出栈序列要求根据进栈序列判断出栈序列是否合法。 我们可以创建一个栈然后分别遍历这两个序列来模拟进栈和出栈的过程。遍历进栈序列的时候先将序列中的元素依此 push 入栈再遍历出栈序列中的元素如果当前元素与刚入栈的这个元素相同那么就将其出栈如果不是就继续对进栈序列中的元素进行入栈直到遇到出栈序列中的相同元素再出栈。如此遍历完两个序列后如果栈为空则说明栈序列是合法的。 .2- 代码编写
class Solution {
public:bool validateStackSequences(vectorint pushed, vectorint popped) {stackint st;int i0;for(auto x:pushed){st.push(x);while(st.size()st.top()popped[i]){st.pop();i;}}return st.empty();}
};
