本文最后更新于 2024年8月18日 下午
今日内容： - 20.有效的括号
- 1047.删除字符串中所有相邻重复项
- 150.逆波兰表达式求值
20.有效的括号
其实这题跟最后一个逆波兰表达式有关，最后一题是逆波兰表达式求值，但是根据中缀表达式生成逆波兰表达式的算法里就会用到栈来处理中缀中的括号问题。
所以一个栈直接秒了，思路打开，碰到左括号别傻傻push左括号，而得push右括号，这样就可以直接判断top()了，而不用碰到右括号的时候再来个转换。
没错，我这次就push的左括号，碰到右括号的时候还用ASCII码去算对应的左括号值
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool isValid(string s) {
if(s.size() % 2 != 0) return false;
stack<char> b;
for(int i = 0;i < s.size();i++) {
if(s[i] == '(') b.push(')');
else if(s[i] == '[') b.push(']');
else if(s[i] == '{') b.push('}');
else if(b.empty() || s[i] != b.top()) return false;
else b.pop();
}
return b.empty();
}
};
|
1047.删除字符串中所有相邻重复项
如果不告诉用栈做的话，貌似还挺复杂的，不过用栈就很简单了
压栈前判断栈顶是不是重复，重复就pop，不重复就push，建议从尾到头遍历s，这样全pop出来时顺序还是对的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
int i = s.size() - 1;
for(;i >= 0;i--) {
if(st.empty() || st.top() != s[i]) st.push(s[i]);
else st.pop();
}
string ans;
for(i = 0;!st.empty();i++) {
ans.push_back(st.top());
st.pop();
}
return ans;
}
};
|
105.逆波兰表达式求值
笔者大一下的Qt课设就是写一个大数计算器，对这逆波兰表达式还是比较熟悉，有了式子，求值就比较简单了，这个题还确保了int不炸。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(int i = 0;i < tokens.size();i++) {
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
int num1 = st.top();
st.pop();
int num2 = st.top();
st.pop();
if(tokens[i] == "+") st.push(num1 + num2);
if(tokens[i] == "-") st.push(num2 - num1);
if(tokens[i] == "*") st.push(num1 * num2);
if(tokens[i] == "/") st.push(num2 / num1);
}
else
st.push(stoi(tokens[i]));
}
int res = st.top();
st.pop();
return res;
}
};
|