【LeetCode】20. 有效的括号(Deque的Stack用法)

??今日学习的文章链接和视频链接

leetcode题目地址：20. 有效的括号

?代码随想录题解地址：代码随想录

题目简介

给定一个只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

看到题目的第一想法(可以贴代码）

1. 经典的数据结构题目

? ? ? ? push所有的左括号类，遇到右括号类则判断栈顶元素是否为其对应的左括号项，选择是否pop，最后判断栈是否为空。

public boolean isValid(String s) {
    Stack<Character> st = new Stack<>();
    char[] c = s.toCharArray();
    for (char i : c){
        if (i == '('|| i == '[' || i == '{'){
            st.push(i);
            System.out.println("push"+i);
        }else if (i == ')'){
            if (st.empty() || st.peek() != '(') return false;
            if (st.peek() == '(') st.pop();
        }else if (i == ']'){
            if (st.empty() || st.peek() != '[') return false;
            if (st.peek() == '[') st.pop();
        }else if (i == '}'){
            if (st.empty() || st.peek() != '{') return false;
            if (st.peek() == '{') st.pop();
        }
    }
    if (st.empty()) return true; else return false;
}

实现过程中遇到哪些困难

无

看完代码随想录之后的想法

【解题思路】遇到左括号类，push其对应的右括号类，遇到右括号类，判断是否等于栈顶元素，选择是否pop，最后判断栈是否为空。

【想法】

无

看完视频自己写的ACC：

public boolean isValid(String s) {
    Stack<Character> st = new Stack<>();
    char[] c = s.toCharArray();
    for (char i : c){
        if (i == '('){
            st.push(')');
        }else if (i == '['){
            st.push(']');
        }else if (i == '{'){
            st.push('}');
        }else if (i == ')' || i == ']' || i == '}'){
            if (st.empty() || st.peek() != i){
                return false;
            }else { 
                st.pop(); 
            }
        }
    }
    if (st.empty()) return true; else return false;
}

标准答案

public boolean isValid(String s) {
    Deque<Character> deque = new LinkedList<>();
    char ch;
    for (int i = 0; i < s.length(); i++) {
        ch = s.charAt(i);
        //碰到左括号，就把相应的右括号入栈
        if (ch == '(') {
            deque.push(')');
        }else if (ch == '{') {
            deque.push('}');
        }else if (ch == '[') {
            deque.push(']');
        } else if (deque.isEmpty() || deque.peek() != ch) {
            return false;
        }else {//如果是右括号判断是否和栈顶元素匹配
            deque.pop();
        }
    }
    //最后判断栈中元素是否匹配
    return deque.isEmpty();
}

学习时长

略

---

今日收获

Stack类的初始化：

????????Deque<Character> deque = new LinkedList<>();

????????Stack<Character> st = new Stack<>();

Deque可作Queue，也可作Stack：

public interface Deque<E> extends Queue<E> {
? ? void addFirst(E e);
? ? void addLast(E e);
? ? boolean offerFirst(E e);
? ? boolean offerLast(E e);
? ? E removeFirst();
? ? E removeLast();
? ? E pollFirst();
? ? E pollLast();
? ? E getFirst();
? ? E getLast();
? ? E peekFirst();
? ? E peekLast();
? ? boolean removeFirstOccurrence(Object o);
? ? boolean removeLastOccurrence(Object o);
?
? ? // *** Queue methods ***
? ? boolean add(E e);
? ? boolean offer(E e);
? ? E remove();
? ? E poll();
? ? E element();
? ? E peek();
?
? ? // *** Stack methods ***
? ? void push(E e);
? ? E pop();
? ??
? ? // *** Collection methods ***
? ? boolean remove(Object o);
? ? boolean contains(Object o);
? ? public int size();
? ? Iterator<E> iterator();
? ? Iterator<E> descendingIterator();
}