20. 有效的括号 - 力扣（LeetCode）
思路:本题使用栈先进后出的特性来解决问题。当遇到左边的符号时推入栈，遇到右边的符号时先判断栈是不是空的，如果此时栈是空的，直接return false，如果此时栈不是空的，继续判断栈顶的元素是否与现在遇到的元素相匹配，如果匹配则弹出，不匹配直接return false，等全部都走完以后还要判断栈是否为空，只有栈为空才能return true，否则return false，因为可能会出现只输入左半边符号的情况
- 标准答案中出现了以下技巧：
- 可以先判断字符长度是不是奇数，如果是奇数肯定不匹配。
- 让右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单很多。
我的AC代码
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(auto a : s) {
if(a == '(' || a == '{' || a == '[') {
st.push(a);
}
else {
char tmp;
if(!st.empty()) {
tmp = st.top();
}
else {
return false;
}
if((tmp == '(' && a == ')') || (tmp == '[' && a == ']') || (tmp == '{' && a == '}') ) {
st.pop();
}
else {
return false;
}
}
}
if(st.empty()) {
return true;
}
else {
return false;
}
}
};标准答案
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) return false; // 如果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(']');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if (st.empty() || st.top() != s[i]) return false;
else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
return st.empty();
}
};1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
思路:遍历字符串，先把字符串的第一个值存入栈。遍历过程中如果遇到栈顶与遍历到的字符相等，则执行出栈操作，否则就入栈，最后栈中存的就是答案。
- 注意：最后从栈中输出的答案是反着的，需要反转字符串，刚开始我想用
ans = string(1, st.top()) + ans结果一直超时，后来发现就是因为这个函数太慢了，千万不要用这个函数 - 推荐使用标准答案中利用字符串模拟栈的方法，该方法时间复杂度和空间复杂度都大大降低
我的AC代码
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
string removeDuplicates(string s) {
int scnt = s.size();
if(scnt == 1) {
return s;
}
stack<int> st;
string ans = "";
for(int i = 0;i < scnt; ++i) {
if(i == 0) {
st.push(s[i]);
}
else {
if(!st.empty()) {
if(st.top() == s[i]) {
st.pop();
}
else {
st.push(s[i]);
}
}
else {
st.push(s[i]);
}
}
}
while(!st.empty()) {
ans += st.top();
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};标准答案
用栈实现
//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
string removeDuplicates(string S) {
stack<char> st;
for (char s : S) {
if (st.empty() || s != st.top()) {
st.push(s);
} else {
st.pop(); // s 与 st.top()相等的情况
}
}
string result = "";
while (!st.empty()) { // 将栈中元素放到result字符串汇总
result += st.top();
st.pop();
}
reverse (result.begin(), result.end()); // 此时字符串需要反转一下
return result;
}
};用字符串模拟栈实现
class Solution {
public:
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. 逆波兰表达式求值 - 力扣（LeetCode）
思路:用栈来解决该题，遇到数字则入栈，遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。
- 注意：
- 两个出栈数字的运算顺序是 后出栈的数字
+-*/先出栈的数字 - 为防止溢出，应该使用long long 来作为数据类型
- 两个出栈数字的运算顺序是 后出栈的数字
我的AC代码
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long> st;
for(auto a : tokens) {
long long tmp1;
long long tmp2;
if(a == "+") {
tmp1 = st.top();
st.pop();
tmp2 = st.top();
st.pop();
st.push(tmp1 + tmp2);
}
else if(a == "-") {
tmp1 = st.top();
st.pop();
tmp2 = st.top();
st.pop();
st.push(tmp2 - tmp1);
}
else if(a == "*") {
tmp1 = st.top();
st.pop();
tmp2 = st.top();
st.pop();
st.push(tmp2 * tmp1);
}
else if(a == "/") {
tmp1 = st.top();
st.pop();
tmp2 = st.top();
st.pop();
st.push(tmp2 / tmp1);
}
else if(stoi(a) >= -200 && stoi(a) <= 200) {
st.push(stoi(a));
}
}
return st.top();
}
};标准答案
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 力扣修改了后台测试数据，需要用longlong
stack<long long> st;
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;
}
};
Comments NOTHING