【CT】LeetCode手撕—20. 有效的括号

题目

• 原题连接：20. 有效的括号

---

1- 思路

模式识别

• 模式1：括号左右匹配 ——> 借助栈来实现 ——> Deque<Character> deque = new LinkedList<>()
• 模式2：顺序匹配 ——> 用 if 判断

具体思路

• 1.遇到左括号
  • 直接入栈相应的右括号
• 2.不匹配情况
  • **① 左括号多：**此时 栈 deque.isEmpty() ，因此该条件下返回 false
  • ② 括号相等但括号顺序不对：此时 s.charAt(i) != deque.poll()，因此此条件下返回 false
  • ③ 右括号多：此时 在遍历完 deque 之后，deque.isEmpty() 结果为 false

---

2- 实现

⭐20. 有效的括号——题解思路

class Solution {public boolean isValid(String s) {Deque<Character> st = new LinkedList<>();for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {st.push(')');} else if (s.charAt(i) == '{') {st.push('}');} else if (s.charAt(i) == '[') {st.push(']');} else if (st.isEmpty() || s.charAt(i) != st.peek()) {return false;} else {st.pop();}}return st.isEmpty();}}

---

3- ACM实现

public class isValid {public static boolean isValid(String s){int n = s.length();Deque<Character> deque = new LinkedList<>();for(int i = 0 ; i < n;i++){if(s.charAt(i)=='['){deque.add(']');}else if(s.charAt(i) == '{'){deque.add('}');}else if(s.charAt(i) == '('){deque.add(')');}else if(deque.isEmpty() || s.charAt(i) != deque.peek()){return false;}else{deque.pop();}}return deque.isEmpty();}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入括号字符串");String str = sc.nextLine();System.out.println("是否为有效括号"+isValid(str));}
}