目录
有效的括号
用到的数据结构:
位运算、Map 和 Stack
Stack 常用的函数:
题解:
代码:
运行结果;
给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()" 输出:true示例 2:
输入:s = "()[]{}" 输出:true示例 3:
输入:s = "(]" 输出:false提示:
1 <= s.length <= 104
s
仅由括号'()[]{}'
组成
用到的数据结构:
位运算、Map 和 Stack
使用位运算
(n&1)==1
来判断字符串长度n
是否为奇数,如果是奇数则直接返回 false。因为有效的括号序列必须是成对出现的。使用 Map 数据结构
buckets
来存储左右括号的映射关系。键值对的形式为左括号-右括号。使用了 Stack 栈数据结构
stack
来存储遍历过程中的左括号Stack 常用的函数:
push(E item)
: 将元素 item 压入栈顶。
pop()
: 弹出并返回栈顶的元素。
peek()
: 返回栈顶的元素,但不进行弹出操作。
isEmpty()
: 判断栈是否为空,如果为空则返回 true,否则返回 false。
size()
: 返回栈中元素的个数。题解:
遍历字符串的每个字符,如果当前字符是左括号,则将其入栈;如果当前字符是右括号,则判断栈是否为空或者当前右括号是否与栈顶的左括号匹配。如果不匹配,则返回 false;如果匹配,则弹出栈顶的左括号。
最后判断栈是否为空,如果为空则表示所有的左括号都有相应的右括号匹配,返回 true;否则返回 false。
代码:
class Solution {public boolean isValid(String s) {int n=s.length();// 判断奇偶if((n&1)==1) return false;// 存储左右括号映射Map<Character,Character> buckets=new HashMap<>();buckets.put('(',')');buckets.put('[',']');buckets.put('{','}');// 存储左括号Stack<Character> stack =new Stack<>();// 存储当前括号字符char bucket;// 遍历处理for(int i=0;i<n;i++){bucket=s.charAt(i);if(buckets.containsKey(bucket)){stack.push(bucket);// 为左括号,入栈}else if(stack.isEmpty() || bucket !=buckets.get(stack.peek())){return false;//当前为右括号但是此时栈为空或和栈顶不匹配}else{stack.pop();//当前右括号和栈顶匹配,弹出栈顶}}return stack.isEmpty();} }
运行结果;