leetcode-cn 有效的括号-白红宇

leetcode-cn 有效的括号

阅读量：6758 次

发布时间：2019-06-26

本文共 2580 字，大约阅读时间需要 8 分钟。

题目描述如图：

解法一：将待匹配的左括号放入队列或栈（因为只需拿最近一个元素并删除，用数组都行，只不过队列封装了removeLast()，所以直接用就好了）

private static boolean notMatch(char left, char right){    return (left == '(' && right != ')') || (left == '[' && right != ']') || (left == '{' && right != '}');}private static boolean isValid(String s) {    int length = s.length();    if ("".equals(s)) {        return true;    }    // 队列用来存左括号    Deque
    
      bracketsIndex = new ArrayDeque<>();    for (int i = 0; i < length; i++) {        char c = s.charAt(i);        if (c == '(' || c == '[' || c == '{') {            bracketsIndex.add(c);        } else if (!bracketsIndex.isEmpty() && (c == ')' || c == ']' || c == '}')) {            if (notMatch(bracketsIndex.removeLast(), c)) {                return false;            }        } else {            return false;        }    }    // 确保入队列的左括号都被消费掉    return bracketsIndex.isEmpty();}

解法二：将待匹配的左括号的索引放入队列，然后判断待匹配的左右括号的索引是否一个为奇数，另一个为偶数

private static boolean oddAndEvenNumber(int leftIndex, int rightIndex){    // 判断两个数是否同时为偶数或同时为奇数    // 要使左右括号能够匹配上，必须满足：如果左括号索引为偶数，右括号索引则为奇数，反之亦然    // 例如 {({}[])} 第一个"{"索引为0，与之匹配的最后一个索引必定为(length-1)奇数    // 没明白的话，自己可以动手列举下，总结规律    return ((leftIndex & 1) == 1) == ((rightIndex & 1) == 1);}private static boolean isValid(String s) {    int length = s.length();    if ("".equals(s)) {        return true;    }    // 队列用来存左边括号的索引    Deque
    
      braceIndex = new ArrayDeque<>();    Deque
     
       bracketsIndex = new ArrayDeque<>();    Deque
      
        parenthesesIndex = new ArrayDeque<>();    int lastIndex;    for (int i = 0; i < length; i++) {        char c = s.charAt(i);        if (c == '(') {            parenthesesIndex.add(i);        } else if (c == '[') {            bracketsIndex.add(i);        } else if (c == '{') {            braceIndex.add(i);        } else if (c == ')' && !parenthesesIndex.isEmpty()) {            // 以下三个 removeLast()调用的目的是取最近一个左括号的索引，用完得删除            if (oddAndEvenNumber(parenthesesIndex.removeLast(), i)) {                return false;            }        } else if (c == ']' && !bracketsIndex.isEmpty()) {            if (oddAndEvenNumber(bracketsIndex.removeLast(), i)) {                return false;            }        } else if (c == '}' && !braceIndex.isEmpty()) {            if (oddAndEvenNumber(braceIndex.removeLast(), i)) {                return false;            }        } else {            return false;        }    }    // 确保入队列的左括号的索引都被消费掉    return braceIndex.isEmpty() && bracketsIndex.isEmpty() && parenthesesIndex.isEmpty();}

有效得括号