20.有效的括号
遇到左括号入栈，遇到右括号弹出
bool isValid(string s) {
stack<char> kuohao;
char c;
for (char a : s) {
switch (a)
{
case'(':
case'{':
case'[':
kuohao.push(a);
break;
case')':
case'}':
case']':
if (kuohao.empty())
return false;
c = kuohao.top();
kuohao.pop();
if ((a == ')' && c == '(') || (a == ']' && c == '[') || (a == '}' && c == '{'))
continue;
else
return false;
default:
break;
}
}
if (kuohao.empty())
return true;
return false;
}
1047.删除字符串中的所有相邻重复项
- 使用栈
string removeDuplicates(string s) {
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (st.empty()||st.push(s[i]);)
{
st.push(s[i]);
continue;
}
else if (s[i] == st.top())
st.pop();
}
string result="";
int size = st.size();
for (int j = 0; j < size; j++) {
result+= st.top(); //字符串string可以+=，不能result[j]=
st.pop();
}
reverse(result.begin(), result.end());
return result;
}
- 直接使用字符串string，不用再翻转转换
string removeDuplicates(string S) {
string result;
for(char s : S) {
if(result.empty() || result.back() != s) {
result.push_back(s);
}
else {
result.pop_back();
}
}
return result;
}
150.逆波兰表达式求值
int evalRPN(vector<string>& tokens) {
stack<int> number;
for (string s : tokens) {
if (s == "*" || s == "+" || s == "/" || s == "-")
{
int a, b;
a = number.top();
number.pop();
b = number.top();
number.pop();
if (s == "*") number.push(a * b);
else if (s == "/") number.push(b / a);
else if (s == "+") number.push(a + b);
else if (s == "-") number.push(b - a);
}
else
number.push(stoi(s));
}
return number.top();
}