【LeetCode热题100】栈

这道题一共记录了关于栈的5道题目：删除字符串中所有相邻重复项、比较含退格的字符串、基本计算器II、字符串解码、验证栈序列。

class Solution {
public:string removeDuplicates(string s) {string ret;for(auto c : s){if(ret.size() == 0 || c != ret.back()) ret += c;else ret.pop_back();}return ret;}
};

题目分析：这道题我们使用数组模拟栈，遍历字符串，把字符依次放到栈里，如果这个字符和栈顶字符一样，那么就出栈，否则入栈。

class Solution {
public:bool backspaceCompare(string s, string t) {return ChangeStr(s) == ChangeStr(t);   }string ChangeStr(string s){string ret; //用数组模拟栈结构for(auto c : s){if(c != '#') ret += c;else if(ret.size() > 0) ret.pop_back();}return ret;}
};

题目分析：这道题也是用数组模拟栈，依次将两个字符串调整，比较调整完的字符串是否相等即可。

class Solution {
public:int calculate(string s) {char op = '+';vector<int> st;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++];}}int ret = 0;for(auto e : st){ret += e;}return ret;}
};

题目分析：这道题我们使用栈来模拟计算过程，在遍历字符串的写一个字符时，需要分情况讨论：

遇到操作符，更新操作符op
遇到数字：

1）先把数字提取出来，记为tmp

2）根据op的不同，分情况讨论：

op == “+” ，tmp直接入栈

op == “-”，-tmp入栈

op == “*”，直接乘到栈顶元素上

op == “/”，直接除到栈顶元素上

class Solution {
public:string decodeString(string s) {stack<string> st;st.push("");stack<int> num;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';}num.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 n = num.top();num.pop();while(n--){st.top() += tmp;}i++;}else{while(i < n && s[i] >= 'a' && s[i] <= 'z'){st.top() += s[i++];}}}return st.top();}
};

题目分析：这道题需要借助建立两个栈来解决，其中一个栈用来存放次数，一个栈用来存放字符串，依次遍历这个字符串，分情况讨论：

1）遇到数字：提取出来这个数，放入“数字栈”。

2）遇到‘[’：把后面的字符串提取出来，放入“字符串栈”中。

3）遇到‘]’：解析，然后放到“字符串栈”栈顶的字符串后面。这里有一个细节需要注意，为了保证操作的一致性，需要在最开始把字符串栈初始化为""。

4）遇到单独的字符：提取出来这个字符串，直接放在“字符串栈”栈顶的字符串后面。

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