【基础算法】栈

1.删除字符串中所有相邻项

删除字符串中所有相邻项

class Solution {
public:string removeDuplicates(string s) {string ret;for(auto ch : s){if(ret.size() && ch == ret.back()) ret.pop_back();else ret.push_back(ch);}return ret;}
};

2.比较含退格的字符串

比较含退格的字符串

class Solution {
public:bool backspaceCompare(string s, string t) {return changeStr(s) == changeStr(t);}string changeStr(string s){string ret;for(auto ch : s){if(ch != '#') ret += ch;else {if(ret.size()) ret.pop_back();}}return ret;}
};

3.基本计数器ii

基本计数器ii

class Solution {
public:int calculate(string s) {vector<int> st;char op = '+';int i = 0, n = s.size();while(i < n){if(s[i] == ' ') i++;else if(s[i] >= '0' && s[i] <= '9'){int tmp = 0;while(i < n && s[i] >= '0' && s[i] <= '9')tmp = tmp * 10 + (s[i++] - '0');if(op == '+') st.push_back(tmp);else if(op == '-') st.push_back(-tmp);else if(op == '*') st.back() *= tmp;else if(op == '/') st.back() /= tmp;}else {op = s[i];i++;}}int ret = 0;for(auto e : st) {ret += e;}return ret;}
};

4.字符串解码

字符串解码

class Solution {
public:string decodeString(string s) {stack<int> nums;stack<string> st;st.push("");int n = s.size();int i = 0;while(i < n){if(s[i] >= '0' && s[i] <= '9'){int tmp = 0;while(s[i] >= '0' && s[i] <= '9'){tmp = tmp * 10 + (s[i] - '0');i++;}nums.push(tmp);}else if(s[i] == '['){i++;//跳过'['string tmp = "";while(s[i] >= 'a' && s[i] <= 'z'){tmp += s[i];i++;}st.push(tmp);}else if(s[i] == ']'){string tmp = st.top();st.pop();int k = nums.top();nums.pop();while(k--){st.top() += tmp;}i++;}else{while(i < n && s[i] >= 'a' && s[i] <= 'z'){st.top() += s[i];i++;}}}return st.top();}
};

5.验证栈序列

验证栈序列

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i = 0, n = popped.size();for(auto x : pushed){st.push(x);while(st.size() && st.top() == popped[i]){st.pop();i++;}}return i == n;}
};