NC52：括号序列/LeetCode：20.有效的括号
括号序列
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=188&&tqId=38573&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
LeetCode题目地址：https://leetcode-cn.com/problems/valid-parentheses/
方法1
思路：
- 遍历字符串，栈为空时直接入栈，且执行下一循环
- 遇到括号左边就入栈，遇到括号右边就进行判断
- 使用peek()方法取栈顶元素，判断栈顶元素是否是当前右边括号对应的左边括号，是就出栈该左边括号
- 最后判断栈是否为空，为空则为合法的括号序列
- 这个方法需要将整个字符串遍历完，才能根据栈是否为空判断括号序列是否有效
实现代码：
public boolean isValid (String s) {
Stack<Character> stack = new Stack<Character>();
for(int i = 0; i < s.length(); i++){
if(stack.empty()){
stack.push(s.charAt(i));
continue;
}
if(s.charAt(i) == ')' && stack.peek() == '('){
stack.pop();
}else if(s.charAt(i) == ']' && stack.peek() == '['){
stack.pop();
}else if(s.charAt(i) == '}' && stack.peek() == '{'){
stack.pop();
}else{
stack.push(s.charAt(i));
}
}
return stack.empty();
} 方法2
思路：
- 当遇到左边括号，就入栈它对应的右边括号
- 当遇到右边括号，就判断当前栈是否为空，为空就直接返回false，说明这时栈里面铁定没有其左括号入栈的右括号，这时的序列铁定是无效的
- 若栈不为空，就将栈顶元素出栈，判断栈顶元素是否与当前遇到的右边括号相同
- 因为入栈的都是对应左边括号的右边括号，所以不相同就说明该右边括号与左边括号不对应，直接就可以返回false，不用继续再遍历下去
- 注意：最后的返回不能直接返回true，因为有可能会遇到全是左括号的序列，这时会跳过右括号的判断，若直接返回true就错了，应该将判断栈是否为空作为结果返回
public boolean isValid(String s) {
if(s == null || s.length() == 0){
return false;
}
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '('){
stack.push(')');
}else if(c == '['){
stack.push(']');
}else if(c == '{'){
stack.push('}');
}else if(stack.empty() || stack.pop() != c){
return false;
}
}
return stack.empty();
} 
网易公司福利 165人发布
查看17道真题和解析