【算法训练营day11】LeetCode20. 有效的括号 LeetCode1047. 删除字符串中的所有相邻重复项 LeetCode150. 逆波兰表达式求值
LeetCode20. 有效的括号
题目链接：20. 有效的括号
初次尝试
遍历字符串，遇见左括号进栈，遇见右括号且栈不为空出栈，出栈后判断是不是一对括号，感觉写的有点复杂了，还可以优化。
class Solution {
public:
bool isValid(string s) {
stack<int> st;
int temp;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(1);
else if (s[i] == '[') st.push(2);
else if (s[i] == '{') st.push(3);
else if (s[i] == ')' && !st.empty()) {
temp = st.top();
if (temp != 1) return false;
st.pop();
}
else if (s[i] == ']' && !st.empty()) {
temp = st.top();
if (temp != 2) return false;
st.pop();
}
else if (s[i] == '}' && !st.empty()) {
temp = st.top();
if (temp != 3) return false;
st.pop();
}
else return false;
}
if (st.empty()) return true;
else return false;
}
};
看完代码随想录后的想法
可以在遇见左括号时，直接入栈右括号，这样后面也不需要讨论右括号的种类，只需要判断s[i]和st.top()的元素是否相等就可以了，省去了很多代码。
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(')');
else if (s[i] == '[') st.push(']');
else if (s[i] == '{') st.push('}');
else if (!st.empty() && s[i] == st.top()) st.pop();
else return false;
}
return st.empty();
}
};
LeetCode1047. 删除字符串中的所有相邻重复项
题目链接：1047. 删除字符串中的所有相邻重复项
初次尝试
有点类似消消乐的思路，遍历字符串，判断指向的字符是否等于栈顶字符，如果相等就出栈，不相等就把指向的字符入栈，最后从栈中输出剩下的字符串。
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (!st.empty() && s[i] == st.top()) {
st.pop();
}
else {
st.push(s[i]);
}
}
string ans = "";
while (!st.empty()) {
ans += st.top();
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};
看完代码随想录后的想法
一样的思路。
LeetCode150. 逆波兰表达式求值
题目链接：150. 逆波兰表达式求值
初次尝试
题目中这句话已经指明了这道题的思路，按照这个思路写代码就行。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long int> st;
for (int i = 0; i < tokens.size(); i ++) {
if (tokens[i] == "+") {
long int a = st.top();
st.pop();
long int b = st.top();
st.pop();
st.push(b + a);
}
else if (tokens[i] == "-") {
long int a = st.top();
st.pop();
long int b = st.top();
st.pop();
st.push(b - a);
}
else if (tokens[i] == "*") {
long int a = st.top();
st.pop();
long int b = st.top();
st.pop();
st.push(b * a);
}
else if (tokens[i] == "/") {
long int a = st.top();
st.pop();
long int b = st.top();
st.pop();
st.push(b / a);
}
else {
st.push(stoi(tokens[i]));
}
}
return st.top();
}
};
看完代码随想录后的想法
思路一样，代码还有可以优化的地方：
long long比long int更好，而且后面stoi()这个函数也应该相应修改为stoll()。- 多个
if有重复的部分可以合并一下，减少代码量。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
<<<<<<< HEAD
stack<long long> st;
=======
// 力扣修改了后台测试数据，需要用longlong
stack<long long> st;
>>>>>>> 28f3b52a82e3cc650290fb02030a53900e122f43
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
if (tokens[i] == "+") st.push(num2 + num1);
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]));
}
}
int result = st.top();
st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
return result;
}
};