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

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();
}