您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 訊息 >> iOS 相關資訊

演算法練習:括號配對問題解析

編輯:iOS 相關資訊

問題描述

括號配對問題要求判斷一行只包含 [、]、(、) 的字串是否合法配對。合法的意思是每個左括號都有對應的右括號,且閉合順序正確。

演算法思路

最直觀的方法是使用堆疊。遍歷字串時,遇到左括號就放入堆疊;遇到右括號時,檢查堆疊頂端是否為對應的左括號。若符合就彈出,若不符合或堆疊為空,則表示不合法。全部處理完後,若堆疊為空,代表所有括號都成功配對。

範例說明

以 [(]) 為例,流程會先把 [ 放入,再把 ( 放入;遇到 ] 時,堆疊頂端是 (,不匹配,因此結果為 No。以 ([[]()]) 為例,每次遇到右括號都能與堆疊頂端正確配對,最後堆疊清空,因此結果為 Yes。

實作重點

使用 C++ 時,可用 vector 或 string 模擬堆疊,也可用 stack 容器。注意輸入可能包含多組測試資料,且每組字串長度可能很長,因此演算法時間複雜度應保持 O(n)。此外,輸入需排除空字串與過長字串的異常情況。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved