數據結構與算法-有效的括號
大家好，歡迎來到我們的算法學習系列。今天是我們的第一篇文章，我們將探討一個經典的面試題目——有效的括號匹配問題。
什么是有效的括號匹配？
在許多編程語言中，括號用于定義代碼塊、函數參數等。確保這些括號正確匹配是編譯器的重要任務之一。而在算法面試中，這個問題常用來考察你的基本數據結構和邏輯思維能力。
問題描述
給定一個只包括 (, ), {, }, [, ] 的字符串，判斷字符串是否有效。
一個有效的字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
示例
- 輸入:
()
輸出:true - 輸入:
()[]{}
輸出:true - 輸入:
(]
輸出:false - 輸入:
([)]
輸出:false - 輸入:
{[]}
輸出:true
解決思路
我們可以使用棧這種數據結構來解決這個問題。棧是一種后進先出的數據結構（LIFO）。當我們遇到一個左括號時，我們將其推入棧中；當我們遇到一個右括號時，我們檢查棧頂的元素是否是對應的左括號，如果是，我們將棧頂元素彈出。最后，如果棧為空，則說明所有的括號都匹配了。
實現代碼
下面是用JavaScript實現這個算法的代碼：
function isValid(s) {const stack = [];const map = {'(': ')','{': '}','[': ']'};for (let i = 0; i < s.length; i++) {if (map[s[i]]) {stack.push(s[i]);} else {const last = stack.pop();if (s[i] !== map[last]) {return false;}}}return stack.length === 0;
}
代碼解析
- 定義棧和映射：我們定義一個空棧
stack用于存儲左括號，并用一個對象map存儲括號的對應關系。 - 遍歷字符串：我們遍歷輸入字符串
s。 - 處理左括號：如果當前字符是左括號，將其推入棧中。
- 處理右括號：如果當前字符是右括號，彈出棧頂的左括號，并檢查它們是否匹配。
- 最終判斷：遍歷完字符串后，如果棧為空，則所有的括號匹配成功，返回
true，否則返回false。
小結
今天，我們介紹了有效的括號匹配問題及其解決方法。這是一個經典的算法面試題，重點考察了你對棧數據結構的理解和應用。明天，我們將進一步探討更多相關的算法問題，并提供更深入的解析和擴展。
感謝大家的閱讀！如果你有任何問題或建議，歡迎在評論區留言。
)
