本文主要是介绍算法刷题Day11 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 0 引言
- 1 有效的括号
- 1.1 我的解题
- 2 删除字符串中的所有相邻重复项
- 2.1 我的解题
- 3 逆波兰表达式求值
- 3.1 我的解题
- 🙋♂️ 作者:海码007
- 📜 专栏:算法专栏
- 💥 标题:
- ❣️ 寄语:书到用时方恨少,事非经过不知难!
0 引言
1 有效的括号
- 🎈 文档讲解
- 🎈 视频讲解
- 🎈 做题状态:简单
1.1 我的解题
class Solution {
public:bool isValid(string s) {stack<char> myStack;// 遇到左括号压栈,遇到右括号则判断与栈顶元素是否构成一对,构成一对则出栈否则压栈for (auto subS : s){if (subS == '(' || subS == '[' || subS == '{'){myStack.push(subS);}else if (subS == ')'){// 如果遇到右括号先出现的情况,则直接返回falseif (myStack.empty()) return false;if (myStack.top() == '('){myStack.pop();}else{myStack.push(subS);}}else if (subS == ']'){// 如果遇到右括号先出现的情况,则直接返回falseif (myStack.empty()) return false;if (myStack.top() == '['){myStack.pop();}else{myStack.push(subS);}}else{// 如果遇到右括号先出现的情况,则直接返回falseif (myStack.empty()) return false;if (myStack.top() == '{'){myStack.pop();} else{myStack.push(subS);}}}return myStack.empty();}
};
2 删除字符串中的所有相邻重复项
- 🎈 文档讲解
- 🎈 视频讲解
- 🎈 做题状态:简单
2.1 我的解题
class Solution {
public:string removeDuplicates(string s) {// 逻辑类似消消乐,遇到相同的元素则删除stack<char> myStack;for (auto subS : s){// 判断新压栈的元素和栈顶元素是否相等,如果相等,则pop栈顶元素if (!myStack.empty() && myStack.top() == subS){myStack.pop();}else{myStack.push(subS);}}//此时要将字符串按顺序输出,则还需要借助一个栈(或者直接使用string的翻转字符串函数 reverse )stack<char> outStack;int size = myStack.size();for (int i = 0; i < size; i++){outStack.push(myStack.top());myStack.pop();}string result;for (int i = 0; i < size; i++){result.push_back(outStack.top());outStack.pop();}return result;}
};
3 逆波兰表达式求值
- 🎈 文档讲解
- 🎈 视频讲解
- 🎈 做题状态:知道规则了也不难
3.1 我的解题
逆波兰表达式求值的规则:从左到右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号就将处于栈顶的两个数字出栈,进行运算(第二个出栈的元素 运算符 第一个出栈的元素),运算结果进栈,一直到获得最终结果。
回顾点:字符串转换为 int 类型的函数 atoi(s.c_str())
,不然还得手动转换
class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> calculate;int leftNumber = 0, rightNumber = 0;for (auto s : tokens){// 遇到数字就入栈if (s != "+" && s != "-" && s != "*" && s != "/"){// 将字符串转换为数字calculate.push(atoi(s.c_str()));continue;}// 遇到运算符就取出栈顶两个元素进行运算,然后再将结果入栈rightNumber = calculate.top();calculate.pop();leftNumber = calculate.top();calculate.pop();if (s == "+"){calculate.push(leftNumber + rightNumber);}else if (s == "-"){calculate.push(leftNumber - rightNumber);}else if (s == "*"){calculate.push(leftNumber * rightNumber);}else{calculate.push(leftNumber / rightNumber);}}return calculate.top();}
};int main()
{vector<string> tokens = { "10","6","9","3","+","-11","*","/","*","17","+","5","+" };Solution test;int result = test.evalRPN(tokens);cout << result;
}
这篇关于算法刷题Day11 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!