20. 有效的括号
文章讲解:代码随想录
视频讲解:栈的拿手好戏!| LeetCode:20. 有效的括号_哔哩哔哩_bilibili
题目链接:. - 力扣(LeetCode)
解题思路:
1.有三种不匹配情况。第一种,遍历完字符串栈不为空,如:( { [ ] } ( ),第二种,遍历字符串途中栈顶和遍历到的字符不相等,如:( [ { } } ),第三种,还没遍历完字符串栈就为空,如:
( { [ ] } ) ) )。
- 时间复杂度: O(n)
- 空间复杂度: O(n)
关键点:
1.先想明白全部不匹配的情况再写if代码。
c++代码:
class Solution
{
public:
bool isValid(string s)
{
if(s.size()%2 != 0) return false;
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() || st.top() != s[i]) return false;
else st.pop();
}
return st.empty();
}
};
1047. 删除字符串中的所有相邻重复项
文章讲解:代码随想录
视频讲解:栈的好戏还要继续!| LeetCode:1047. 删除字符串中的所有相邻重复项_哔哩哔哩_bilibili
题目链接:. - 力扣(LeetCode)
解题思路:
1.把字符串字符一个个放入栈,每次进入循环先判断字符和栈顶字符是否相等,相等则将字符从栈中pop,然后遍历下一个字符,最后从栈取元素并反转顺序。
关键点:
1.无
c++代码:
class Solution
{
public:
string removeDuplicates(string s)
{
stack<char> st;
for(char cc:s)
{
if(st.empty() || st.top() != cc)
{
st.push(cc);
}
else
{
st.pop();
}
}
string result = "";
while(!st.empty())
{
result += st.top();
st.pop();
}
reverse(result.begin(),result.end());
return result;
}
};
150. 逆波兰表达式求值
文章讲解:代码随想录
视频讲解:栈的最后表演! | LeetCode:150. 逆波兰表达式求值_哔哩哔哩_bilibili
题目链接:. - 力扣(LeetCode)
解题思路:
关键点:
1.进行运算时,是nums2在前
c++代码:
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(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(stoi(tokens[i]));
}
}
int result = st.top();
return result;
}
};