大连百度网站快速优化,wordpress没人维护了,网站开发协议书,网站建设服务哪个便宜题目描述
给定一个只包括 ‘(’#xff0c;‘)’#xff0c;‘{’#xff0c;‘}’#xff0c;‘[’#xff0c;‘]’ 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右…题目描述
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号 测试样例1
输入s ()
输出true测试样例2
输入s (]
输出false测试样例3
输入s ()[]{}
输出true思路
本题考察栈的应用。这里使用stl实现。 要考虑以下几种情况 /******* 1.前面括号全都匹配成功此时栈空了但下一个元素是右括号。例如(()) 2.左括括号入栈后只有但左括号后面的全部匹配。此时栈遍历一遍栈不为空。例如{()()
3、左括号入栈后来一个非匹配的有括号{(}
原则遇到左括号就入栈遇到右的括号就取栈顶一个元素出栈来消耗一个右括号
注意本题用了stlpop()无返回值如果有返回值代码更简洁当然也可以使用别的方法。我这里仅仅提供一种思路。 class Solution {
public:bool isValid(string s) {stackchar st;//定义一个栈for(int i0;is.size();i){if(s[i]( || s[i]{ || s[i][){//当是左括号时入栈。st.push(s[i]);//压入栈中}else{//右括号if(st.empty()true)//是右括号但是栈中已空属于上面的第一种情况return false;//匹配失败if(s[i]) st.top()!(){ //如果扫描到的是右括号从栈中弹出的也就是消耗出来的不与之匹配属于第三种情况return false;//匹配失败}else if(s[i]) st.top()(){//如果左右匹配则弹出元素。st.pop();}if(s[i]} st.top()!{){ //同上return false;//匹配失败}else if(s[i]} st.top(){){st.pop();}if(s[i]] st.top()![){ //同上return false;//匹配失败}else if(s[i]] st.top()[){st.pop();}}}
//循环遍历一遍后如果栈最后为空则匹配成功if(st.empty()){return true;}else{return false;}//栈中不空属于第二种情况代表有单左括号。}
};但还有一些技巧在匹配左括号的时候右括号先入栈就只需要比较当前元素和栈顶相不相等就可以了比左括号先入栈代码实现要简单的多了
方法二
class Solution {
public:bool isValid(string s) {if (s.size() % 2 ! 0) return false; // 如果s的长度为奇数一定不符合要求stackchar 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(]);// 第三种情况遍历字符串匹配的过程中栈已经为空了没有匹配的字符了说明右括号没有找到对应的左括号 return false// 第二种情况遍历字符串匹配的过程中发现栈里没有我们要匹配的字符。所以return falseelse if (st.empty() || st.top() ! s[i]) return false;else st.pop(); // st.top() 与 s[i]相等栈弹出元素}// 第一种情况此时我们已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号来匹配所以return false否则就return truereturn st.empty();}
};
