高校网站如何建设论文,规模以上工业企业名单,国内永久免费crm系统网站推荐,康体设备网站建设目录#xff1a; 力扣 20. 有效的括号力扣 1047. 删除字符串中的所有相邻重复项力扣 150. 逆波兰表达式求值 问题一、 20. 有效的括号
题目链接#xff1a;20. 有效的括号 - 力扣#xff08;LeetCode#xff09; 思路分析#xff1a; 很多朋友刚开始接触这一类题的时候…目录 力扣 20. 有效的括号力扣 1047. 删除字符串中的所有相邻重复项力扣 150. 逆波兰表达式求值 问题一、 20. 有效的括号
题目链接20. 有效的括号 - 力扣LeetCode 思路分析 很多朋友刚开始接触这一类题的时候 , 可能会没有思路 1、使用栈来解决。 2、遍历字符串遇到左括号 { 、 [ 、 ( ,我们将右括号压入栈中。 3、当我们遇到右括号时则和栈顶元素进行匹配如果不相等则说明没有有效的括号。如果 相等则匹配成功将其出栈。 4、循环结束之后如果栈为空则说明括号是有效的。 文章讲解/视频讲解代码随想录: 代码随想录 问题解答
bool isValid(string s) {stack char st; //定义一个栈//要括号都匹配,说明传入的字符串一定是偶数if( s.length() %2!0) return false;for(int i 0 ;i s.length() ; i){if( s[i](){st.push( ) );continue;}else if( s[i] {){st.push( } );continue;}else if( s[i] [){st.push( ] );continue;}//开始匹配else if( st.empty()!true s[i]st.top()){st.pop();continue;} else {return false;}}if(st.empty()){return true;}return false;
} 问题二、1047. 删除字符串中的所有相邻重复项
题目链接1047. 删除字符串中的所有相邻重复项 - 力扣LeetCode 思路分析
利用栈的特性 用来记录字符串中已经遍历的数据for 循环遍历字符串 , 如果我们的当前字符和栈顶元素相同,则出栈,不同则将其压入栈最后我们需要元素就是栈中的元素,但是我们需要注意的是 , 栈中元素和我们想要的顺序是相反的。提示我们使用字符串来模拟栈的操作
文章讲解/视频讲解 代码随想录 : 代码随想录
问题解答
tring removeDuplicates(string s) {string ret; //用来记录我们遍历过的数据(用字符串来模拟栈的结构)for(int i0 ; is.length() ; i ){//每遍历一个元素都要和栈中的元素进行比较if(ret.empty() || ret.back()!s[i]){ //不相等的情况ret.push_back(s[i]);}else {ret.erase(ret.end()-1);}}return ret;
} 问题三、150. 逆波兰表达式求值
问题链接150. 逆波兰表达式求值 - 力扣LeetCode 思路分析
还是利用栈的特性( 可以记录当前元素的前一个数据 )。 遍历字符串,将整数依次放入栈中,如果遇到有效运算符,这从栈中取出两个数据进行计算 将计算的结果再次放入栈中。 最后栈中剩余的元素就是我们表达式的值。 这里我们想要主要的是 从栈中取出的两个元素 在进行运算的时候是后一个元素放在前面比如取出的数据是 a,b 。操作时应该是 b-a | b*a。 补充: C 中 std::stoistring to integer将字符串转换为整数类型。
文章 | 视频讲解代码随想录代码随想录 问题解答
我这里给出的过程比较冗余,大家可以改进优化一下.
class Solution {
public:void getAB(int a,int b){ast.top();st.pop();bst.top();st.pop();
}
int evalRPN(vectorstring tokens) {//2. 遍历字符串,将整数依次放入栈中,如果遇到有效运算符,这从栈中取出两个数据进行计算//3. 将计算的结果再次放入栈中 int a0 , b0, temp0;for(int i0 ; i tokens.size() ; i){if( tokens[i]* ){getAB(a,b);temp a*b;st.push(temp);continue;}else if( tokens[i]/ ){getAB(a,b);tempb/a;st.push(temp);continue;}else if( tokens[i] ){getAB(a,b);tempab;st.push(temp);continue;}else if( tokens[i]- ){getAB(a,b);tempb-a;st.push(temp);continue;}else{st.push(std::stoi(tokens[i]) );}}return st.top();
}
private://1. 定义一个栈stack int st;
};
总结:
栈的应用场景
合适做一些类似于爱消除的操作,因为栈帮助我们记录了 遍历数组当前元素时候前一个元素是什么。
