今日刷题3道：20. 有效的括号，1047. 删除字符串中的所有相邻重复项，150. 逆波兰表达式求值
● 20. 有效的括号
题目链接/文章讲解/视频讲解：https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
碎碎念：主要考虑三种情况，左括号多，左右括号不匹配，右括号多，解题技巧是在匹配左括号的时候，让对应的右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
class Solution { public: stack<char> sk; bool isValid(string s) { if(s.size()%2==1) return false; for(int i=0;i<s.size();i++){ if(s[i]=='(') sk.push(')'); else if(s[i]=='[') sk.push(']'); else if(s[i]=='{') sk.push('}'); else if(!sk.empty()&&s[i]==sk.top()){ sk.pop(); } else{ return false; }} return sk.empty(); } };
● 1047. 删除字符串中的所有相邻重复项
碎碎念：用栈来存放已经遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素，若有，则从栈中删除，最后拼成字符串，逆置一下栈中元素即可。
class Solution { public: string removeDuplicates(string s) { stack<char> sk; for(char ss : s){ if(sk.empty() || ss != sk.top()){ sk.push(ss); } else{ sk.pop(); } } string st = ""; while(!sk.empty()){ st += sk.top(); sk.pop(); } reverse(st.begin(),st.end()); return st; } }; 也可以用字符串去模拟栈，因为用栈的话还要转为字符串并逆置。 class Solution { public: string removeDuplicates(string s) { string st = ""; for(char ss : s){ if(st.empty() || ss != st.back()){ //s.back()是取字符串的最后一个元素 st.push_back(ss); //s.push_back()是添加到字符串的末尾 } else{ st.pop_back(); //删除末尾元素 } } return st; } };● 150. 逆波兰表达式求值
题目链接/文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
碎碎念：逆波兰表达式相当于是二叉树中的后序遍历。可以用栈解决，遍历字符串，若是数字则进栈。若是运算符则出栈两个元素，再把二者的运算结果压入栈即可，数值很大，需要用long long型，然后还要注意是nums2-nums1。
class Solution { public: int evalRPN(vector<string>& tokens) { stack<long long> sk; for(int i=0;i<tokens.size();i++){ if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/"){ long long nums1=sk.top();sk.pop(); long long nums2=sk.top();sk.pop(); if(tokens[i]=="+") sk.push(nums2+nums1); if(tokens[i]=="-") sk.push(nums2-nums1); if(tokens[i]=="*") sk.push(nums2*nums1); if(tokens[i]=="/") sk.push(nums2/nums1); } else{ sk.push(stoll(tokens[i])); //stoll（）此函数将在函数调用中作为参数提供的字符串转换为long long int。它解析str并将其内容解释为指定基数的整数，并将其作为long long int类型的值返回。 } } return sk.top(); } }; 标签：11,tokens,string,训练营,随想录,long,st,sk,push From： https://www.cnblogs.com/zzw0612/p/17032420.html