LeetCode 20.有效的括号 Java

题名：LeetCode 20.有效的括号 参考：LeetCode官方题解 内容：重新写了一遍自己的理解 差别：没啥差别，为了加强记忆写的 0.0 语言：Java 标签：简单

主要数据结构：

栈：正括号压入栈，反括号和最近的一个正括号抵消。因为()算有效的括号，而)(不算，若压入反括号，当栈为空的时候，有可能不是有效的括号。如果不嫌麻烦的话，用队列也可以。（俺没试过队列 0.0）HashMap：对应正括号和反括号的。注意：key为反括号，value为正括号。因为当栈取出最顶上那层的正括号时，若要使其为有效字符串，下一个字符肯定是反括号，而如果key为正括号，value为反括号，map.get(反括号)会抛出空指针错误。

思路：

正括号压入栈，若出现第一个反括号，消掉与其最近的正括号

代码：

import java.util.HashMap; import java.util.Stack; public class ValidBracket { public static void main(String[] args) { Solution s=new Solution(); System.out.println(s.isValid("{[[]}}[}()")); } } class Solution{ public boolean isValid(String s){ //首先需要一个hashmap用来存放括号,key和value顺序逻辑是：如果map包含正括号，就要push进栈里 HashMap<Character,Character> map=new HashMap<>(); map.put('}','{'); map.put(']','['); map.put(')','('); Stack<Character> stack= new Stack<>(); //注意：stack里全为正括号 //遍历数组 for (int i=0;i<s.length();i++){ char c=s.charAt(i); //获取第一个括号 if (map.containsKey(c)){ //如果c是反括号，则要匹配括号对，进行消去 //既然stack里全是正括号，那么输入的第一个反括号(c)与与最近的正括号(topElement)匹配(用map的键对值实现)，否则直接返回false //如果栈内为空，说明栈内一个正括号都没有，反而多出来了反括号，此时直接返回False char topElement=stack.empty()?'#': stack.pop(); if (topElement!=map.get(c)){ return false; } //没有else，因为如果匹配成功的化stack的顶层元素已经被弹出来了 }else{ //如果c是正括号 stack.push(c); } } return stack.empty(); //有可能stack内还有正括号，所以当且仅当stack为空时，返回true } }

出现过的Bug：

Bug 1: NullPointerException Stack<Character> stack=new Stack(); 没写类型Character，导致默认类型为Object，并将stack.pop()强制转换为char型 空指针报错原因

Bug 2：NullPointerException if (topElement!=map.get(c)) 此时topElement为正括号，c为反括号，map里的key全是正括号，所以当map.get(key)时，会出现空指针报错。 修改：把key和value反过来存，其余的也要改。 也可以不修改，HashMap根据Value获取Key。