遵义市汇川区建设厅网站,擼擼擼做最好的导航网站,中国核工业第五建设有限公司待遇,中天建设哪里的20.有效的括号 栈类的题目都很神奇#xff0c;这道题分有不有效有三种情况#xff0c;一种是左括号多了#xff0c;一种是右括号多了#xff0c;一种是左括号和右括号不匹配。我们设置一个栈来放s[i]所对应的右括号#xff0c;如果s[i]‘{’#xff0c;那么就在栈里放‘}…20.有效的括号 栈类的题目都很神奇这道题分有不有效有三种情况一种是左括号多了一种是右括号多了一种是左括号和右括号不匹配。我们设置一个栈来放s[i]所对应的右括号如果s[i]‘{’那么就在栈里放‘}’依次类推.......假如遇到的是一个右括号那么就看看它和栈顶元素是否匹配因为栈顶元素对应的是最近的一个左括号如果不匹配就返回false,对应的是左括号和右括号不匹配的情况。假如说还没把s遍历完栈就为空了说明这时候右括号多了也返回false最后怎么判断左括号多了的情况呢就看遍历完后栈是否为空不为空说明左括号多了不匹配。
https://leetcode.cn/problems/valid-parentheses/
class Solution {
public:bool isValid(string s) {stackcharright;for(int i0;is.size();i){if(s[i]{){right.push(});}else if(s[i](){right.push());}else if (s[i][){right.push(]);}else if(right.empty()||right.top()!s[i])return false;elseright.pop();}return right.empty();}
};
1047.删除字符串中的所有相邻重复项 这道题和上一道题的内核有点像本质上都是消消乐即遇到匹配的元素就两个一起销毁。所以一开始的思路是先设置一个栈然后遍历给定的字符串s如果s[i]栈顶元素说明可以消消乐了所以stack.pop()然后我们再把栈里面的元素取出来但由于是先进后出所以结果还得reverse。不过我们也可以用字符串来模拟栈这样就不用reverse,相当换了一个方向我们还是遍历字符串如果s[i]和result的最后一个元素相同那么就消消乐result.pop_back()注意这里的前提条件是栈即字符串result不能为空如果元素不同那么result.push_back(s[i])。
https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/、
class Solution {
public:string removeDuplicates(string s) {string result;for(int i0;is.size();i){ if(!result.empty()s[i]result.back()){result.pop_back();}else{result.push_back(s[i]);}} return result;}
};
150.逆波兰表达式求值 这道题还是采用消消乐的方法一旦遇到符号就把栈顶元素和栈顶元素的下一个元素进行运算然后又返回栈里。这道题看似简单实际上有几个小细节需要注意虽然tokens[i]对应的都只是一个字符但是它还是字符串所以判断的时候要写tokens[i] 而不能写tokens[i] ‘’注意单引号和双引号的区别同时我们把元素入栈的时候由于是把字符串入栈所以要先把字符串转换为int类型再放入栈中所以要用stoi函数 st.push(std::stoi(tokens[i]));最后我们要得到结果这时候需要取出栈里面的结果就要用到stack.top()。
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
class Solution {
public:int evalRPN(vectorstring tokens) {stackintst;for(int i0;itokens.size();i){if (tokens[i] || tokens[i] - || tokens[i] * || tokens[i] /) {int num1st.top();st.pop();int num2st.top();st.pop();int temp;if(tokens[i]){tempnum2num1;}else if(tokens[i]-){tempnum2-num1;}else if(tokens[i]*){tempnum2*num1;}else if(tokens[i]/){tempnum2/num1;}st.push(temp);}else{st.push(std::stoi(tokens[i]));}}int resultst.top();st.pop();return result;}
};
