20. 有效的括号
问题描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
解题思路
引入栈作为辅助数据结构，遍历字符串，依次将左括号入栈；
遇到右括号时，检查它与栈顶元素是否匹配，如果匹配则栈顶元素出栈，遍历继续；
如果栈顶元素为空或者右括号与栈顶元素不匹配，则说明字符串无效。
遍历结束之后，如栈中的所有左括号元素都成功匹配到了右括号，则说明字符串有效。
在Java中，我们用双端队列Deque可以实现Stack的功能：
把元素压栈：push(E)/addFirst(E)；
把栈顶的元素“弹出”：pop(E)/removeFirst()；
取栈顶元素但不弹出：peek(E)/peekFirst()。
- 当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。
代码实现
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new LinkedList();
for(int i = 0; i < s.length(); i++){
Character str = s.charAt(i);
if(str == '(' || str == '[' || str == '{'){
stack.push(str);
}else{
if(stack.isEmpty() || !isMatch(stack.pop(), str)){
return false;
}
}
}
return stack.isEmpty();
}
private boolean isMatch(Character s1, Character s2){
if( s1 == '{' && s2 == '}'){
return true;
}else if(s1 == '[' && s2 == ']'){
return true;
}else if(s1 == '(' && s2 == ')'){
return true;
}else{
return false;
}
}
}
上述代码判断左右括号是否匹配的逻辑也可以采用HashMap（key为左括号，value为对应的右括号）来实现
class Solution {
public boolean isValid(String s) {
HashMap<Character, Character> map = new HashMap<>();
map.put('(',')');
map.put('[',']');
map.put('{','}');
Deque<Character> stack = new LinkedList();
for(int i = 0; i < s.length(); i++){
Character str = s.charAt(i);
if(str == '(' || str == '[' || str == '{'){
stack.push(str);
}else{
if(stack.isEmpty() || !str.equals(map.get(stack.pop()))){
return false;
}
}
}
return stack.isEmpty();
}
}
856. 括号的分数
问题描述
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
解题思路
分析解读S的得分规则：
- 相邻括号对()才会得分；
- 每个相邻括号对所得的分数为其2^n，其中n为括号对左侧的左括号数量（不包括当前相邻括号对的左括号），也就是说n=stack.size() -1
- 平衡括号字符串 S的总得分为其中所有相邻括号对所得分数之和
代码实现
class Solution {
public int scoreOfParentheses(String S) {
Deque<Character> stack = new LinkedList<>();
int sum = 0;
Character prev = ')';
for(int i = 0; i < S.length(); i++){
Character c = S.charAt(i);
if(c.equals('(')){
stack.push(c);
}else{
//相邻的()才会得分
if(prev.equals('(')){
sum += 1 << (stack.size() -1);
}
stack.pop();
}
prev = c;
}
return sum;
}
}
