leetcode【棧與隊列—簡單】 20. 有效的括号

文章目錄

• 前言
• 題目
• 題解
• • NO1：棧解決
• 參考文章

前言

哈喽，我是長路，目前剛剛大三，方向是後端也偶爾搗鼓下前端，現在的主語言是Java。之前一大段時間都是在學習web開發的一些技術，就很久沒有進行類似于資料結構、算法之類的學習與刷題，打算這段時間拾起來好好學一學、搞一搞。

這段時間也是機緣巧合看到草帽路飛的部落格，加了自學群，正巧看到部落客組織在群裡組織了leetcode刷題打卡活動，我也就參與進來，為期一個月，打算堅持每天都花一些時間做一些題目，并通過部落格的方式來進行記錄。

目前跟着一個Github倉庫刷題(leetcode)：代碼随想錄leetcode刷題，目前為棧與隊列專題。

題目來源leetcode

leetcode位址：20. 有效的括号，難度：簡單。

題目描述(摘自leetcode)：

給定一個隻包括 '('，')'，'{'，'}'，'['，']' 的字元串 s ，判斷字元串是否有效。

有效字元串需滿足：
左括号必須用相同類型的右括号閉合。
左括号必須以正确的順序閉合。
 
示例 1：
輸入：s = "()"
輸出：true

示例 2：
輸入：s = "()[]{}"
輸出：true

示例 3：
輸入：s = "(]"
輸出：false

示例 4：
輸入：s = "([)]"
輸出：false

示例 5：
輸入：s = "{[]}"
輸出：true
 
提示：
1 <= s.length <= 104
s 僅由括号 '()[]{}' 組成
           

本地調試代碼：

class Solution {
    public int search(int[] nums, int target) {
        ....
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{-1,0,3,5,9,12};//這裡修改數組内容
        System.out.println(solution.search(arr, 2));//數組、目标值
    }
}
           

思路：若是左閉合符号就壓入配對的右閉合符号，友善之後進行比對。

示例："()[{}]"   stack=[]
① 字元'('，壓入')'  stack=['(']
② 字元')'，與目前棧頂存放比對，出棧  stack=[]
③ 字元'['，壓入']'  stack=[']']
④ 字元'{'，壓入'}'  stack=[']','}']
⑤ 字元'}'，與目前棧頂存放比對，出棧 stack=[']']
⑥ 字元']'，與目前棧頂存放比對，出棧 stack=[]
所有字元都周遊一遍之後，判斷棧中是否存在元素，為空表示有效括号；不為空表示無效括号。
           

代碼：

public boolean isValid(String s) {
    Deque<Character> stack = new LinkedList<>();
    for (char c : s.toCharArray()) {
        //前面三個判斷當比對到左閉合時存儲右閉合符号到棧，之後用來進行直接比對
        if(c == '('){
            stack.push(')');
        }else if(c == '{'){
            stack.push('}');
        }else if(c == '['){
            stack.push(']');
        }else if(stack.isEmpty() || stack.peek() != c){ //若是棧為空或者對應比對的不一緻，直接判定不比對
            return false;
        }else {
            stack.pop();
        }
    }
    //若是為空，表示全部比對完了，若是沒有空說明另外少了右閉合括括号
    return stack.isEmpty();
}