天晴创艺网站建设百度小程序,佛山网站优化步骤,58同城本地网页版,网站设计制作从哪里学起#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 有效的括号删除字符串中的所… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 有效的括号删除字符串中的所有相邻重复项逆波兰表达式求值总结 有效的括号
20. 有效的括号 这道题相信学过数据结构的同学应该并不陌生这道题是一道在学习栈的时候的一道十分经典的题型起初第一次接触的时候多少会有点感觉难现在做来还行的。
题目要求就是将所有的括号匹配起来主要有两种情况会匹配失败 一种是左括号或者右括号出现多余的情况另一种情况是前一个括号与后一个括号不能连续匹配我们可以根据栈这个数据结构的特点使左括号字符都放进去遇到右括号的时候top一下看看栈顶元素是否为相匹配的左括号如果相匹配我们将其弹出栈然后接着遍历如果不匹配我们直接return false
注意如果在碰到右括号时候栈为空则说明栈中没有左括号那么此时直接弹出说明右括号有多余的。如果将整个字符都遍历完了依然没有return那么则说明第二种情况已经判断完毕并没有括号不匹配的情况出现但是此时并不代表就一定没有错误当匹配完毕之后如果栈中还剩下括号说明左括号有多余的。
class Solution {
public:bool isValid(string s) {stackint arr1;for(int i0;is.size();i){if(s[i]!)s[i]!}s[i]!]){arr1.push(s[i]);}if(s[i])){if(arr1.empty()true||arr1.top()!(){return false;}else{arr1.pop();}}if(s[i]}){if(arr1.empty()true||arr1.top()!{){return false;}else{arr1.pop();}}if(s[i]]){if(arr1.empty()true||arr1.top()![){return false;}else{arr1.pop();}}}if(arr1.empty()true){return true;}else{return false;}}
};还有另一种思路在遇到左括号时候往栈里直接加入右括号然后碰到右括号时候在进行判断和上一种思路基本上是一样的。
class Solution {
public:bool isValid(string s) {if(s.size()%2!0){// 如果s的长度为奇数一定不符合要求return false;}stackcharst;for(int i0;is.size();i){if(s[i](){st.push());}else if(s[i]{){st.push(});}else if(s[i][){st.push(]);}// 第二种情况遍历字符串匹配的过程中发现栈里没有我们要匹配的字符。所以return false// 第三种情况遍历字符串匹配的过程中栈已经为空了没有匹配的字符了说明右括号没有找到对应的左括号 return falseelse if(st.empty()||st.top()!s[i]){return false;}else{ // st.top() 与 s[i]相等栈弹出元素st.pop();}}// 第一种情况此时我们已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号来匹配所以return false否则就return truereturn st.empty();}
};删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 这道题是消除字符串中连续的字符只要有相邻重复就直接删除所以并不是我们第一眼看到只有一处相邻相同字符就只删一次可能在删除一处之后又有新的元素碰到一起这时栈派上了用场它可以存储我们遍历过的数据我们只需要判断当前遍历的数据是否和栈顶元素一样一致就将其弹出这样不仅解决了表面的相邻相同字符消去当消去后如果有两个新的相邻相同元素碰到一起了我们也能发现并消除他们一举多得。
class Solution {
public:string removeDuplicates(string s) {stackint st;for(char s1:s){if(st.empty()||s1!st.top()){st.push(s1);}else{st.pop();// s 与 st.top()相等的情况}}string result;while(!st.empty()){// 将栈中元素放到result字符串汇总resultst.top();st.pop();}reverse(result.begin(),result.end()); // 此时字符串需要反转一下return result;}
};上面的代码我们用字符串来模拟栈的一个实现让字符串的头部充当栈底尾部充当栈顶这样做的好处是避免了直接使用栈的时候数据元素是倒序且还要转换为字符串输出。
class Solution {
public:string removeDuplicates(string s) {string result;for(char s1:s){if(result.empty()||result.back()!s1){result.push_back(s1);}else{result.pop_back();}}return result;}
};逆波兰表达式求值
150. 逆波兰表达式求值
逆波兰表达式求值这道题的难度是中等题并不是是它有多么难的思路而是如果你没有接触到这个题不是很容易想到解题思路逆波兰表达式实际上就是一种后缀表达式可以把我们日常熟悉的一个等式12* 3*4看成中序表达式画树形图很容易得出那么后续表达式大题运算思路就是两个数遇到符号再进行运算操作没遇到符号时候先保留起来每次遇到符号拿出两个操作数操作这种思路很适用于栈的数据结构。
class Solution {
public:int evalRPN(vectorstring tokens) {stackint st;for(int i0;itokens.size();i){if(tokens[i]||tokens[i]-||tokens[i]*||tokens[i]/){long long num1st.top();st.pop();long long num2st.top();st.pop();if(tokens[i]){st.push(num1num2);}if(tokens[i]-){st.push(num2-num1);}if(tokens[i]*){st.push(num2*num1);}if(tokens[i]/){st.push(num2/num1);}}else{st.push(stoll(tokens[i]));//在C中std::stoll函数用于将字符串转换为长整型long long数据类型。}}int result st.top();st.pop();// 把栈里最后一个元素弹出其实不弹出也没事return result;}
};具体代码如上在未碰到操作符时将数字入栈遇到操作符再取出两个操作符值得注意的是操作数顺序很重要是第二个操作数相对于第一个操作数来进行操作数据放入里的stoll函数作用是将字符串转换为long数据类型。此外这道题并不需要我们来判断传输进来的数据是否合法只需要我们写出判断字符和数据的代码即可。
总结
今天我们完成了有效的括号、删除字符串中的所有相邻重复项、逆波兰表达式求值三道题目相关的思想需要多复习回顾。接下来我们继续进行算法练习·。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
