长沙微营销,seo竞价推广,php和mysql网站毕业设计,动画设计师月薪多少目录
有效的括号
用到的数据结构#xff1a;
位运算、Map 和 Stack
Stack 常用的函数#xff1a;
题解#xff1a;
代码#xff1a;
运行结果; 给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符…
目录
有效的括号
用到的数据结构
位运算、Map 和 Stack
Stack 常用的函数
题解
代码
运行结果; 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例 1 输入s ()
输出true示例 2 输入s ()[]{}
输出true示例 3 输入s (]
输出false提示 1 s.length 104s 仅由括号 ()[]{} 组成 用到的数据结构 位运算、Map 和 Stack 使用位运算 (n1)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 ns.length();// 判断奇偶if((n1)1) return false;// 存储左右括号映射MapCharacter,Character bucketsnew HashMap();buckets.put((,));buckets.put([,]);buckets.put({,});// 存储左括号StackCharacter stack new Stack();// 存储当前括号字符char bucket;// 遍历处理for(int i0;in;i){buckets.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();}
} 运行结果;
