leetcode算法之栈

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+=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 x:st) ret+=x;return ret;}
};

4.字符串解码

字符串解码

class Solution {
public:string decodeString(string s) {//双栈stack<string> st;stack<int> nums;st.push("");int i =0,n = s.size();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');nums.push(tmp);}else if(s[i] == '['){i++;string tmp;while(s[i]>='a'&&s[i]<='z') tmp+=s[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{string tmp;while(i<n && s[i]>='a'&&s[i]<='z') tmp+=s[i++];st.top()+=tmp;}}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 ch:pushed){st.push(ch);while(st.size() && st.top() == popped[i]) {st.pop();i++;}}return i==n;}
};