day11
20.有效的括号
题目链接：20. 有效的括号
题目思路：使用栈的思路，碰到左括号，就将对应的右括号压入栈，判断栈是否为空，或者栈顶元素是否等于第i个。
class Solution {
public:
bool isValid(string s) {
// 定义栈
stack<int> st;
// 如果为奇数个直接返回false，肯定不匹配
if ( s.size() % 2 != 0) return false;
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(); //如果都不满足删除栈顶元素，也就是说这种是s[i] == st.top()的情况，移除栈顶元素
}
return st.empty();
}
};
1047.删除字符串中的所有相邻重复项
题目链接：1047. 删除字符串中的所有相邻重复项
解题思路：借用栈的方法，将没有出现过的元素都加入栈，出现过的元素直接弹出栈，最终得到结果，注意这块栈如何变为字符串，第一次不会写。
注意：这里可以直接将字符串作为栈
class Solution {
public:
string removeDuplicates(string s) {
if (s.size() == 1) return s;
// 定义一个栈
stack<int> st;
for ( int i = 0; i < s.size() ; i++){
// 如果栈为空
if ( st.empty() || s[i] != st.top() ){
st.push(s[i]);
}
else if ( s[i] == st.top()){
st.pop();
}
// else if ( s[i] != st.top() ){
// st.push(s[i]);
// }
}
// 将栈转换为字符串后再反转。
string result = "";
while( !st.empty()){ //将栈中的元素result字符串汇总
result += st.top();
st.pop();
}
reverse( result.begin(),result.end());//此时字符串需要反转
return result;
}
};
//直接将字符串作为栈来解决
string result;
for( char t: s){
if ( result.empty() || result.back() != t){ //.back() 返回最后一个元素
result.push_back(t); //在容器对象的末尾插入一个新元素
}
else{
result.pop_back(); //删除容器对象的最后一个元素
}
}
return result;
150.逆波兰表达式求值
题目链接：150. 逆波兰表达式求值
解题思路：使用栈的方法，碰到数字压入栈，碰到运算符取出栈中的元素进行运算然后再存入栈。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 定义栈来解决问题
stack<long long> st;
for ( int i = 0; i < tokens.size(); i++){
if ( tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
long long nums1 = st.top();
st.pop();
long long nums2 = st.top();
st.pop();
// 注意-和÷的先后顺序
if (tokens[i] == "+" ) st.push( nums2 + nums1);
else if ( tokens[i] == "-" ) st.push( nums2 - nums1 );
else if ( tokens[i] == "*" ) st.push( nums2 * nums1 );
else if ( tokens[i] == "/") st.push( nums2 / nums1 );
}
else{
st.push( stoll(tokens[i]));
}
}
int result = st.top();
st.pop();
return result;
}
};
// long long 占用8字节64位
// int 占用4字节 32位
// stoll 同 int 转换，只是范围不一样 stoll-> long long型