20. 有效的括号
这题有这种匹配（局部对称）的特征，用堆栈先进先出的结构很方便，通过遍历左括号，将右括号压栈，再在遍历到右括号的时候匹配栈内元素完成，很有哈希表算A+B = target用 A= target - B的意思，具体要考虑以下三种失效的情况。
- 遍历到右括号的时候，如果和栈顶元素不匹配，代表括号种类不匹配。
- 遍历到右括号的时候，如果栈内是空的，代表右括号是多余的，或者说没有左括号跟右括号匹配。
- 遍历完字符串时，如果栈还不是空，代表左括号是多余的，因为没有对应的右括号将栈内元素弹出。
当遍历完字符串且栈为空，则代表匹配。
C++
class Solution {
public:
bool isValid(string 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('}');
else if (st.empty() || s[i] != st.top()) return false;
else st.pop();
}
return st.empty();
}
};
C#
public class Solution {
public bool IsValid(string s) {
Stack<char> st = new Stack<char>();
for (int i = 0; i < s.Length; i++) {
if (s[i] == '(') st.Push(')') ;
else if (s[i] == '[') st.Push(']');
else if (s[i] == '{') st.Push('}');
else if (st.Count == 0|| s[i] != st.Peek()) return false;
else st.Pop();
}
return st.Count == 0;
}
}
1047. 删除字符串中的所有相邻重复项
知道栈为什么适合做这种类似于爱消除的操作，因为栈帮助我们记录了遍历数组当前元素时候，前一个元素是什么。
二刷看一下双指针模拟堆栈法，和C#的StringBuilder。
C++
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;
}
};
也可以直接把string当栈用。
class Solution {
public:
string removeDuplicates(string s) {
string result;
for (int i = 0; i < s.size(); i++) {
if (result.empty() || result.back() != s[i]) result.push_back(s[i]);
else result.pop_back();
}
return result;
}
};
C#
Stack,Queue定义的时候记得new。
public class Solution {
public string RemoveDuplicates(string s) {
Stack<char> st = new Stack<char>();
char[] a = s.ToCharArray();
for (int i = 0; i < a.Length; i++) {
if(st.Count == 0 || a[i] != st.Peek()) st.Push(a[i]);
else st.Pop();
}
Array.Resize(ref a, st.Count);
for(int i = a.Length - 1; i >= 0; i--) {
a[i] = st.Pop();
}
return new string(a);
}
}
150. 逆波兰表达式求值
思路是每扫到运算符就取两个栈元素做运算，注意减和除两个数的顺序，运算结果再压回栈。
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 n1 = st.top();
st.pop();
int n2 = st.top();
st.pop();
int tmp = 0;
if (tokens[i] == "+") tmp = n1 + n2;
if (tokens[i] == "-") tmp = n2 - n1;
if (tokens[i] == "*") tmp = n1 * n2;
if (tokens[i] == "/") tmp = n2 / n1;
st.push(tmp);
}
else {
st.push(stoi(tokens[i]));
}
}
return st.top();
}
};
C#
C#可以用int.TryParse更方便，且siwtch可以判断字符串（C++siwtch只能判断整形）。
public class Solution {
public int EvalRPN(string[] tokens) {
int num = 0;
Stack<int> stack = new Stack<int>();
for (int i = 0; i< tokens.Length; i++) {
if (int.TryParse(tokens[i], out num)) {
stack.Push(num);
} else {
int num1 = stack.Pop();
int num2 = stack.Pop();
switch (tokens[i])
{
case "+":
stack.Push(num1 + num2);
break;
case "-":
stack.Push(num2 - num1);
break;
case "*":
stack.Push(num1 * num2);
break;
case "/":
stack.Push(num2 / num1);
break;
}
}
}
return stack.Pop();
}
}
二刷
有效的括号
三种情况，左括号多余，右括号多余，左右不匹配，分别对应访问完字符串栈还有东西，访问过程栈为空了，还有就是访问元素和栈顶不匹配，可以反向往栈里放东西，这样代码更简洁，一开始写有点麻烦了。
- 匹配和消除问题是栈的强项。
class Solution {
public:
bool isValid(string s) {
stack<char> data;
for (char a : s) {
if (a == '(' || a == '[' || a == '{') {
data.push(a);
}
if (a == ')') {
if (!data.empty() && data.top() == '(') data.pop();
else return false;
}
if (a == '}') {
if (!data.empty() && data.top() == '{') data.pop();
else return false;
}
if (a == ']') {
if (!data.empty() && data.top() == '[') data.pop();
else return false;
}
}
if (data.empty()) return true;
else return false;
}
};
//简化
class Solution {
public:
bool isValid(string s) {
stack<char> data;
for (char a : s) {
if (a == '(') data.push(')');
else if (a == '[') data.push(']');
else if (a == '{') data.push('}');
else if (data.empty() || a != data.top()) return false;
else data.pop();
}
return data.empty();
}
};
删除字符串中的所有相邻项
利用栈保存了上一个元素，直接判断，而且处理完栈顶的一部分，之前的自动就会露出来（这点很重要！）。
- 注意空栈不要调用top(),会超尾-1报错。
class Solution {
public:
string removeDuplicates(string s) {
stack<char> data;
for (char a : s) {
if (data.empty()) {
data.push(a);
}
else if (a != data.top()) {
data.push(a);
}
else {
data.pop();
}
}
string ans = "";
while (!data.empty()) {
ans += data.top();
data.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};
或者用双指针方法（用数组单指针遍历一遍，中间消除后可能会出现新的匹配项比如abba，bb消掉后aa也要消掉，所以需要双指针），slow不断维护，fast遍历。
逆波兰表达式求值
还是用到栈处理完一部分弹出去，之前的自动暴露出来继续处理的特性，每次遇到运算符就弹出来两个数组计算完再把结果压进去，注意弹出来的顺序和运算的顺序是反的。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> data;
for (string it : tokens) {
if (it != "+" && it != "-" && it != "*" && it != "/") data.push(stoi(it));
else {
int it1 = data.top();
data.pop();
int it2 = data.top();
data.pop();
if (it == "+") data.push(it2 + it1);
if (it == "-") data.push(it2 - it1);
if (it == "*") data.push(it2 * it1);
if (it == "/") data.push(it2 / it1);
cout << it1 << it << it2 << " = " <<data.top() << endl;
}
}
return data.top();
}
};
京公网安备 11010502036488号